이진검색트리(BST)

이진검색트리(BST) 정의

 1. 이진 탐색(binary search)와 연결 리스트(Linked list)를 결합한 자료구조이다. 

  * 이진 탐색: 탐색 범위를 두 부분으로 분할 하면서 찾는 자료구조, 삽입 및 삭제는 불가능, 보통 배열로 구성

 

 2. 이진 탐색의 효율적인 탐색능력을 유지하면서, 자료 삽입(Insert)과 삭제(Delete)를 가능하게끔 고안되었다. 

이진검색트리 특징

 1. 트리의 모양은 상관 없으며 이진트리여야 한다. 

 2. 부모노드의 값을 중심으로 왼쪽 자식 트리의 값은 작고, 오른쪽 자식 트리의 값은 커야한다. 

 3. 중복된 노드는 없어야 한다. 

 4. 이진 탐색트리는 중위 순회를 통해 순회를 진행한다. -> 이진 검색트리 내에 있는 모든 값들을 정렬된 순서대로 읽을 수 있다. 

- 중위 순회 -

중위 순회 결과: 1, 3, 5, 7, 8, 10

순회 방법 (트리 루트를 기준)

 1. 전위 순회: 왼쪽 -> 루트 -> 오른쪽

 2. 중위 순회: 루트 -> 왼쪽 -> 오른쪽

 3. 후위 순회: 오른쪽 -> 왼쪽 -> 루트

예시 

 1. 검색(Search)

- 이진탐색트리 검색 -

2. 삽입(Insert)

- 이진검색트리 삽입 -

이진검색트리의 단점 

 1. 편향된 트리(트리의 Branch 가 한쪽으로만 뻗는 경우)로 변형될 확률이 존재한다. -> 이러한 단점을 보완하기 위해서 레드블랙 트리, AVL트리, Spray트리, BB 트리 등 구현되었다. 

---

< 참고자료 >

 

[도서] 자료구조  - 정광식 지음-

 

<Data structures> chapter 9,  이진탐색트리(BST) end

 

---