이진 탐색 트리

이진 탐색 트리

트리 자료구조 중에서 이진 탐색이 동작할 수 있도록 고안된, 효율적인 탐색이 가능한 자료구조이다. 이진 탐색 트리는 다음과 같은 특징을 가진다.

• 부모 노드보다 왼쪽 자식 노드가 작다.
• 부모 노드보다 오른쪽 자식 노드가 크다.

 

실제 코딩 테스트에서 이진 탐색 트리 자료구조를 구현하도록 요구하는 문제는 출제 빈도가 낮다. 이진 탐색 트리가 이미 구현되어 있다고 가정하고 이진 탐색 트리에서 탐색하는 과정만 알아도 충분하다.

 

탐색은 루트 노드에서부터 자식노드로 내려가면서 찾는 원소값과 비교해가면 된다.