(cs)이진 탐색 트리 (Binary Search Tree, BST)

이진 탐색 트리 (Binary Search Tree, BST)

1. 개념

이진 탐색 트리(Binary Search Tree, BST)는
이진 트리의 일종으로, 다음의 조건을 만족하는 트리 구조를 말한다.

• 모든 노드의 왼쪽 서브트리: 현재 노드의 값보다 작은 값을 가진 노드들로 구성
• 모든 노드의 오른쪽 서브트리: 현재 노드의 값보다 큰 값을 가진 노드들로 구성

이러한 규칙 덕분에 탐색(search), 삽입(insert), **삭제(delete)**를 효율적으로 수행할 수 있다.

 

 

사진 춢처 - 유튜브 쉬운코드

---

2. 이진 탐색 트리 순회 방법 (Traversal)

트리의 모든 노드를 방문하는 방법을 **트리 순회(Tree Traversal)**라고 한다.
이진 탐색 트리에서는 주로 다음 세 가지 순회 방법을 사용한다.

(1) 중위 순회 (In-order Traversal)

"왼쪽 → 현재 → 오른쪽" 순서로 방문

• 왼쪽 서브트리를 재귀적으로 순회
• 현재 노드를 방문
• 오른쪽 서브트리를 재귀적으로 순회

특징:
BST에서 중위 순회를 수행하면 노드 값이 오름차순으로 출력된다.

(2) 전위 순회 (Pre-order Traversal)

"현재 → 왼쪽 → 오른쪽" 순서로 방문

• 현재 노드를 방문
• 왼쪽 서브트리를 재귀적으로 순회
• 오른쪽 서브트리를 재귀적으로 순회

특징:
트리 구조를 복원하거나 저장할 때 주로 사용한다.

(3) 후위 순회 (Post-order Traversal)

"왼쪽 → 오른쪽 → 현재" 순서로 방문

• 왼쪽 서브트리를 재귀적으로 순회
• 오른쪽 서브트리를 재귀적으로 순회
• 현재 노드를 방문

특징:
메모리 해제(삭제) 작업 등 하위 노드를 먼저 처리해야 할 때 사용한다.

---

3. 노드의 후임자(석세서, Successor)와 선임자(프레드세서, Predecessor)

(1) 후임자(Successor)

• 현재 노드보다 값이 큰 노드들 중 가장 작은 노드를 의미한다.
• 보통 오른쪽 서브트리의 최솟값이 후임자가 된다.

(2) 선임자(Predecessor)

• 현재 노드보다 값이 작은 노드들 중 가장 큰 노드를 의미한다.
• 보통 왼쪽 서브트리의 최댓값이 선임자가 된다.

---

4. 삽입, 삭제, 검색 연산

BST의 규칙(왼쪽은 작고 오른쪽은 크다)을 기반으로,
다음과 같은 기본 연산을 수행할 수 있다.

(1) 삽입 (Insertion)

• 루트 노드에서부터 시작하여,
• 삽입하려는 값이 현재 노드보다 작으면 왼쪽으로, 크면 오른쪽으로 이동
• 비어 있는 자리에 새로운 노드를 삽입한다.

시간복잡도: 평균 O(log N), 최악 O(N)

(2) 검색 (Search)

• 루트 노드에서부터 시작하여,
• 찾고자 하는 값이 현재 노드보다 작으면 왼쪽 서브트리로,
• 크면 오른쪽 서브트리로 이동하며 탐색한다.

시간복잡도: 평균 O(log N), 최악 O(N)

(3) 삭제 (Deletion)

삭제할 노드의 형태에 따라 세 가지 경우로 나뉜다.

• 자식 노드가 없는 경우 (Leaf Node)
  • 해당 노드를 단순히 삭제한다.
  • 부모 노드의 레퍼런스를 null로 설정.
• 자식 노드가 하나인 경우
  • 삭제할 노드를 건너뛰고 자식 노드를 부모 노드와 연결한다.
• 자식 노드가 둘인 경우
  • 삭제할 노드를 대체할 값을 찾는다.
    • 보통 **오른쪽 서브트리에서 가장 작은 값(후임자)**을 찾는다.
  • 삭제할 노드의 값을 후임자의 값으로 교체한 후,
  • 후임자 노드를 삭제한다. (이때 후임자는 자식이 하나 이하라 삭제가 쉽다.)

특수 케이스: 루트 노드를 삭제할 경우에도 동일한 원칙을 적용한다.

---

5. 이진 탐색 트리의 장단점

장점

1. 삽입과 삭제가 유연하다
   • 레퍼런스(포인터)만 재조정하면 되므로 구조적 수정이 쉽다.
2. 탐색이 빠르다 (평균 O(logN))
   • 값의 크기에 따라 왼쪽/오른쪽으로 반씩 좁혀가므로 효율적이다.
3. 값의 정렬된 순서에 따라 순회 가능
   • 중위 순회를 이용하면 노드들이 오름차순으로 출력된다.

단점

1. 최악의 경우 성능 저하
   • 삽입 순서가 잘못되면 트리가 한쪽으로 편향(Degenerate)될 수 있다.
   • 이 경우 트리가 사실상 **연결 리스트(Linked List)**처럼 변하여 탐색, 삽입, 삭제 모두 O(N)이 된다.
2. 균형 유지 필요
   • 성능 저하를 막기 위해 **자체적으로 균형을 잡는 이진 탐색 트리(AVL 트리, Red-Black 트리 등)**를 사용하기도 한다.

---

최종 정리

이진 탐색 트리는 간단하면서도 강력한 자료구조로,
정렬된 데이터를 빠르게 탐색하거나 삽입/삭제할 수 있는 기반을 제공한다.
그러나 트리의 균형이 깨질 경우 성능이 급격히 저하될 수 있기 때문에,
스스로 균형을 맞추는 트리(예: AVL, Red-Black 트리)와의 차이점도 이해하는 것이 중요하다.