Chèn nút vào AVL Tree bằng JavaScript

Chúng ta có thể học cách chèn một nút vào AVL Tree. Việc chèn trong AVL tree giống như BST, chỉ cần thực hiện thêm một bước gọi là cân bằng cây (balance tree) trong lúc chèn mỗi khi di chuyển xuống cây.

Điều này yêu cầu tính toán balance factor (hệ số cân bằng) như đã thấy trước đó. Và tùy theo cấu hình, cần gọi các phương thức xoay (rotation) phù hợp. Những thứ này khá trực quan với sự giải thích ở trên.

Chúng ta lại tạo một phương thức class và hàm helper cho gọi đệ quy:

Ví dụ

insert(data) {
  let node = new this.Node(data);
  // Kiểm tra nếu cây rỗng
  if (this.root === null) {
    // Chèn làm phần tử đầu tiên
    this.root = node;
  } else {
    insertHelper(this, this.root, node);
  }
}

Phương thức helper

function insertHelper(self, root, node) {
  if (root === null) {
    root = node;
  } else if (node.data < root.data) {
    // Đi trái!
    root.left = insertHelper(self, root.left, node);
    // Kiểm tra balance factor và thực hiện xoay phù hợp
    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) {
    // Đi phải!
    root.right = insertHelper(self, root.right, node);
    // Kiểm tra balance factor và thực hiện xoay phù hợp
    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 bằng cách sau:

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

Kết quả

Điều này sẽ cho ra kết quả:

3 5 7 10 12 15 50