binary search tree (이진 탐색 트리)

- 이진 트리에 4가지 조건을 더 갖는 트리구조

- 데이터의 삽입, 삭제, 탐색 등이 자주 발생하는 경우에 효율적인 구조다.

- 루트를 기준으로 루트보다 작은 값은 왼쪽, 큰 값은 오른쪽으로 정해져 있다.

​

4가지 조건

1. 모든 노드는 다른 값을 갖는다.

2. 왼쪽 서브 트리의 데이터 값은 부모 노드의 데이터 값보다 작은 값을 갖는다.

3. 오른쪽 서브 트리의 데이터 값은 부모 노드의 데이터 값보다 큰 값을 갖는다.

4. 왼쪽, 오른쪽 서브트리도 이진 탐색 트리다.

​

아래와 같은 이진 트리에서 12를 검색하고자 할 때

(출처 네이버 백과)

​

1. 루트 노드의 값(8)보다 찾으려는 값(12)이 클 경우 오른쪽 서브트리에서 탐색한다.

2. 다음 루트(10)의 값보다 찾으려는 값(12)이 클 경우 오른쪽 서브트리에서 탐색한다.

3. 다음 루트(14)의 값이 찾으려는 값(12)보다 클 경우 왼쬑 서브트리에서 탐색한다.

4. 12 검색 완료

​

참고 출처

 

다람쥐와 포동포동이

RememberCook 9월 28일 정식 출시!