Chèn khóa vào cây trong JavaScript

Việc chèn đầu tiên trong một cây nhị phân mới tạo ra một nút tại root. Các chèn tiếp theo sẽ được chèn theo đặc tính BST: con trái nhỏ hơn cha, con phải lớn hơn cha.

Hãy xem cách triển khai thuật toán này trong code:

Ví dụ

insertIter(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;
    return;
  }
  let currNode = this.root;
  while (true) {
    if (data < currNode.data) {
      // Đặt giá trị ở đây vì đã đến nút lá
      if (currNode.left === null) {
        currNode.left = node;
        break;
      } else {
        currNode = currNode.left;
      }
    } else {
      // Đặt giá trị ở đây vì đã đến nút lá
      if (currNode.right === null) {
        currNode.right = node;
        break;
      } else {
        currNode = currNode.right;
      }
    }
  }
}

Hãy hiểu cách hàm này hoạt động. Trước tiên kiểm tra root có null không (cây rỗng), nếu có thì gán node mới làm root và xong. Nếu không, tạo biến currNode trỏ tới root. Sau đó kiểm tra data có nhỏ hơn currNode không, nếu có thì kiểm tra con trái có null không. Nếu null thì đặt data ở đó và thoát. Ngược lại tiếp tục lặp cho đến khi đến lá và đặt data đó.

Bạn có thể kiểm tra hàm này bằng cách sau:

Ví dụ

let BST = new BinarySearchTree();
BST.insertIter(10);
BST.insertIter(15);
BST.insertIter(5);
BST.insertIter(50);
BST.insertIter(3);
BST.insertIter(7);
BST.insertIter(12);

Chúng ta cũng có thể làm hàm này đệ quy. Cây bản chất là cấu trúc đệ quy và ta có thể tận dụng đặc tính này dễ dàng. Hãy xem phiên bản đệ quy của insert:

Ví dụ

insertRec(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 {
    insertRecHelper(this.root, node);
  }
}

Cần tạo hàm helper có thể đệ quy nhưng không muốn lộ ra thuộc tính class, nên hàm này sẽ nằm ngoài định nghĩa class.

Ví dụ

function insertRecHelper(root, node) {
  if (node.data < root.data) {
    // Đặt giá trị ở đây vì đã đến nút lá
    if (root.left === null) {
      root.left = node;
    } else {
      // Gọi đệ quy hàm này với cây con trái
      insertRecHelper(root.left, node);
    }
  } else {
    // Đặt giá trị ở đây vì đã đến nút lá
    if (root.right === null) {
      root.right = node;
    } else {
      // Gọi đệ quy hàm này với cây con phải
      insertRecHelper(root.right, node);
    }
  }
}

Bạn có thể kiểm tra bằng cách sau:

Ví dụ

let BST = new BinarySearchTree();
BST.insertRec(10);
BST.insertRec(15);
BST.insertRec(5);
BST.insertRec(50);
BST.insertRec(3);
BST.insertRec(7);
BST.insertRec(12);