[자료구조] 이진 탐색 트리(Binary Search Tree)

이진 탐색 트리

 

앞으로 글을 쓰겠지만 선형 자료 구조에서는 원하는 값을 탖는 방법이 여러가지가 있다.

가장 먼저 생각할 수 있는 것은 앞 혹은 뒤에서부터 하나씩 살펴보는 선형탐색이다.

그렇다면 트리형 자료구조에서는 원하는 값을 어떻게 찾을 수 있을까? 

가장 기초적인 방법이 바로 이진탐색 트리이다. (물론 모두 살펴볼 수도 있을 것이다.)

 

먼저 그림부터 보자.

루트 노드에 값 K가 담겨있다고 생각하자.

그렇다면 이 루트 노드의 왼쪽에 있는 서브 트리에는 K보다 작은 값이, 

오른쪽에는 K보다 큰 값만이 들어있는 트리를 생각할 수 있고,

이 모든 서브트리에도 같은 생각이 적용된다면 원하는 값을 찾기가 쉬울 것이다. 

이를 이진 탐색 트리라 한다. 실제 값을 넣어서 확인해보자

위 트리에서 13을 찾고 싶다고 생각해보자.

13은 17보다는 작고, 10보다는 크며, 15보다는 작다.

이렇게 트리를 만들어놓고 값을 찾으면 전체를 다 확인해보는 것보다 훨씬 빠르다.

따라서, 선형 자료 구조에서도 값을 빨리 찾기 위해 비슷한 방식의 이진탐색을 사용한다.

 

그렇다면 이진 탐색트리가 올바르게 동작하기 위해서는

트리에 값을 넣거나 뺄 때 노드가 적절한 위치를 찾아가야 한다.

 

먼저 값을 삽입하는 경우는 쉽다. 알맞은 자리에 간선으로 연결해주기만 하면 된다.

예를 들어 위 그래프에서 7을 넣고 싶은 경우, 1의 노드까지 찾아간 다음에 7은 1보다 크므로 7의 오른쪽에 연결해주면 된다.

 

어려운 것은 값을 삭제할 때이다.

위 그림에서 10노드를 삭제할 경우 밑에서 값이 땡겨 올라와야하는데, 값이 알맞게 처리된 후에도 이진탐색트리의 구조는 유지되어야 한다.

 

이를 유지하는 방법은 두 가지가 있다.

첫째로, 제거할 노드(10)의 오른쪽 트리의 가장 왼쪽 리프노드(13)를 땡겨와서 대체,

13은 10보다 작은 값보다는 크고, 10보다 큰 값들 중에서는 가장 작은 값이므로 10의 자리를 대체할 수 있다.

 

두번째로는, 제거할노드(10)의 왼쪽 서브트리의 가장 오른쪽 리프노드(1)을 땡겨와서 대체,

이는 위와 마찬가지로 10의 오른쪽 서브트리의 모든 값보다는 작고, 왼쪽 서브트리의 모든 값보다 큰 값이므로 10의 자리를 대체할 수 있게 된다.

 

자식 노드의 상황을 고려하여 위 두 가지 경우를 모두 사용해야 한다.

 

이진 탐색 트리를 코드로 구현하면 다음과 같다.

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

class BST:
    def __init__(self,item):
        self.root = Node(item)

    def insert(self, item):
        if self.root is None:
            self.root = Node(item)
        else:
            cur = self.root
            while 1:
                if item < cur.data:
                    if cur.left is not None:
                        cur = cur.left
                    else:
                        cur.left = Node(item)
                        break
                else:
                    if cur.right is not None:
                        cur = cur.right
                    else:
                        cur.right = Node(item)
                        break

    def search(self, item):
        cur = self.root
        while cur:
            if cur.data == item:
                return True
            elif cur.data < item:
                cur = cur.right
            else:
                cur = cur.left
        return False

    def delete(self, item):
        if not self.search(item):
            return False
        
        cur = self.root
        parent = self.root
        while cur:
            if cur.data == item:
                temp = parent
                if cur.left is None and cur.right is None:
                    if temp.left.data == item:
                        temp.left = None
                        break
                    else:
                        parent.right = None
                        break
                    
                elif cur.right is None:
                    temp = cur
                    parent_tmp = cur
                    cur = cur.right
                    
                    while cur.right is not None:
                        parent_tmp = cur
                        cur = cur.right
                    
                    temp.left = cur.left
                    temp.right = cur.right
                    parent_tmp.right = None
                    break

                else:
                    temp = cur
                    parent_tmp = cur
                    cur = cur.right
                    
                    while cur.left is not None:
                        parent_tmp = cur
                        cur = cur.left
                    
                    temp.left = cur.left
                    temp.right = cur.right
                    parent_tmp.left = None
                    break
                    
                        
            elif cur.data < item:
                parent = cur
                cur = cur.right
            else:
                parent = cur
                cur = cur.left
                
    def inorder(self, n):
        if n:
            self.inorder(n.left)
            print(n.data, end=' ')
            self.inorder(n.right)