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

목차

• 이진 탐색 트리의 개념
• 이진 탐색 트리의 특징
• 트리 순회 방식
• 시간 복잡도
• 이진 탐색 트리의 장단점

 

이진 탐색 트리(Binary Search Tree)

이진 탐색 트리(Binary Search Tree, BST)는 트리 구조 중에서도 특정 규칙을 따르는 트리로,

데이터를 효율적으로 관리하고 검색할 수 있는 구조이다.

 

이진 탐색 트리의 개념

• 이진 탐색 트리는 각 노드가 최대 두 개의 자식 노드를 가지는 트리 구조로, 다음 규칙을 따른다.
  • 왼쪽 서브 트리는 해당 노드의 값보다 작은 값들을 가진다.
  • 오른쪽 서브 트리는 해당 노드의 값보다 큰 값들을 가진다.

이 규칙 덕분에 이진 탐색 트리는 빠른 데이터 검색, 삽입, 삭제 연산을 지원할 수 있다.

---

이진 탐색 트리의 특징

• 이진 트리에서 최소값과 최대값
  • 최소값: 이진 탐색 트리에서 최소값은 트리의 가장 왼쪽에 위치한 노드이다.
  • 최대값: 이진 탐색 트리에서 최대값은 트리의 가장 오른쪽에 위치한 노드이다.
• 노드의 후임자와 선임자
  • 후임자: 해당 노드보다 값이 큰 노드 중에서 가장 값이 작은 노드이다. 이는 다음에 올 수 있는 가장 가까운 값을 의미한다.
  • 선임자: 해당 노드보다 값이 작은 노드 중에서 가장 값이 큰 노드이다. 이는 이전에 올 수 있는 가장 가까운 값을 의미한다.
  • 이 둘은 트리에서 특정 노드의 이전이나 이후에 어떤 값이 존재하는지를 알아낼 때 사용된다.

 

---

이진 탐색 트리의 순회 방식

• 이진 탐색 트리를 순회하는 방법에는 크게 세 가지가 있다.
• 각 방법은 트리 구조를 방문하는 순서에 따라 다르게 구분된다.

 

1️⃣ 중위 순회 (Inorder Traversal): 중위 순회는 트리의 모든 노드를 오름차순으로 방문하는 방식이다.

1. 재귀적으로 왼쪽 서브 트리 순회
2. 현재 노드 방문 (ex. 출력)
3. 재귀적으로 오른쪽 서브 트리 순회

출력 순서: 3 ➔ 5 ➔ 10 ➔ 15 ➔ 17 ➔ 20 ➔ 30 ➔ 40 ➔ 50

 

2️⃣ 전위 순회 (Preorder Traversal): 전위 순회는 먼저 현재 노드를 방문한 후 서브 트리를 순회하는 방식

1. 현재 노드 방문 (ex. 출력)
2. 재귀적으로 왼쪽 서브 트리 순회
3. 재귀적으로 오른쪽 서브 트리 순회

출력 순서: 20 ➔ 5 ➔ 3 ➔ 15 ➔ 10 ➔ 17 ➔ 50 ➔ 30 ➔ 40

 

3️⃣ 후위 순회 (Postorder Traversal): 후위 순회는 먼저 서브 트리를 순회한 후 마지막에 현재 노드를 방문하는 방식

1. 재귀적으로 왼쪽 서브 트리 순회
2. 재귀적으로 오른쪽 서브 트리 순회
3. 현재 노드 방문 (ex. 출력)

출력 순서: 3 ➔ 10 ➔ 17 ➔ 15 ➔ 5 ➔ 40 ➔ 30 ➔ 50 ➔ 20

---

이진 탐색 트리의 시간 복잡도

탐색, 삽입, 삭제 연산의 평균 시간 복잡도

• 이진 탐색 트리의 높이가 균형을 잘 유지하고 있을 경우, 탐색, 삽입, 삭제 모두 평균적으로 트리의 높이에 비례한 시간 복잡도를 가진다.
• 트리의 높이가 log n이므로 평균적으로 O(log n)의 시간이 걸린다.

최악의 경우 시간 복잡도

• 트리가 한쪽으로 치우쳐(편향된 트리) 높이가 n에 가까워지면, 리스트와 비슷한 구조가 되어 탐색, 삽입, 삭제 연산에서O(n)의 시간이 소요될 수 있다.

---

이진 탐색 트리의 장단점

장점

1. 삽입과 삭제가 유연:
   • 이진 탐색 트리는 값의 크기에 따라 좌우로 분리되기 때문에 삽입과 삭제가 효율적으로 이루어질 수 있다.
2. 정렬된 데이터 출력:
   • 중위 순회(Inorder Traversal)를 통해 트리의 데이터를 오름차순으로 정렬된 형태로 출력할 수 있다.
3. 탐색 성능이 좋음:
   • 트리 구조 덕분에 크기에 따른 탐색이 가능하며, 적절하게 균형 잡힌 트리에서는 매우 빠른 탐색 성능을 기대할 수 있다.

단점

1. 편향된 트리의 문제:
   • 만약 트리가 한쪽으로 치우치면, 이진 탐색 트리는 선형 리스트처럼 동작하게 되어 최악의 경우 시간 복잡도가 O(n)까지 증가한다.
2. 균형을 유지하는 트리 필요:
   • 균형 잡힌 이진 탐색 트리(Balanced Binary Search Tree)가 아니면 성능이 급격히 떨어질 수 있다.
   • 이를 해결하기 위해 AVL 트리나 레드-블랙 트리와 같은 자체 균형 트리(Self-balancing Tree)가 자주 사용된다.

---