การค้นหาข้อมูลใน Binary Search Tree ด้วย JavaScript

เราจะใช้ property ของ BST ในการค้นหา element มาดู iterative implementation ก่อน:

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

searchIter(data) {
  let currNode = this.root;
  while (currNode !== null) {
    if (currNode.data === data) {
      // เจอ element!
      return true;
    } else if (data < currNode.data) {
      // ไปทางซ้าย เพราะ data น้อยกว่า parent
      currNode = currNode.left;
    } else {
      // ไปทางขวา เพราะ data มากกว่า parent
      currNode = currNode.right;
    }
  }
  return false;
}

ในฟังก์ชันนี้ เราเริ่มจาก root เป็น currNode และเปรียบเทียบ data กับ currNode.data ถ้าเจอคืน true ไม่เช่นนั้นวนซ้ำไปซ้ายหรือขวาตามความสัมพันธ์จนกว่าจะถึง leaf หรือเจอ element

ทดสอบการทำงานได้ดังนี้:

ตัวอย่างการใช้งาน

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

ผลลัพธ์

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

false
true
true
false
false

คล้ายกับ insert function search ก็สามารถทำแบบ recursive ได้เช่นกัน:

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

เราต้องสร้าง helper function ที่ recurse แต่ไม่อยาก expose เป็น property ของคลาส จึงสร้างนอก class definition:

ตัวอย่าง

function searchRecHelper(data, root) {
  if (root === null) {
    // ถึง leaf แล้วแต่ยังไม่เจอ
    return false;
  }
  if (data < root.data) {
    return searchRecHelper(data, root.left);
  } else if (data > root.data) {
    return searchRecHelper(data, root.right);
  }
  // หมายถึงเจอ element
  return true;
}

ทดสอบการทำงานได้ดังนี้:

ตัวอย่างการใช้งาน

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

ผลลัพธ์

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

false
true
true
false
false