자료구조 | 이진 탐색 트리(Binary Search Tree, BST)

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

이진 탐색 트리는 이진 트리의 한 종류로, 효율적인 탐색이 가능하도록 노드를 배치한 형태이다. 

 

1. 기본 개념

이진 탐색 트리의 모든 노드에는 다음 두 가지 조건이 재귀적으로 적용된다. 

1. 왼쪽 서브트리의 모든 노드의 Key는 자신의 Key보다 작고,
2. 오른쪽 서브트리의 모든 노드의 Key는 자신의 Key보다 크다.

(좌 출처: https://yoongrammer.tistory.com/71) (우 출처: Do it! 자료구조와 함께 배우는 알고리즘 입문)

 

위 이미지를 보면, 어떠한 노드이든 자기자신을 기준으로 반을 나누면 왼쪽은 자신보다 Key 값이 작고, 오른쪽은 자신보다 Key 값이 크다. 

 

BST의 특성

이진 탐색 트리는 다음과 같은 특성이 있다.

1. 데이터의 정렬된 순서를 유지하는 속성을 갖는다.
   1. BST의 최소값 -> 트리의 가장 왼쪽 값
   2. BST의 최대값 -> 트리의 가장 오른쪽 값
2. 중위 순회를 거치면 노드 값을 오름차순으로 얻을 수 있다.
   • 위 그림으로 테스트해보면 바로 알 수 있다.
   • 오른쪽 그림에서 중위 순회를 거친 경로: [1, 4, 5, 6, 7, 9, 11, 12, 13, 14, 15, 18]
3. 이진 탐색과 비슷한 방식으로 아주 빠른 검색이 가능
   • 주어진 값을 기준으로 더 작은 값을 찾고 싶을 때는 왼쪽 서브트리로 , 더 큰 값을 찾고 싶을 때는 오른쪽 서브트리로 이동하여 탐색한다.
4. 노드 삽입이 수월하다.

 

2. 노드의 후계자(successor), 전임자(predecessor)

노드의 후계자(successor)

• 해당 노드보다 값이 큰 노드들 중에서 가장 작은 노드
  • 20의 후계자 = 30
  • 17의 후계자 = 20
  • 10의 후계자 = 15

 

노드의 전임자(predecessor)

• 해당 노드보다 값이 작은 노드들 중에서 가장 큰 노드
  • 20의 전임자 = 17
  • 17의 전임자 = 15
  • 10의 전임자 = 5

 

후계자와 전임자 개념은 BST의 삭제 연산 중에서, 삭제 대상 노드가 두 개의 자식 노드를 갖고 있는 경우에 필요하다. 

 

3. BST의 주요 연산 - 코드로 이해하기

노드를 클래스로 구현 -> 1) 탐색, 2) 삽입, 3) 삭제 순으로 알아보자.

 

노드 구현하기

가장 먼저 노드를 클래스로 구현해본다.

# 노드 객체
class Node:
    def __init__(self, key):
        self.value = key # 현재 노드의 값을 저장
        self.left = None # 왼쪽 자식 노드를 가리킴
        self.right = None # 오른쪽 자식 노드를 가리킴

 

• Node 클래스의 인스턴스를 생성하여 각각의 노드를 만든다. 
• __init__()은 자바로 치면 생성자이다. 객체 초기화 작업을 수행한다. 
• self는 해당 인스턴스를 가리키는 참조변수이다. 자바의 'this'와 유사한 역할을 한다. 
• 객체의 속성으로 자기 자신의 값(self.val), 왼쪽 자식 노드(self.left), 오른쪽 자식 노드(self.right)를 갖고있다. 이를 통해 트리 구조를 구성한다. 

파이썬도 객체지향언어 ...

 

탐색 (Search)

# 탐색
def search(root, key):
    # 현재 노드가 없거나 찾는 값이라면 반환해준다.
    if root is None or root.value == key:
        return root
    
    # 찾는 값이 현재 노드의 값보다 크면 오른쪽으로 탐색
    if root.value < key:
        return search(root.right, key)
    # 그렇지 않으면 왼쪽으로 탐색
    else:    
        return search(root.left, key)
시작 노드에서 값을 비교하여 찾으려는 값이 현재 노드의 값보다 작으면 왼쪽 서브트리로, 크면 오른쪽 서브트리로 이동한다.
이 과정을 반복하며 값을 찾거나 탐색 가능한 노드가 없을 때까지 진행한다.

• 시작 노드에서 값을 비교하여 찾으려는 값이 현재 노드의 값보다 작으면 왼쪽 서브트리로, 크면 오른쪽 서브트리로 이동한다.
• 이 과정을 반복하며 값을 찾거나 탐색 가능한 노드가 없을 때까지 진행한다.

 

삽입 (Insertion)

(중복된 값을 삽입하지 않는다는 가정 하에 진행)

# 삽입
def insert(root, key):
    # 현재 노드가 없으면(리프에 도달했다면) 새로운 노드 생성 후 반환
    if root is None:
        return Node(key)
    
    # 삽입하려는 값이 현재 노드의 값보다 작으면 -> 왼쪽 subtree에 삽입
    if key < root.value:
        root.left = insert(root.left, key)
    # 삽입하려는 값이 현재 노드의 값보다 크거나 같으면 -> 오른쪽 subtree에 삽입
    else:
        root.right = insert(root.right, key)
    
    return root # 반환된 노드(root)가 상위 호출에서 왼쪽 or 오른쪽 자식으로 설정되면서 삽입 수행

1. 트리를 순회하며, 값의 크기를 기준으로 삽입하려는 값이 들어갈 적절한 위치를 찾는다. 
2. 해당 위치에 새 노드를 생성하여 값을 삽입한다.

 

 

삭제 (Deletion)

BST에서의 삭제 연산은 그 과정이 꽤 복잡하다.

# 자식 노드 2개인 경우를 처리하기 위한 함수
def minValueNode(node):
    # 현재 노드 기준으로 왼쪽 가지로 내려가서 최소값 노드를 반환함
    current_node = node
    while current_node.left is not None:
        current_node = current_node.left
    return current_node

# 삭제 
def delete(root, key):
    # 0. 삭제하려는 노드가 이미 트리에 존재하지 않는 경우
    if root is None:
        return root # root.left 또는 root.right에 None이 들어가면서 삭제가 구현됨
	
    # 1. 삭제하려는 노드 찾기
    if key < root.value: # 삭제하려는 값이 현재 노드의 값보다 작으면
        root.left = delete(root.left, key) # 왼쪽 서브트리로 재귀
    
    elif key > root.value: # 삭제하려는 값이 현재 노드의 값보다 크면
        root.right = delete(root.right, key) # 오른쪽 서브트리로 재귀

    # 2. 자식 개수에 따라 적절한 삭제 조치
    else:
        # 왼쪽 자식이 없는 경우 (자식이 0개인 경우도 여기에 걸림)
        if root.left is None: 
            return root.right # 오른쪽 자식 or None을 현재 노드 자리로 올려준다. 
        
        # 오른쪽 자식이 없는 경우
        elif root.right is None:
            return root.left # 왼쪽 자식 or None을 현재 노드 자리로 올려준다. 
        
        # 2개의 자식 노드를 가지는 경우
        root.value = minValueNode(root.right).value # successor 값을 현재 노드에 복사
        root.right = delete(root.right, root.value) # succssor의 원래 위치를 삭제

    return root

1. 삭제하려는 값을 탐색하여 노드를 찾는다.
2. 삭제 및 대체 작업: 자식 노드의 개수에 따라 다음 3가지 케이스로 나뉜다. 

1. 자식이 없는 경우(해당 노드가 리프 노드인 경우)

• 땡큐. 해당 노드를 None으로 바꾸고 끝

출처: Do it! 자료구조와 함께 배우는 알고리즘 입문

 

2. 하나의 자식만을 가진 경우

• 부모에서 해당 노드를 가리키던 포인터를 해당 노드의 자녀를 가리키도록 변경한다.
• (파이썬의 경우 자식 노드를 자기 대신 리턴해줌으로써 위치 바꾸기)

 

3. 두 개의 자식 노드를 가진 경우 

• 전임자 또는 후계자를 찾아 그 값으로 대체하고, 해당 자리를 삭제한다.
• 둘 중에 뭐로 대체할지는 정하기 나름. 
• 밑의 예시는 전임자로 대체하는 예시인데, CLRS 기준으로는 후계자로 대체함.
  (후계자는 오른쪽 서브트리의 리프 노드일 수밖에 없으므로 후계자가 더 직관적인 것 같음)

이 이미지에선 왼쪽 서브트리의 최대값 노드를 올려줬다.

 

 

4. BST의 장단점

장점:

탐색, 삽입, 삭제가 모두 평균적으로 O(logn)에 가능하다.

• 탐색의 효율성: 평균적으로 O(logn)의 시간 복잡도로 원하는 값을 찾을 수 있다. 이진 탐색 트리의 구조상, 루트부터 시작하여 탐색하려는 키 값과 노드의 키 값을 비교하여 왼쪽 혹은 오른쪽 서브트리로 이동하면서 탐색을 진행하기 때문이다. 
• 삽입의 효율성: 평균적인 시나리오에서 O(logn)의 시간 복잡도로 노드를 삽입할 수 있다. 삽입 또한 탐색과 유사한 과정을 거쳐 적절한 위치에 노드를 추가할 수 있다. 
• 삭제의 효율성: 평균적으로 O(logn)의 시간에 삭제가 완료된다. 노드를 삭제할 때도 탐색을 먼저 진행한 후, 해당 노드를 삭제하는 과정이 이루어진다.

단점:

• 트리의 균형 유지 문제: 이진 탐색 트리는 입력 순서에 따라 트리의 깊이가 너무 깊어질 수 있다.

오름차순으로 데이터가 입력되어 BST가 치우쳐진 예시

예를 들어, 오름차순으로 데이터를 입력하면 트리는 한쪽으로 치우친 형태가 된다. 

• 최악의 경우 시간 복잡도 문제: 위의 균형 유지 문제로 인해, 최악의 경우에는 탐색, 삽입, 삭제 연산의 시간 복잡도가 시간 복잡도는 O(n)이 되어 효율성이 크게 떨어진다. 
  
  

 

5. 균형 이진 탐색 트리

위에서 언급한 이진 탐색 트리의 단점인 트리의 균형 유지 문제를 해결하기 위해 균형 이진 탐색 트리가 고안되었다.

 

균형 이진 탐색 트리는 삽입, 삭제 시 트리의 균형을 유지하면서 연산을 수행한다. 이를 통해 트리의 높이를 O(logn)으로 유지하고, 탐색, 삽입, 삭제 연산의 효율성을 항상 보장한다. 

 

 

균형 이진 탐색 트리 간단 소개:

• AVL 트리: AVL 트리는 노드마다 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이(균형 인수)를 저장한다. 삽입이나 삭제 시에 균형 인수가 2 이상이면, 회전 연산을 통해 트리의 균형을 유지한다.
• 레드-블랙 트리 (RB tree): 레드-블랙 트리는 각 노드에 색상(레드 혹은 블랙)을 부여하여 트리의 균형을 유지한다. 특정 규칙(레드-블랙 트리의 성질)을 만족시키도록 삽입, 삭제 시 회전 및 색상 변경 연산을 수행한다.
  • https://hyuga.tistory.com/48