Tính balance factor trong AVL Tree JavaScript

AVL tree kiểm tra chiều cao của cây con trái và phải và đảm bảo hiệu số không quá 1. Hiệu số này gọi là Balance Factor (Hệ số cân bằng).

Ví dụ, trong các cây sau, cây đầu tiên cân bằng, hai cây tiếp theo không cân bằng:

Ở cây thứ hai, cây con trái của C có chiều cao 2 và cây con phải có chiều cao 0, hiệu số là 2. Ở cây thứ ba, cây con phải của A có chiều cao 2 và trái thiếu (chiều cao 0), hiệu số cũng là 2. AVL tree chỉ cho phép hiệu số (balance factor) là 1.

BalanceFactor = height(left-subtree) - height(right-subtree)

Nếu hiệu số chiều cao của cây con trái và phải lớn hơn 1, cây được cân bằng bằng một số kỹ thuật xoay.

Hãy định nghĩa phương thức này và khởi tạo class:

Ví dụ

class AVLTree {
  constructor() {
    // Khởi tạo phần tử root là 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;
  }
};