[이산수학]이진 탐색 트리란?_예제포함

[이산수학]이진 탐색 트리의 정의(예제포함)

탐색(Search): 어떤 원소를 찾아가는 과정

키(key): 탐색에서 기준이 되는 값

 

■ 이진탐색트리(Binary Search Tree)란

노드가 가지는 데이터의 크기에 따라 노드의 위치를 탐색할 수 있는 트리

1. 트리에서 탐색되는 모든 원소는 서로 다른 유일키를 갖는다. 

2. 왼쪽 서브 트리에 있는 원소의 키들은 그 루트의 키보다 작다. 

3. 오른쪽 서브 트리에 있는 원소의 키들은 그 루트의 키보다 크다. 

 

루트 15를 기준으로 왼쪽 서브 트리는 15보다 작은 값들로 구성되고, 오른쪽 서브 트리는 15보다 큰 값들을 구성됩니다. 즉 15는 탐색되는 모든 원소들의 유일키가 됩니다. 왼쪽 서브 트리를 보면 12를 기준으로 12보다 작은 값은 왼쪽 버스 트리를 구성하고, 큰 값은 오른쪽 서브 트리를 구성합니다.

 

그래서 15보다 작은 값들은 12를 유일키로 하여 탐색할 수 있습니다. 이와 같이 이진 탐색 트리에서 탐색되는 모든 원소는 유일키를 하나씩 가집니다. 이 유일티를 기준으로 왼쪽 서브 트리에는 유일키보다 작은 값이, 오른쪽 서브 트리에는 유일키보다 큰 값이 구성됩니다. 

 

 

수학으로 이해하는 디지털 논리 이산수학 389p 참고

 

-----------------------------------

이산수학 총정리

목록 보러가기 

-----------------------------------