Chèn một nút trong Cây AVL Javascript

Chúng ta có thể tìm hiểu cách chèn một nút vào Cây AVL. Chèn trong cây AVL cũng giống như BST, chúng ta chỉ cần thực hiện thêm một bước gọi là cây cân bằng trong quá trình chèn bất cứ khi nào chúng ta di chuyển xuống cây.

Điều này yêu cầu tính toán hệ số cân bằng mà chúng ta đã thấy trước đó. Và theo các cấu hình, chúng ta cần gọi các phương thức xoay vòng thích hợp. Chúng khá trực quan với sự trợ giúp của giải thích ở trên.

Chúng tôi lại tạo một phương thức lớp và một hàm trợ giúp cho các cuộc gọi đệ quy -

Ví dụ

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

Phương thức trợ giúp

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

Bạn có thể kiểm tra điều này bằng cách sử dụng -

Ví dụ

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();

Đầu ra

Điều này sẽ cung cấp đầu ra -

3
5
7
10
12
15
50