[알고리즘] 이진 탐색 트리(Binary Search Tree) (Python)

설명

---

이진 탐색 트리(Binary Search Tree)란 왼쪽 서브 트리는 자신보다 작은 수들만 존재하고 오른쪽 서브 트리는 자신보다 큰 수들만 존재하는 이진트리를 뜻한다.

 

단순한 이진트리는 원하는 값의 존재 여부를 확인하려면 트리 전체를 탐색해야 한다.

 

따라서 자료구조로써의 효율이 떨어진다.

 

그래서 나온 것이 이진 탐색 트리이며 왼쪽은 작은 수, 오른쪽은 큰 수를 유지함으로써 탐색하는데 O(logn)의 효율적인 시간 복잡도를 가질 수 있다.

 

또한 모든 원소들은 서로 다른 값을 가진다는 조건이 붙어있다.

 

삽입과 삭제 과정을 그림을 통해 보면 이해가 쉬울 것이다.

 

이진 탐색 트리의 삽입 연산

 

먼저 트리는 항상 루트부터 시작한다.

 

기존의 트리에서 4를 추가하기 위해 루트 원소를 살펴보니 6으로 4가 더 작기 때문에 왼쪽 자식 노드로 내려간다.

 

다시 비교해보니 추가하려는 원소가 더 크기 때문에 오른쪽으로 내려가야 되는데 더 이상 자식 노드가 없으므로 오른쪽 자식 노드로 추가한다.

 

그다음 8을 추가하기 위해 다시 루트 노드부터 탐색을 시작한다.

 

6보다 크니 오른쪽 자식 노드로 내려가고 9보다 작으니 왼쪽 자식 노드, 7보다 크니 오른쪽 자식 노드로 내려가는데 이때 오른쪽 자식 노드가 없으므로 오른쪽에 노드를 추가하면 된다.

 

루트에서 시작해서 매번 범위를 절반씩 줄여 나가므로 삽입 시 O(logn)의 시간 복잡도가 걸린다.

 

삽입 연산이 크기 비교만을 통해 탐색 후 추가하는 거라 상당히 단순하기 때문에 삽입에 비해서 삭제 연산은 다소 복잡하게 느껴질 수 있다.

 

하지만 케이스를 나눠 순서를 따라가면 이해할 수 있을 것이다.

 

케이스는 크게 2가지로 삭제할 노드가 단말 노드인 경우, 자식 노드가 존재하는 경우로 나눠서 생각하면 된다.

 

단말 노드일 때 삭제 연산

 

삭제 노드를 찾기 위한 탐색은 삽입 연산과 동일하다.

 

먼저 가장 간단한 경우인 삭제할 노드가 단말 노드인 경우는 그냥 해당 노드와 부모 노드의 관계를 끊어주고 삭제하면 된다.

 

자식 노드가 존재할 경우 삭제 연산

두 번째는 자식 노드가 존재할 경우이다.

 

통상 이진 탐색 트리의 삭제는 단말 노드인 경우, 자식 노드가 한 개인 경우, 자식 노드가 두 개인 경우 이렇게 나누는데 자식 노드가 하나나 둘이어도 원리는 같은 방식이니 굳이 구분 짓진 않겠다.

 

기억해야 할 중요한 점은 삭제할 노드와 가장 차이가 적게 차이나는 노드로 교체한다는 것이다.

 

이것과 이진 탐색 트리의 특성을 기억한다면 방식을 까먹을 일은 없다.

 

즉, 삭제할 노드의 왼쪽 자식(왼쪽 서브 트리)으로 내려갔다면 가장 차이가 적게 나는 값을 찾기 위해 최대한 오른쪽 자식 노드(오른쪽 서브 트리)로 이동해야 값을 찾을 수 있을 것이고, 반대로 오른쪽 자식 노드로 내려갔다면 가장 차이가 적게 나는 값을 찾기 위해 최대한 왼쪽 자식 노드로 이동해야 값을 찾을 수 있을 것이다.

 

가장 차이가 적게 나는 노드를 찾았다면 원래 삭제할 노드와 값을 교환하고 단말 노드의 삭제를 하면 된다.

 

그림을 보면 삭제할 9를 찾기 위해 루트 노드의 오른쪽 자식으로 이동하여 삭제할 노드를 찾았고, 왼쪽 자식이 있으므로 왼쪽으로 이동 후 오른쪽 자식 노드가 존재하지 않을 때까지 오른쪽 자식 노드로 이동하였다.

 

결국 8을 찾았고 이를 9와 교체한 뒤 삭제하면 된다.

 

전체적으로 보면 알겠지만 삽입과 삭제 과정에서도 꾸준히 이진 탐색 트리의 특성을 유지하는 것을 알 수 있다.

 

구현

---

이진 트리를 구현하는 3가지 방법을 소개하겠다.

 

1. 리스트(배열)로 구현
2. 딕셔너리로 구현
3. 구조체로 구현

보통 리스트로 구현하는 방법은 낭비되는 공간이 많으므로(공간 복잡도가 비효율적이므로) 구조체로 구현하는 방법을 많이 쓴다.

 

또한 파이썬은 키, 값을 갖는 딕셔너리로도 구현이 가능하기 때문에 상황에 맞게 자신이 편한 방식대로 구현하면 된다. (필자는 딕셔너리가 가장 편하고 쉬우며 효율적이기에 자주 쓴다.)

 

코딩 테스트를 기준으로 보통 이진 탐색 트리가 나온다면 삽입이나 순회가 나온다.

 

삭제를 실제로 구현하기엔 다소 복잡하기 때문이다.

 

따라서 이진 탐색 트리를 다양하게 구현해보고 노드 삽입까지 해보겠다.

 

def list_insert(curr,num):
    if binary_tree[curr]=='*':
        binary_tree[curr]=num
    elif num<binary_tree[curr]:
        list_insert(2*curr,num)
    else:
        list_insert(2*curr+1,num)
        
print("리스트로 구현한 이진 탐색 트리\n")
binary_tree=['*' for i in range(16)]
root=1
list_insert(root,6)
list_insert(root,3)
print(binary_tree)
list_insert(root,1)
list_insert(root,9)
print(binary_tree)
list_insert(root,7)
list_insert(root,4)
list_insert(root,8)
print(binary_tree)

 

리스트로 구현할 때는 연산의 편의성 때문에 인덱스 1을 루트 노드로 가정한다.

 

인덱스 1을 루트로 하기 때문에 인덱스*2는 왼쪽 자식 노드, 인덱스*2+1은 오른쪽 자식 노드로 생각할 수 있다.

 

트리의 형태는 본문의 노드 삽입 결과와 똑같기 때문에 결과 화면과 그림을 비교해보면서 인덱스를 추적하면 이해가 될 것이다.

 

리스트 결과 화면

 

def dic_insert(curr,num):
    global root
    if len(binary_tree)==0:
        root=num
        binary_tree[root]=['*','*']
    else:
        if num<curr:
            if binary_tree[curr][0]=='*':
                binary_tree[curr][0]=num
                binary_tree[num]=['*','*']
            else:
                dic_insert(binary_tree[curr][0],num)
        else:
            if binary_tree[curr][1]=='*':
                binary_tree[curr][1]=num
                binary_tree[num]=['*','*']
            else:
                dic_insert(binary_tree[curr][1],num)
                
print("딕셔너리로 구현한 이진 탐색 트리\n")
binary_tree={}
root=None
dic_insert(root,6)
dic_insert(root,3)
print(binary_tree)
dic_insert(root,1)
dic_insert(root,9)
print(binary_tree)
dic_insert(root,7)
dic_insert(root,4)
dic_insert(root,8)
print(binary_tree)

 

딕셔너리는 키를 노드의 원소, 값을 길이가 2인 리스트로 선언하여 왼쪽 자식과 오른쪽 자식으로 구분 짓는다.

 

따라서 딕셔너리의 길이가 0일 땐 루트의 원소로 갱신하고 새로운 노드를 삽입할 땐 부모 노드에서 자식 노드를 갱신하고 초기화된 노드를 추가하는 것을 잊지 말아야 한다. 

 

딕셔너리 결과 화면

 

class Node:
    def __init__(self,num):
        self.data=num
        self.left=self.right=None

class Binary_tree:
    def __init__(self):
        self.root=None

    def Node_insert(self,num):
        if self.root==None:
            self.root=Node(num)
        else:
            self.curr=self.root
            while True:
                if num<self.curr.data:
                    if self.curr.left==None:
                        self.curr.left=Node(num)
                        break
                    else:
                        self.curr=self.curr.left
                else:
                    if self.curr.right==None:
                        self.curr.right=Node(num)
                        break
                    else:
                        self.curr=self.curr.right
                        
print("구조체로 구현한 이진 탐색 트리\n")
Binary=Binary_tree()
Binary.Node_insert(6)
Binary.Node_insert(3)
Binary.Node_insert(1)
Binary.Node_insert(9)
Binary.Node_insert(7)
Binary.Node_insert(4)
Binary.Node_insert(8)

 

구조체로 구현하는 방식은 노드에 대한 구조체를 선언하고 해당 노드들을 이진 트리의 구조체로 묶는 형식이다.

 

파이썬의 특성상 Class의 인스턴스를 생성한 뒤 첫 번째 인자로 넘기기 때문에 self로 받는다.

 

이런 부분까지 다루게 되면 상당히 복잡하고 어려워지므로 이진 탐색 트리는 여기까지 하도록 하겠다.