Javascript 이진 검색 트리에서 값 검색

BST의 속성을 사용하여 요소를 조회할 것입니다. 먼저 검색의 반복적 구현을 ​​살펴보겠습니다.

예시

searchIter(data) {
   let currNode = this.root;
   while (currNode !== null) {
      if (currNode.data === data) {
         // Found the element!
         return true;
      } else if (data < currNode.data) {
         // Go Left as data is smaller than parent
         currNode = currNode.left;
      } else {
         // Go right as data is greater than parent
         currNode = currNode.right;
      }
   }
   return false;
}

이 함수에서는 루트를 currNode로 시작하여 currNode의 데이터와 비교하여 데이터를 확인합니다. 일치하는 항목을 찾으면 true를 반환하고, 그렇지 않으면 리프에 도달하거나 요소를 찾을 때까지 currNode의 데이터에 대한 데이터의 관계에 따라 왼쪽 또는 오른쪽으로 계속 반복합니다.

다음을 사용하여 테스트할 수 있습니다.

예시

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

삽입 기능과 유사하게 검색도 재귀적으로 구현될 수 있습니다.

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

다시 말하지만, 우리는 클래스의 일부로 원하지 않는 도우미 함수를 생성해야 할 것이므로 클래스 정의 외부에서 이 함수를 생성할 것입니다 -

예시

function searchRecHelper(data, root) {
   if (root === null) {
      // Reached leaf but didn't find it.
      return false;
   }
   if (data < root.data) {
      return searchRecHelper(data, root.left);
   } else if (data > root.data) {
      return searchRecHelper(data, root.right);
   }
   // This means element is found
   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