자료구조 - 이진탐색트리

이진 트리에 데이터의 저장 규칙을 더해놓은 것이 이진 탐색 트리이다.

이진 탐색 트리가 되기 위한 조건을 나열해보면

 

· 루트 노드의 키가 왼쪽 서브 트리를 구성하는 어떠한 노드의 키보다 크다.

· 루트 노드의 키가 오른쪽 서브 트리를 구성하는 어떠한 노드의 키보다 작다.

· 왼쪽과 오른쪽 서브 트리도 이진 탐색 트리이다.

 

아래 그림은 위의 조건을 만족하는 트리의 예이다.

 

왼쪽 자식 노드의 키 < 부모 노드의 키 < 오른쪽 자식 노드의 키

 

와 같은 수식을 만족하고 있으며 위 그림의 이진 탐색 트리를 대상으로 숫자 10을 저장한다고 가정해보면

 

10<12 이므로 왼쪽 자식 노드로 이동

10>8 이므로 오른쪽 자식 노드로 이동

10>9 이므로 오른쪽 자식 노드로 이동

그 위치에 저장