การเพิ่ม Node ใน AVL Tree ด้วย JavaScript

เราสามารถเรียนรู้วิธีเพิ่ม node ใน AVL Tree การ insert ใน AVL trees เหมือน BST เพียงแค่ต้องทำขั้นตอนเพิ่มเติมคือ balance tree ระหว่าง insert เมื่อเราเคลื่อนลงต้นไม้

สิ่งนี้ต้องคำนวณ balance factor ที่เราเคยเห็น และตาม configuration เราต้องเรียก rotation methods ที่เหมาะสม ซึ่งเข้าใจง่ายด้วยคำอธิบายข้างต้น

เราสร้าง class method และ helper function สำหรับ recursive calls อีกครั้ง:

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

insert(data) {
  let node = new this.Node(data);
  // ตรวจสอบว่าต้นไม้ว่างหรือไม่
  if (this.root === null) {
    // ใส่เป็น element แรก
    this.root = node;
  } else {
    insertHelper(this, this.root, node);
  }
}

Helper method

function insertHelper(self, root, node) {
  if (root === null) {
    root = node;
  } else if (node.data < root.data) {
    // ไปซ้าย!
    root.left = insertHelper(self, root.left, node);
    // เช็ค balance factor และทำ 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) {
    // ไปขวา!
    root.right = insertHelper(self, root.right, node);
    // เช็ค balance factor และทำ 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();

ผลลัพธ์

จะได้ผลลัพธ์ดังนี้:

3 5 7 10 12 15 50