BST에서 원소 검색

이진 검색 트리에서 원소 검색, 삽입, 삭제 방법에 대해 알아보겠습니다. 중복되지 않는 양수를 원소로 갖는 BST가 그림 2-5와 같이 구성되어 있다고 가정하겠습니다.

▲ 그림 2-5 이진 검색 트리에서 원소 검색

그림 2-5 트리에서 숫자 7을 검색하는 방법에 대해 알아보겠습니다. 그림 2-5에서 화살표로 표현된 것처럼 각 노드의 숫자와 7을 비교하여 어느 하위 노드로 이동할지를 결정해야 합니다. 이진 검색 트리에서 현재 노드보다 왼쪽 노드는 값이 작고, 오른쪽 노드는 값이 크다는 점을 기억해야 합니다.

먼저 루트 노드와 숫자 7을 비교합니다. 루트 노드 값은 12이고, 7은 12보다 작기 때문에 왼쪽 자식 노드로 이동해야 합니다. 왜냐하면 12보다 작은 값을 갖는 노드는 모두 루트 노드의 왼쪽에 있기 때문입니다. 이후 자식 노드에서도 그 값이 7보다 작으면 왼쪽, 7보다 크면 오른쪽 자식 노드로 이동합니다. 결국 그림 2-5에서는 4 노드에서 오른쪽으로 이동하여 숫자 7을 찾을 수 있습니다.

BST에서 원소를 검색할 때는 트리의 모든 원소를 방문하지 않아도 됩니다. 현재 노드가 찾고자 하는 노드가 아닐 때마다 검색 범위가 반으로 줄어듭니다. 이러한 특징은 선형 자료 구조에 대한 이진 검색에서도 유사하게 나타나며, 이에 대해서는 4장 분할 정복에서 자세히 다루겠습니다.