[자료구조] 이진 탐색 트리

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

정렬된 데이터를 효율적으로 저장하고 검색하기 위해 사용되는 이진 트리 자료 구조

---

노드 구조

각각의 노드는 3가지의 정보를 가진다.

• 값(Value) : 노드에 저장된 데이터
• 왼쪽 자식 (Left Child) : 현재 노드보다 작은 값을 가진 노드
• 오른쪽 자식 (Right Child) : 현재 노드보다 큰 값을 가진 노드

 

정렬 규칙

• 왼쪽 하위 트리에 있는 모든 노드의 값은 부모 노드의 값보다 작아야 한다.
• 오른쪽 하위 트리에 있는 모든 노드의 값은 부모 노드의 값보다 커야 한다.
• 왼쪽 및 오른쪽 하위 트리도 각각 이진 탐색 트리여야 한다.
• 각 노드의 최대 차수는 2이다.

 

중복된 값

일반적으로 이진 탐색 트리에서는 중복된 값을 허용하지 않는다. 

 

 

 

 

위의 이진 탐색 트리에서,

8의 값을 가진 왼쪽 하위 트리에 있는 값들(1, 3, 4, 6, 7)은 루트 노드인 8보다 모두 작고,

오른쪽 하위 트리에 있는 값들(10, 13, 14)은 모두 8보다 큰 값들이다.

 

---

삽입 과정

[8, 10, 3, 14, 6, 7, 1, 4, 13] 순서로 삽입해보자.

 

8 삽입

트리에 아무 노드도 없기 때문에 8이 삽입된다.

 

 

10 삽입

8보다 크기 때문에 오른쪽 하위 트리에 넣어준다.

 

 

3 삽입

8보다 작기 때문에 왼쪽 하위 트리에 넣어준다.

 

 

14 삽입

8보다 크기 때문에 오른쪽 하위 트리로 들어가고, 10보다 크기 때문에 10의 오른쪽 하위 트리에 넣어준다.

 

 

6 삽입

8보다 작기 때문에 8의 왼쪽 하위 트리로 넣어주고, 3보다 크기 때문에 3의 오른쪽 하위 트리로 넣어준다.

 

7 삽입

8보다 작기 때문에 8의 왼쪽 하위 트리로 넣어주고, 3보다 크기 때문에 3의 오른쪽 하위 트리로 넣어준다.

6보다 크기 때문에 6의 오른쪽 하위 트리로 넣어준다.

 

 

1 삽입

8보다 작기 때문에 8의 왼쪽 하위 트리로 넣어주고, 3보다 작기 때문에 3의 왼쪽 하위 트리로 넣어준다.

 

4 삽입

8보다 작기 때문에 8의 왼쪽 하위 트리로 넣어주고, 3보다 크기 때문에 3의 오른쪽 하위 트리로 넣어준다.

6보다 작기 때문에 6의 왼쪽 하위 트리로 넣어준다.

 

 

13 삽입

8보다 크기 때문에 오른쪽 하위 트리로 들어가고, 10보다 작기 때문에 10의 왼쪽 하위 트리에 넣어준다.

---

장점

• 데이터 검색, 삽입, 삭제 연산이 평균적으로 O(log⁡ n)에 수행 가능하여 효율적이다.
• 정렬된 데이터를 유지하면서 삽입 및 삭제가 가능하다.

 

단점

• 트리의 균형 상태에 따라 성능이 저하될 수 있다. => 한 쪽으로 치우쳐질 수도 있다.
• 한쪽으로 치우친 트리는 선형 구조가 되어 시간 복잡도가 O(n)으로 증가한다.

한 쪽으로 치우친 트리