Tính hệ số cân bằng trong Cây AVL Javascript

Cây AVL kiểm tra chiều cao của cây con bên trái và bên phải và đảm bảo rằng sự khác biệt không quá 1. Sự khác biệt này được gọi là Hệ số cân bằng. >

Ví dụ, trong các cây sau, cây đầu tiên cân đối và hai cây tiếp theo không cân đối -

Ở cây thứ hai, cây con bên trái của C có chiều cao là 2 và cây con bên phải có chiều cao 0 nên hiệu là 2. Ở cây thứ ba, cây con bên phải của A có chiều cao là 2 và cây con bên trái bị thiếu nên là 0. , và sự khác biệt là 2 lần nữa. Cây AVL cho phép chênh lệch (hệ số cân bằng) chỉ bằng 1.

BalanceFactor = height(left-sutree) − height(right-sutree)

Nếu sự khác biệt về chiều cao của các cây phụ bên trái và bên phải lớn hơn 1 thì cây được cân đối bằng một số kỹ thuật luân canh.

Hãy để chúng tôi xác định phương thức này và khởi tạo cả lớp -

Ví dụ

class AVLTree {
   constructor() {
      // Initialize a root element to null.
      this.root = null;
   }
   getBalanceFactor(root) {
      return this.getHeight(root.left) - this.getHeight(root.right);
   }
   getHeight(root) {
      let height = 0;
      if (root === null) {
         height = -1;
      } else {
         height = Math.max(this.getHeight(root.left), this.getHeight(root.right)) + 1;
      }
      return height;
   }
}
AVLTree.prototype.Node = class {
   constructor(data, left = null, right = null) {
      this.data = data;
      this.left = left;
      this.right = right;
   }
};