การแทรกโหนดใน Javascript AVL Tree

เราสามารถเรียนรู้วิธีที่เราสามารถแทรกโหนดในแผนผัง AVL การแทรกในแผนผัง AVL จะเหมือนกับ BST เราเพียงแค่ต้องทำขั้นตอนพิเศษที่เรียกว่าแผนผังสมดุลระหว่างการแทรกเมื่อใดก็ตามที่เราเลื่อนลงมา

สิ่งนี้ต้องคำนวณปัจจัยความสมดุลที่เราเคยเห็นมาก่อน และตามการกำหนดค่า เราจำเป็นต้องเรียกวิธีการหมุนที่เหมาะสม คำอธิบายเหล่านี้ค่อนข้างเข้าใจง่ายด้วยความช่วยเหลือจากคำอธิบายข้างต้น

เราสร้างเมธอดคลาสและฟังก์ชันตัวช่วยสำหรับการเรียกซ้ำอีกครั้ง -

ตัวอย่าง

insert(data) {
   let node = new this.Node(data);
   // Check if the tree is empty
   if (this.root === null) {
      // Insert as the first element
      this.root = node;
   } else {
      insertHelper(this, this.root, node);
   }
}

วิธีการช่วยเหลือ

function insertHelper(self, root, node) {
   if (root === null) {
      root = node;
   } else if (node.data < root.data) {
      // Go left!
      root.left = insertHelper(self, root.left, node);
      // Check for balance factor and perform appropriate rotation
      if (root.left !== null && self.getBalanceFactor(root) > 1) {
         if (node.data > root.left.data) {
            root = rotationLL(root);
         } else {
            root = rotationLR(root);
         }
      }
   } else if (node.data > root.data) {
      // Go Right! root.
      right = insertHelper(self, root.right, node);
      // Check for balance factor and perform appropriate rotation
      if (root.right !== null && self.getBalanceFactor(root) < -1) {
         if (node.data > root.right.data) {
            root = rotationRR(root);
         } else {
            root = rotationRL(root);
         }
      }
   }
   return root;
}

คุณสามารถทดสอบได้โดยใช้ −

ตัวอย่าง

let AVL = new AVLTree();

AVL.insert(10);
AVL.insert(15);
AVL.insert(5);
AVL.insert(50);
AVL.insert(3);
AVL.insert(7);
AVL.insert(12);

AVL.inOrder();

ผลลัพธ์

สิ่งนี้จะให้ผลลัพธ์ -