Tìm kiếm giá trị trong Binary Search Tree JavaScript

Chúng ta sẽ dùng đặc tính của BST để tìm kiếm phần tử. Hãy xem trước triển khai lặp:

Ví dụ

searchIter(data) {
  let currNode = this.root;
  while (currNode !== null) {
    if (currNode.data === data) {
      // Tìm thấy phần tử!
      return true;
    } else if (data < currNode.data) {
      // Đi sang trái vì data nhỏ hơn cha
      currNode = currNode.left;
    } else {
      // Đi sang phải vì data lớn hơn cha
      currNode = currNode.right;
    }
  }
  return false;
}

Trong hàm này, bắt đầu từ root làm currNode và so sánh data với data của currNode. Nếu tìm thấy khớp thì trả về true,否则 tiếp tục lặp sang trái hoặc phải tùy theo quan hệ của data với data của currNode cho đến khi gặp lá hoặc tìm thấy phần tử.

Bạn có thể kiểm tra 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);
console.log(BST.searchIter(2));
console.log(BST.searchIter(12));
console.log(BST.searchIter(50));
console.log(BST.searchIter(-22));
console.log(BST.searchIter(200));

Kết quả

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

false true true false false

Tương tự như hàm insert, tìm kiếm cũng có thể triển khai đệ quy.

searchRec(data) {
  return searchRecHelper(data, this.root);
}

Lại cần tạo hàm helper không muốn làm thuộc tính của class, nên tạo hàm này bên ngoài định nghĩa class:

Ví dụ

function searchRecHelper(data, root) {
  if (root === null) {
    // Đã đến lá nhưng không tìm thấy.
    return false;
  }
  if (data < root.data) {
    return searchRecHelper(data, root.left);
  } else if (data > root.data) {
    return searchRecHelper(data, root.right);
  }
  // Nghĩa là phần tử đã tìm thấy
  return true;
}

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);
console.log(BST.searchRec(2));
console.log(BST.searchRec(12));
console.log(BST.searchRec(50));
console.log(BST.searchRec(-22));
console.log(BST.searchRec(200));

Kết quả

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

false true true false false