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

이진 탐색 트리 (binary search tree) 

 

※ 이진 탐색 트리 삽입 구현 :: insert

class Node:
    """이진 탐색 트리 노드 클래스"""
    def __init__(self, data):
        self.data = data
        self.parent = None
        self.right_child = None
        self.left_child = None


def print_inorder(node):
    """주어진 노드를 in-order로 출력해주는 함수"""
    if node is not None:
        print_inorder(node.left_child)
        print(node.data)
        print_inorder(node.right_child)


class BinarySearchTree:
    """이진 탐색 트리 클래스"""
    def __init__(self):
        self.root = None


    def insert(self, data):
        """이진 탐색 트리 삽입 메소드"""
        new_node = Node(data)  # 삽입할 데이터를 갖는 노드 생성

        # 트리가 비었으면 새로운 노드를 root 노드로 만든다
        if self.root is None:
            self.root = new_node
            return

        temp = self.root  # 저장하려는 위치를 찾기 위해 사용할 변수. root 노드로 초기화한다

        # 원하는 위치를 찾아간다
        while temp is not None:
            if data > temp.data:  # 삽입하려는 데이터가 현재 노드 데이터보다 크다면
                # 오른쪽 자식이 없으면 새로운 노드를 현재 노드 오른쪽 자식으로 만듦
                if temp.right_child is None:
                    new_node.parent = temp
                    temp.right_child = new_node
                    return
                # 오른쪽 자식이 있으면 오른쪽 자식으로 간다
                else:
                    temp = temp.right_child
            else:  # 삽입하려는 데이터가 현재 노드 데이터보다 작다면
                # 왼쪽 자식이 없으면 새로운 노드를 현재 노드 왼쪽 자식으로 만듦
                if temp.left_child is None:
                    new_node.parent = temp
                    temp.left_child = new_node
                    return
                # 왼쪽 자식이 있다면 왼쪽 자식으로 간다
                else:
                    temp = temp.left_child
            


    def print_sorted_tree(self):
        """이진 탐색 트리 내의 데이터를 정렬된 순서로 출력해주는 메소드"""
        print_inorder(self.root)  # root 노드를 in-order로 출력한다


# 빈 이진 탐색 트리 생성
bst = BinarySearchTree()

# 데이터 삽입
bst.insert(7)
bst.insert(11)
bst.insert(9)
bst.insert(17)
bst.insert(8)
bst.insert(5)
bst.insert(19)
bst.insert(3)
bst.insert(2)
bst.insert(4)
bst.insert(14)

# 이진 탐색 트리 출력
bst.print_sorted_tree()

 

 

※ 이진 탐색 트리 탐색

  : 3가지의 경우로 반복문 돌리기. 

    [  data == temp.data  /  data > temp.data  /  data < temp.data  ]

def search(self, data):
    """이진 탐색 트리 탐색 메소드, 찾는 데이터를 갖는 노드가 없으면 None을 리턴한다"""
    temp = self.root  # 탐색용 변수, root 노드로 초기화

    # 원하는 데이터를 갖는 노드를 찾을 때까지 돈다
    while temp is not None:
        # 원하는 데이터를 갖는 노드를 찾으면 리턴
        if data == temp.data:
            return temp
        # 원하는 데이터가 노드의 데이터보다 크면 오른쪽 자식 노드로 간다
        if data > temp.data:
            temp = temp.right_child
        # 원하는 데이터가 노드의 데이터보다 작으면 왼쪽 자식 노드로 간다
        else:
            temp = temp.left_child

    return None # 원하는 데이터가 트리에 없으면 None 리턴

▼ 이진 탐색 트리 응용해서 find_min 함수 구현하기

@staticmethod
def find_min(node):
    """(부분)이진 탐색 트리의 가장 작은 노드 리턴"""
    temp = node  # 도우미 변수. 파라미터 node로 초기화

    # temp가 node를 뿌리로 갖는 부분 트리에서 가장 작은 노드일 때까지 왼쪽 자식 노드로 간다
    while temp.left_child is not None:
        temp = temp.left_child      

    return temp

 

 

※ 이진 탐색 트리 삭제 구현  :: delete

 : 코드를 짤 때, 삭제하려는 노드가 root 노드인지, 삭제하려는 노드가 부모의 왼쪽자식인지 오른쪽 자식인지,

   삭제하려는 노드의 자식이 왼쪽에 있는지 오른쪽에 있는지를 다 생각해 줘야 된다.

   어떤 경우든 "삭제하는 노드의 위치를 자식 노드가 대신 차지한다."는 원칙을 잘 기억하면 쉽게 접근이 가능하다 !

 

def delete(self, data):
    """이진 탐색 트리 삭제 메소드"""
    node_to_delete = self.search(data)  # 삭제할 노드를 가지고 온다
    parent_node = node_to_delete.parent  # 삭제할 노드의 부모 노드

CASE 1. 지우려는 노드가 leaf 노드일 때

    if node_to_delete.left_child is None and node_to_delete.right_child is None:
        if self.root is node_to_delete:
            self.root = None
        else:  # 일반적인 경우
            if node_to_delete is parent_node.left_child: 
                parent_node.left_child = None
            else:
                parent_node.right_child = None

CASE 2. 지우려는 노드가 자식이 하나인 노드일 때

    elif node_to_delete.left_child is None:  # 지우려는 노드가 오른쪽 자식만 있을 때:
        # 지우려는 노드가 root 노드일 때
        if node_to_delete is self.root:
            self.root = node_to_delete.right_child
            self.root.parent = None
        # 지우려는 노드가 부모의 왼쪽 자식일 때
        elif node_to_delete is parent_node.left_child:
            parent_node.left_child = node_to_delete.right_child
            node_to_delete.right_child.parent = parent_node
        # 지우려는 노드가 부모의 오른쪽 자식일 때
        else:
            parent_node.right_child = node_to_delete.right_child
            node_to_delete.right_child.parent = parent_node

    elif node_to_delete.right_child is None:  # 지우려는 노드가 왼쪽 자식만 있을 때:
        # 지우려는 노드가 root 노드일 때
        if node_to_delete is self.root:
            self.root = node_to_delete.left_child
            self.root.parent = None
        # 지우려는 노드가 부모의 왼쪽 자식일 때
        elif node_to_delete is parent_node.left_child:
            parent_node.left_child = node_to_delete.left_child
            node_to_delete.left_child.parent = parent_node
        # 지우려는 노드가 부모의 오른쪽 자식일 때
        else:
            parent_node.right_child = node_to_delete.left_child
            node_to_delete.left_child.parent = parent_node

CASE 3. 삭제하려는 데이터의 노드가 두 개의 자식이 있을 때  (제일 이해가 어려웠던 경우..)

             - successor : 특정 노드보다 큰 노드 중 가장 작은 노드

    else:
        successor = self.find_min(node_to_delete.right_child)  # 삭제하려는 노드의 successor 노드 받아오기

        node_to_delete.data = successor.data  # 삭제하려는 노드의 데이터에 successor의 데이터 저장

        # successor 노드 트리에서 삭제
        if successor is successor.parent.left_child:  # successor 노드가 오른쪽 자식일 때
            successor.parent.left_child = successor.right_child
        else:  # successor 노드가 왼쪽 자식일 때
            successor.parent.right_child = successor.right_child        

        if successor.right_child is not None:  # successor 노드가 오른쪽 자식이 있을 떄
            successor.right_child.parent = successor.parent

 

   ▽ 해결방법 단계별 정리 

       1. 지우려는 노드의 successor를 받아온다. (find_min() 메소드 활용)

       2. 삭제하려는 노드 데이터에 successor의 데이터를 저장한다.

       3. successor 노드를 삭제한다.

 

  ▽ successor 노드를 삭제할 때 고려해야 하는 두 가지 경우.

    → 삭제하려는 노드의 오른쪽 부분 트리 내에서, 어떤 부모 노드의 왼쪽 자식으로 있는 경우

        : successor는 어떤 부모 노드의 오른쪽 자식으로 있을 수 없다. successor 조건 어긋남.

    → 삭제하려는 노드의 바로 밑에 있는 오른쪽 자식인 경우

 

 

 

 

이진 탐색 트리 연산들의 시간은 모두 그 높이 h에 비례한다.

따라서, 편향된 트리일수록 연산들이 비효율적으로, 균형이 잡힌 트리일수록 연산들이 효율적으로 이루어진다.

 

이진 탐색 트리로 추상 자료형, 세트나 딕셔너리를 코드로 구현할 수 있다.

일반적인 경우에는 해시 테이블을 사용하는 게 이진 탐색 트리를 사용하는 것보다 더 효율적이다.

하지만 세트의 데이터나 딕셔너리의 key를 정렬된 상태로 사용하고 싶을 때는 이진 탐색 트리를 사용해야 한다.

대신 이때는 물론 해시 테이블 때보다는 연산의 효율성은 조금 포기해야된다 .. !