[자료 구조] 이진 탐색 트리 Binary search Tree, BST

출처

ChatGPT

---

이진 탐색 트리는 이진 트리의 한 종류로, 각 노드에 저장된 값이 특정 규칙을 따르며 정렬된 상태를 유지하는 트리이다. 이 규칙 덕분에 빠른 검색, 삽입, 삭제 연산이 가능하여, 데이터의 효율적인 관리를 제공한다.

• 관련 글 -> [자료 구조] 이진 트리 Binary Tree
• 관련 글 -> [빈 구멍 채우기] - [자료구조] 트리 Tree

 

1. 구조

이진 탐색 트리의 각 노드는 최대 두 개의 자식 노드를 가질 수 있다. 각 노드는 트리의 특정 규칙에 따라 배치된다.

규칙

1. 왼쪽 자식 노드 : 부모 노드보다 작은 값

2. 오른쪽 자식 노드 : 부모 노드보다 큰 값

 

이 규칙으로 인해 트리의 어느 지점에서도 왼쪽 서브트리는 부모다 작은 값들로 이루어져 있고, 오른쪽 서브트리는 부모보다 큰 값들로 이루어져 있어, 탐색이 매우 빠르게 이루어질 수 있다.

 

예시

        50
       /  \
     30    70
    /  \   /  \
   20  40 60  80

 

• 왼쪽 자식 노드 : 부모 노드보다 작은 값(예: 30은 50보다 작다)
• 오른쪽 자식 노드 : 부모 노드보다 큰 값(예: 70은 50보다 크다)

 

2. 연산 및 시간 복잡도

BST의 주요 연산은 탐색, 삽입, 삭제이다. 이들은 모두 트리의 높이에 따라 달라지며, 최선의 경우와 최악의 경우가 나뉘어 있다.

(1) 탐색 Search

트리의 루트에서 시작해, 찾고자 하는 값이 현재 노드보다 작으면 왼쪽으로, 크면 오른족으로 이동한다.

이 과정을 반복해 값이 있는 노드를 찾는다.

시간 복잡도

평균 : O(log n)

트리가 균형을 유지할 경우, 트리의 높이는 log n에 비례하므로, 탐색은 log n 단계에서 끝난다.

최악의 경우 : O(n)

트리가 한 쪽으로 치우쳐질 경우(즉, 스큐 트리(Skewed Tree)), 리스트와 같은 구조가 되어 탐색에 최대 n 단계를 거칠 수 있다.

• 관련 글 ->  [자료 구조] 스큐 트리 Skewed Tree

 

예시

        50
       /  \
     30    70
    /  \   /  \
   20  40 60  80

 

해당 트리에서 40을 찾으려면, 50 -> 30 -> 40 순서로 탐색한다.

 

(2) 삽입 Insertion

삽입할 값을 탐색해 적절한 위치(왼쪽 또는 오른쪽)에 삽입한다.

새로운 노드를 항상 리프 노드로 삽입된다.

시간복잡도

평균 : O(log n)

트리가 균형을 이루고 있다면, 삽입 과정도 log n 단계에서 끝난다.

최악의 경우 : O(n)

트리가 한 쪽으로 치우쳐 있을 때, 리스트와 같은 구조가 되어 삽입에 n 단계를 거칠 수 있다.

 

예시

        50
       /  \
     30    70
    /  \   /  \
   20  40 60  80
      /
   (+35)

 

해당 트리에  35를 삽입하려면, 50 -> 30 -> 40까지 탐색해 40의 왼쪽 자식으로 35를 삽입한다.

 

(3) 삭제 Deletion

삭제할 노드를 찾고, 세 가지 경우에 따라 삭제를 처리한다.

1. 자식이 없는 경우 : 단순히 삭제

2. 자식이 하나일 경우 : 자식 노드를 부모와 연결한 뒤 삭제

3. 자식이 두 개인 경우 :대체 노드를 찾는다. 대체할 노드는 두 가지 방법 중에 하나를 사용한다.

• 오른쪽 서브트리에서 가장 작은 값(후속자): 오른쪽 서브트리에서 가장 작은 값을 찾아서 대체한다. 
• 왼쪽 서브트리에서 가장 큰 값(전임자) : 왼쪽 서브트리에서 가장 큰 값을 찾아 대체한다.

시간 복잡도

평균 : O(log n)

트리가 균형을 유지하고 있으면 삭제도 log n의 시간 복잡도를 가진다.

최악의 경우 : O(n)

트리가 한 쪽으로 치우쳐 있을 때, 삭제에 최대 n 단계가 걸릴 수 있다.

 

예시

        50
       /  \
     30    70
    /  \   / \
   20  40 60  80

 

해당 트리에서 50을 삭제하려고 한다. 이 경우, 오른쪽 서브트리에서 가장 작은 값 또는 왼쪽 서브트리에서 가장 큰 값을 찾아서 대체한다.

 

1. 오른쪽 서브트리에서 가장 작은 값(후속자)를 찾는 경우

오른쪽 서브트리970, 60, 80)에섯 가장 작은 값은 60이다.

따라서 60을 삭제할 50 노트의 위치로 가져오고, 기존 리프 노드인 60 노드는 삭제한다.

최종 트리는 다음과 같다

        60
       /  \
     30    70
    /  \     \
   20  40    80

 

2. 왼쪽 서브트리에서 가장 큰 값(전임자)를 찾는 경우

왼쪽 서브트리에서 가장 큰 값은 40이다.

40을 삭제할 50 노드의 위치로 가져오고, 기존 리프 노드인 40 노드는 왼쪽 서브 트리에서 삭제한다.

최종 트리는 다음과 같다.

        40
       /  \
     30    70
    /      / \
   20     60  80

 

3. BST의 장점과 단점

장점

빠른 탐색

잘 균형잡힌 BST는 탐색, 삽입, 삭제 연산에서 O(log n)의 시간 복잡도를 가진다.

정렬된 순서로 저장 

BST는 중위 순회(In-order Traversal)를 하면 모든 요소를 정렬된 순서로 얻을 수 있다.

 

단점

트리의 균형 문제

일반적인 BST는 삽입 순서에 따라 트리가 한쪽으로 치우쳐질 수 있다. 이러한 경우 성능이 O(n)으로 저하된다.

이를 해결하기 위해 자가 균형 이진 탐색 트리(레드-블랙 트리, AVL 트리)를 사용한다.

• 관련 글 -> [자료 구조] 레드-블랙 트리 Red-Black Tree

 

4. BST의 순회 Traversal

BST에서 노드를 순회하는 방법은 크게 세 가지이다.

1. 전위 순회 Pre-order Traversal

루트 -> 왼쪽 -> 오른쪽 순서로 방문

2. 중위 순회 In-order Traversal

왼쪽 -> 루트 -> 오른쪽 순서로 방문

BST에서 중위 순회는 정렬된 순서를 반환한다.

3. 후위 순회 Post-order Traversal

왼쪽 -> 오른쪽 -> 루트 순서로 방문

 

중위 순회의 예시

        50
       /  \
     30    70
    /  \   /  \
   20  40 60  80

 

중위 순회 결과 : 20, 30, 40, 50, 60, 70, 80

 

5. BST의 최악의 경우

이진 탐색 트리가 한 쪽으로 치우쳐지는 경우, 트리는 사실 상 연결 리스트와 같은 형태가 된다. 이 경우 탐색, 삽입, 삭제의 시간 복잡도는 O(n)까지 나빠진다.

 

치우쳐진 트리(스튜 트리)의 예

  10
    \
     20
       \
        30
          \
           40

 

이 경우 각 연산에서 모든 노드를 거쳐야 하므로, 성능이 저하된다.

 

6. 자가 균형 이진 탐색 트리와의 차이점

일반적인 이진 탐색 트리는 삽입 순서에 따라 트리가 한 쪽으로 치우칠 수 있기 때문에, 자가 균형 이진 탐색 트리(Self-Balancing Binary Search Tree)가 필요하다. 자가 균형 트리(예 - 레드-블랙 트리, AVL 트리)는 삽입, 삭제 후에도 트리가 균형을 유지하여, 모든 연산에서 O(log n)의 성능을 보장한다.