การคำนวณ Balance Factor ใน AVL Tree ด้วย JavaScript

AVL tree ตรวจสอบความสูงของ left และ right sub-trees และรับรองว่าความต่างไม่เกิน 1 ความต่างนี้เรียกว่า Balance Factor

เช่นใน tree ต่อไปนี้ tree แรกสมดุล สอง tree ถัดไปไม่สมดุล:

ใน tree ที่สอง left subtree ของ C สูง 2 right subtree สูง 0 ความต่างคือ 2 ใน tree ที่สาม right subtree ของ A สูง 2 left หายไป คือ 0 ความต่างคือ 2 อีกครั้ง AVL tree อนุญาตให้ balance factor แค่ 1

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

ถ้าความต่างของความสูง left และ right sub-trees มากกว่า 1 tree จะถูกปรับสมดุลด้วย rotation techniques

มากำหนดเมธอดนี้และ initialize คลาส:

ตัวอย่างโค้ด

class AVLTree {
  constructor() {
    // Initialize root element เป็น 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;
  }
};