search : 이진탐색트리(Binary Search Tree, BST)

이진탐색트리(Binary Search Tree, BST)에서 search 메소드를 구현하는 것은 insert 메소드와 유사한 방식으로 진행할 수 있습니다. search 메소드는 트리 내에서 특정 데이터를 찾아 그 데이터가 존재하는지 여부를 반환하거나, 해당 데이터를 포함하는 노드를 반환합니다. 이 메소드 역시 재귀적인 방법을 사용하여 구현할 수 있습니다.

아래는 BST 클래스에 search 메소드를 추가한 예시입니다. 이 메소드는 주어진 데이터와 일치하는 노드를 찾으면 그 노드를 반환하고, 데이터를 찾지 못하면 **null**을 반환합니다.

class Node {
  constructor(data, left = null, right = null) {
    this.data = data;
    this.left = left;
    this.right = right;
  }
}

class BST {
  constructor() {
    this.root = null;
  }

  // insert 메소드는 이전 예시와 동일하게 유지됩니다.
  // ...

  search(data) {
    const searchTree = function(node) {
      if (node === null) {
        return null; // 데이터를 찾지 못하고 트리의 끝에 도달함
      }
      if (data < node.data) {
        return searchTree(node.left); // 왼쪽 서브트리에서 계속 검색
      } else if (data > node.data) {
        return searchTree(node.right); // 오른쪽 서브트리에서 계속 검색
      } else {
        return node; // 데이터를 찾음, 해당 노드 반환
      }
    };

    return searchTree(this.root);
  }
}

이 구현에서 search 메소드는 루트 노드에서 시작하여 주어진 데이터를 트리 내에서 찾습니다. 데이터가 현재 노드의 데이터보다 작으면 왼쪽 자식 노드로 이동하고, 데이터가 현재 노드의 데이터보다 크면 오른쪽 자식 노드로 이동합니다. 이 과정을 데이터를 찾거나 더 이상 탐색할 노드가 없을 때까지 반복합니다.

이진탐색트리의 특성 상, 각 단계에서 탐색 범위를 절반으로 줄일 수 있기 때문에, 검색 연산은 평균적으로 효율적입니다. 하지만, 트리가 균형을 잃어 한쪽으로 치우친 경우(예: 모든 노드가 오른쪽에만 있는 경우), 최악의 성능은 선형 검색과 유사할 수 있습니다. 이러한 문제를 해결하기 위해 AVL 트리나 레드-블랙 트리와 같은 자가 균형 이진 탐색 트리를 사용할 수 있습니다.