[자료구조] 이진 탐색 트리의 이해(1)

[자료구조] 이진 탐색 트리의 이해(1)

이진 탐색 트리는 말 그대로 탐색에 특화된 이진 트리이다.

앞서 이진 트리를 공부했기 때문에 이해와 구현이 어렵진 않겠지만,

기본적인 기능인 삽입, 삭제, 참조 중 삭제의 구현이 까다롭다.

왜 까다로운지, 어떻게 구현하는지는 차차 알아가 보도록하겠다.

이진 탐색 트리는 이진 트리의 확장 버전이라고 생각하면 된다.

이진 탐색 트리 = 이진 트리 + 데이터의 저장 규칙    ( 저장 규칙은 곧 탐색 규칙이라 말할 수 있다. )

위의 트리는 이진 탐색 트리를 나타낸 것이다.

루트 노드보다 작은 쪽은 왼쪽으로, 루트 노드보다 큰 쪽은 오른쪽으로라는 단순한 저장 규칙이다.

자세히 보면 꼭 루트노드가 아니더라도 어떠한 노드를 찍었을 때 왼쪽은 현재 노드보다 값이 작고 오른쪽은 크다.

정리하자면

1. 이진 탐색 트리의 저장된 키는 유일하다.

2. 루트 노드의 키 > 왼쪽 서브 트리의 루트 노드의 키

3. 루트 노드의 키 < 오른쪽 서브 트리의 루트 노드의 키

4. 왼쪽과 오른쪽 서브트리 또한 이진 탐색 트리이다.

지금까지의 내용은 이진 트리에서 간단한 규칙하나만 적용되었을 뿐이다.

하지만 이 간단한 규칙에 의해 탐색에 엄청난 효율을 가져올 수 있는데, 그 구현은 다음 포스팅에서 다루도록 하겠다.