[Data Structure] 이진 탐색 트리(Binary Search Tree)

이진 탐색 트리(Binary Search Tree)?

이진탐색트리란 다음과 같은 특징을 갖는 이진트리를 말한다.

• 각 노드에 중복되지 않는 키가 있다.
• 노드의 왼쪽 서브트리에는 그 노드의 값보다 작은 값들을 지닌 노드들로 이루어져 있다.
• 노드의 오른쪽 서브트리에는 그 노드의 값보다 큰 값들을 지닌 노드들로 이루어져 있다.
• 좌우 서브 트리는 각각이 다시 이진탐색트리여야 한다.

 

이진탐색트리는 이진탐색(Binary Search)과 연결리스트(Linked List)를 결합한 자료구조이다.

이진탐색트리(BST)는 이진탐색의 빠른 탐색 시간과 연결리스트의 빠른 삽입/삭제의 장점들을 가져왔다.

• 이진탐색은 탐색 시간이 O(log n)으로 빠르지만 삽입/삭제가 불가능하다. 또 연결리스트의 경우, 삽입/삭제는 O(1)이지만 탐색 시간은 O(n)으로 이진탐색보다 효율적이지 않다.

중복된 키는 왜 없어야 하는가?

중복키를 제대로 처리하려면 모든 중복키에 접근할 수 있어야 한다. 하지만 이진탐색트리는 비선형 자료구조 특성상 중복키를 제대로 처리하기 힘들다.

또 중복이 많아지면 트리의 탐색 속도가 느려져 이진탐색트리의 장점이 사라진다.

따라서, 중복값은 카운트나 연결리스트를 통하여 처리할 수 있도록 하는 것이 좋다.

 

특징

• 균형 상태이면 O(logN), 불균형 상태이면 O(N)의 시간복잡도를 가진다.
• 중위 순회(Inorder Traversal)를 통해 키 값이 정렬된 상태로 가져올 수 있다.
• 입력되는 값의 순서에 따라 한쪽으로 노드가 몰리게 될 수 있다.
  • 불균형한 트리는 효율이 좋지 않아 균형잡힌 트리로 바꿔주는 것이 좋다.
  • 균형잡힌 트리로 바꾸는 대표적인 방법으로는 AVL Tree, B-Tree 등이 있다.

 

연산

탐색

이진탐색트리의 탐색은 다음과 같은 과정을 거친다.

1. 루트에서부터 찾고자 하는 값을 비교한다.
2. 탐색하려는 값이 루트노드의 값보다 작다면 왼쪽서브트리로, 크다면 오른쪽서브트리로 탐색을 진행한다.
3. 일치하는 값을 찾을때까지 반복한다.
4. 탐색하려는 값이 없으면 null을 반환한다.

def search(self, key):
	self.cur_node = self.root
    while self.cur_node:
    	if key == self.cur_node.key:
            return self.cur_node.key
        elif key < self.cur_node.key:
            if self.cur_node.left is None:
                return None
            else:
                self.cur_node = self.cur_node.left
        else:
            if self.cur_node.right is None:
                return None
            else:
                self.cur_node = self.cur_node.right

 

순환 탐색

이진탐색트리는 중위순회를 통해 정렬된 순서로 탐색할 수 있다.

중위순회

 

삽입

삽입하려는 노드를 트리에 있는 각 노드들과 비교하여 알맞은 위치를 찾아나간다.

-> 해당 노드의 값보다 작으면 왼쪽 자식 노드, 크면 오른쪽 자식 노드로 이동

def insert(self, key):
    self.cur_node = self.root
    while True:
        if key < self.cur_node.key:
            if self.cur_node.left is None:
                self.cur_node.left = Node(key)
            else:
                self.cur_node = self.cur_node.left
                break
        else:
            if self.cur_node.right is None:
                self.cur_node.right = Node(key)
            else:
                self.cur_node = self.cur_node.right
                break

 

삭제

삭제 연산은 3가지의 경우의 수가 존재한다.

• 단말 노드(leaf node)인 경우
  • 처리할 서브 트리가 없으므로 삭제할 노드의 부모 노드를 찾아서 연결을 끊는다.
• 하나의 서브 트리만 가지고 있는 경우
  • 해당 노드를 삭제하고 서브 트리를 삭제된 노드 자리로 올린다.
• 두 개의 서브트리를 가지고 있는 경우
  • 트리 삭제 수행 후, 왼쪽 자식 노드에서 가장 큰 값이나 오른쪽 자식 노드에서 가장 작은 값을 삭제된 노드 자리로 올린다.

def delete(self, key):
    is_search = False
    self.cur_node = self.root
    self.parent = self.root
    while self.cur_node:
        if self.cur_node.key == key:
            is_search = True
            break
        elif key < self.cur_node.key:
            self.parent = self.cur_node
            self.cur_node = self.cur_node.left
        else:
            self.parent = self.cur_node
            self.cur_node = self.cur_node.right
    if is_search == False:
        return False

    # 삭제할 노드가 자식 노드를 갖고 있지 않을 때
    if self.cur_node.left is None and self.cur_node.right is None:
        if key < self.parent.key:
            self.parent.left = None
        else:
            self.parent.right = None

    # 삭제할 노드가 자식 노드를 한 개 가지고 있을 때(왼쪽 자식 노드)
    if self.cur_node.left is not None and self.cur_node.right is None:
        if key < self.parent.key:
            self.parent.left = self.cur_node.left
        else:
            self.parent.right = self.cur_node.left

    # 삭제할 노드가 자식 노드를 한 개 가지고 있을 때(오른쪽 자식 노드)
    if self.cur_node.left is None and self.cur_node.right is not None:
        if key < self.parent.key:
            self.parent.left = self.cur_node.right
        else:
            self.parent.right = self.cur_node.right

    # 삭제할 노드가 자식 노드를 두 개 가지고 있을 때
    if self.cur_node.left is not None and self.cur_node.right is not None:
        self.change_node = self.cur_node.right
        self.change_node_parent = self.cur_node.right
        while self.change_node.left is not None:
            self.change_node_parent = self.change_node
            self.change_node = self.change_node.left
        if self.change_node.right != None:
            self.change_node_parent.left = self.change_node.right
        else:
            self.change_node_parent.left = None

        if key < self.parent.key:
            self.parent.left = self.change_node
            self.change_node.right = self.cur_node.right
            self.change_node.left = self.cur_node.left
        else:
            self.parent.right = self.change_node
            self.change_node.left = self.cur_node.left
            self.change_node.right = self.cur_node.right

    return True

 

시간복잡도

• 균등 트리(Blanced Binary Tree): O(log n)
• 편향 트리(Skewed Binary Tree): O(n)

트리의 연산(탐색, 삽입, 삭제)의 속도는 트리의 깊이(depth)에 비례하며, 균등 트리(Blanced Binary Tree)일 때보다 편향 트리(Skewed Binary Tree)일 때 더 느려진다.

 

전체 코드

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

class Tree:
    def __init__(self, root):
        self.root = root
        
    def insert(self, key):
        self.cur_node = self.root
        while True:
            if key < self.cur_node.key:
                if self.cur_node.left is None:
                    self.cur_node.left = Node(key)
                else:
                    self.cur_node = self.cur_node.left
                    break
            else:
                if self.cur_node.right is None:
                    self.cur_node.right = Node(key)
                else:
                    self.cur_node = self.cur_node.right
                    break
    
    def search(self, key):
        self.cur_node = self.root
        while self.cur_node:
            if key == self.cur_node.key:
                return self.cur_node.key
            elif key < self.cur_node.key:
                if self.cur_node.left is None:
                    return None
                else:
                    self.cur_node = self.cur_node.left
            else:
                if self.cur_node.right is None:
                    return None
                else:
                    self.cur_node = self.cur_node.right
                    
    def delete(self, key):
        is_search = False
        self.cur_node = self.root
        self.parent = self.root
        while self.cur_node:
            if self.cur_node.key == key:
                is_search = True
                break
            elif key < self.cur_node.key:
                self.parent = self.cur_node
                self.cur_node = self.cur_node.left
            else:
                self.parent = self.cur_node
                self.cur_node = self.cur_node.right
        if is_search == False:
            return False

        # 삭제할 노드가 자식 노드를 갖고 있지 않을 때
        if self.cur_node.left is None and self.cur_node.right is None:
            if key < self.parent.key:
                self.parent.left = None
            else:
                self.parent.right = None

        # 삭제할 노드가 자식 노드를 한 개 가지고 있을 때(왼쪽 자식 노드)
        if self.cur_node.left is not None and self.cur_node.right is None:
            if key < self.parent.key:
                self.parent.left = self.cur_node.left
            else:
                self.parent.right = self.cur_node.left

        # 삭제할 노드가 자식 노드를 한 개 가지고 있을 때(오른쪽 자식 노드)
        if self.cur_node.left is None and self.cur_node.right is not None:
            if key < self.parent.key:
                self.parent.left = self.cur_node.right
            else:
                self.parent.right = self.cur_node.right

        # 삭제할 노드가 자식 노드를 두 개 가지고 있을 때
        if self.cur_node.left is not None and self.cur_node.right is not None:
            self.change_node = self.cur_node.right
            self.change_node_parent = self.cur_node.right
            while self.change_node.left is not None:
                self.change_node_parent = self.change_node
                self.change_node = self.change_node.left
            if self.change_node.right != None:
                self.change_node_parent.left = self.change_node.right
            else:
                self.change_node_parent.left = None

            if key < self.parent.key:
                self.parent.left = self.change_node
                self.change_node.right = self.cur_node.right
                self.change_node.left = self.cur_node.left
            else:
                self.parent.right = self.change_node
                self.change_node.left = self.cur_node.left
                self.change_node.right = self.cur_node.right

        return True