이진 탐색 트리

이진 탐색 트리는 이진 트리의 일종으로 이진 트리에 대해서 이해가 선행되어야 한다.

이진 탐색 트리의 이해

트리는 탐색에 효율적인 것을 알 수 있다. 이진 트리의 경우 데이터가 10억개라고 해도 트리의 높이는 30을 넘지 않는다.

단 데이터가 무수히 많을 경우 찾는 데이터가 존재하는 길을 정확하게 찾기만 한다면 탐색에 아주 좋은 구조임을 알 수 있다.

이진 탐색 트리에는 이진 트리에 데이터 저장 규칙을 추가한 것이다. 데이터를 저장하는 규칙을 통해 특정 데이터의 위치를 찾을 수 있다.

이진 탐색 트리의 특징

• 이진 탐색 트리의 노드에 저장된 키(key)는 유일성을 갖는다.
• 루트 노드의 key가 왼쪽 서브 트리를 구성하는 어떤 노드의 key보다 크다
• 루트 노드의 key가 오른쪽 서브 트리를 구성하는 어떤 노드의 key보다 작다
• 왼쪽과 오른쪽 서브 트리도 이진 탐색 트리이다.

위 그림을 보면 루트 노드를 기준으로 왼쪽 서브 트리에 저장된 값들은 루트 노드보다 작고, 오른쪽 서브 트리에 저장된 값들은 루트 노드보다 크다.

이를 통해서 왼쪽 자식 노드의 키 < 부모 노드의 키 < 오른쪽 자식 노드의 키가 모든 노드가 동일하게 적용됨을 알 수 있다.

그럼 위 트리에서 숫자 23을 저장한다고 하면, 아래 일련의 과정을 통해서 저장 위치를 결정한다.

• 30 > 23 이므로 왼쪽으로 이동
• 22 < 23 이므로 오른쪽으로 이동
• 26 > 23 이므로 왼쪽으로 이동
• 비어있으므로 그 위치에 저장

최종적으로 숫자 23은 숫자 26의 자식 노드로 저장된다.

위 데이터 저장 과정과 동일하게 탐색 과정도 똑같은 방식으로 동작한다.