การคำนวณปัจจัยความสมดุลใน Javascript AVL Tree

ต้นไม้ AVL ตรวจสอบความสูงของต้นไม้ย่อยด้านซ้ายและด้านขวา และรับรองว่าความแตกต่างไม่เกิน 1 ความแตกต่างนี้เรียกว่า ปัจจัยความสมดุล>

ตัวอย่างเช่น ในต้นไม้ต่อไปนี้ ต้นไม้ต้นแรกสมดุลและต้นไม้สองต้นถัดไปไม่สมดุล -

ในต้นไม้ที่สอง ต้นไม้ย่อยด้านซ้ายของ C มีความสูง 2 และต้นไม้ย่อยด้านขวามีความสูง 0 ดังนั้นความแตกต่างคือ 2 ในต้นไม้ที่สาม ต้นไม้ย่อยด้านขวาของ A มีความสูง 2 และด้านซ้ายหายไป จึงเป็น 0 และผลต่างเป็น 2 อีกครั้ง ต้นไม้ AVL อนุญาตให้ส่วนต่าง (ปัจจัยสมดุล) เป็น 1 เท่านั้น

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

หากความแตกต่างในความสูงของทรีย่อยซ้ายและขวามากกว่า 1 ต้นไม้จะถูกปรับสมดุลโดยใช้เทคนิคการหมุนบางอย่าง

ให้เรากำหนดวิธีการนี้และเริ่มต้นคลาสด้วย -

ตัวอย่าง

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;
   }
};