-
이진 탐색 트리
탐색을 위한 이진 트리로 데이터의 크기에 따라 노드의 위치를 결정하며 다음과 같이 정의한다.
- 모든 원소는 서로 다른 유일한 키를 갖는다.
- 왼쪽 서브 트리에 있는 원소의 키들은 그 루트의 키보다 작다.
- 오른쪽 서브 트리에 있는 원소의 키들은 그 루트의 키보다 크다.
- 왼쪽 서브 트리와 오른쪽 서브 트리도 이진 탐색 트리다.
이진 탐색 트리의 탐색 연산
값을 찾을 때에는 루트에서 시작해서 찾으려는 값을 비교하여 진행한다.
- 노드의 값 = 찾으려는 값 탐색 성공
- 노드의 값 > 찾으려는 값 왼쪽 서브 트리로 이동하여 탐색 연산 수행
- 노드의 값 < 찾으려는 값 오른쪽 서브 트리로 이동하여 탐색 연산 수행