이와 같은 순서로 만들어진 BST는 그림 2-12와 같은 형태로 구성되고, 이 경우 4를 찾는 단계가 크게 감소합니다.

▲ 그림 2-12 균형 잡힌 트리에서 원소 검색

그림 2-12의 트리는 편향되지 않은 상태이며, 이러한 트리를 균형이 잡혔다고 합니다. 이 상태의 트리에서는 4를 찾는 단계가 크게 감소합니다. 즉, find() 함수의 시간 복잡도는 단순히 원소 개수에만 영향을 받는 것이 아니라 트리의 형태에 대해서도 영향을 받습니다. 검색 단계를 면밀히 살펴보면 항상 트리의 아래쪽으로 한 단계씩 나아가는 것을 알 수 있습니다. 그리고 결국에는 더 이상 자식 노드가 없는 리프 노드(leaf node)에서 끝나게 됩니다. 여기서 찾고자 하는 원소를 발견하면 해당 노드를 반환하고, 없으면 NULL을 반환합니다. 따라서 검색에 필요한 단계의 수는 BST의 최대 레벨 수보다는 작습니다. BST의 레벨 수를 BST의 높이(height)라고 부르기 때문에 원소 검색의 실제 시간 복잡도는 O(높이)로 표현할 수 있습니다.