이진 탐색 트리(Binary Search Tree), 이진 트리 구조 도식도, 이진 검색 트리 저장 원리

 

 

이진 탐색 트리(Binary Search Tree)

모든 노드는 최대 두 개의 자식노드를 가질 수 있습니다.

바이너리 서치 트리는 어느 노드에서든 그 노드의 왼쪽 부분 트리의 모든 원소는 그 노드의 값보다 작거나 같고, 오른쪽 부분 트리에는 해당 값보다 큰 값이 저장되어 있습니다.

정렬, 검색, 범위 검색(range search)에 높은 성능을 보여주는 자료구조입니다.

 

 

 

 

8, 5, 20의 순서로 저장된 이진 트리 구조 도식도

간단하게 도식화한 이진 트리 구조

 

실제로 저장되는 이진 트리 구조

 

 

 

 

이진 검색 트리 원리

첫번째로 저장되는 값은 root노드가 됩니다.

두번째 저장되는 값은 트리의 root부터 시작해서 값의 크기를 비교해서 트리를 따라 내려가게 됩니다. 비교해서 작은 값은 왼쪽에 큰 값은 오른쪽에 저장하게 됩니다.

모두 값이 트리에 저장되게되면 가장 왼쪽에 있는 노드는 제일 작은 값을 가지고 가장 오른쪽의 노드는 제일 큰 값을 가지게 됩니다.

 

 

8, 5, 20, 2, 6의 순서로 값 저장하기

8을 트리의 ‘루트’, 즉 맨 위 머리부분으로 배치했습니다. 8의 두 자식 노드는 5와 20이고, 5는 2와 6이라는 두 자식 노드를 갖습니다.

트리에서 루트 노드에는 8의 값이 저장돼 있고, 왼쪽 부분 트리의 모든 값은 5, 2, 6으로 8보다 작고, 20은 8보다 큽니다.

 

 

 

단계	도식도
8 저장
5 저장
20 저장
2 저장
6 저장