이진 탐색 트리

Jeris·2023년 4월 18일
data structure
0

코드잇 부트캠프 0기

목록 보기
44/107

1. 이진 탐색 트리란

이진 탐색 트리(Binary search tree)

  • 다음과 같은 속성이 있는 이진 트리 자료 구조
    • 각 노드에 값이 있다.
    • 값들은 전순서가 있다.
      • 전순서(totally order): 임의의 두 원소를 비교할 수 있는 부분 순서
    • 노드의 왼쪽 서브트리에는 그 노드의 값보다 작은 값들을 지닌 노드들로 이루어져 있다.
    • 노드의 오른쪽 서브트리에는 그 노드의 값보다 큰 값들을 지닌 노드들로 이루어져 있다.
    • 좌우 하위 트리는 각각이 다시 이진 탐색 트리여야 한다.
  • 딕셔너리, 세트 등을 구현하는 데 쓸 수 있다.

2. 이진 탐색 트리 노드 구현

  • 완전 이진 트리가 아닐 수 있기 때문ㄴ에 노드 클래스를 정의한 후 여러 노드 인스턴트들을 생성하고 이 인스턴스들을 연결해서 구현한다.
  • 더블리 링크드 리스트로 구현한 트리 노드에서 parent reference를 담을 변수만 추가하면 된다.

3. 이진 탐색 트리 출력

  • 이진 탐색 트리를 in-order 순회하면 정렬된 순서대로 노드에 접근할 수 있다.
  • Worst-case time complexity: O(h)
  • Best-case time complexity: O(1)
  • Average time complexity: O(log(h))
  • Worst-case space complexity: O(n)
class Node:
    def __init__(self, data):
        self.data = data
        self.parent = None
        self.left_child = None
        self.right_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 print_sorted_tree(self):
        """이진 탐색 트리 내의 데이터를 정렬된 순서로 출력해주는 메소드"""
        print_inorder(self.root)  # root 노드를 in-order로 출력한다

4. 이진 탐색 트리 삽입

  1. 새로운 노드를 생성한다. (O(1))
  2. root 노드부터 data를 비교하면서 저장할 위치를 찾는다. (h: 트리의 높이, O(h))
  3. 찾은 위치에 새롭게 만든 노드를 연결한다. (O(1))
  • Worst-case time complexity: O(h)
  • Best-case time complexity: O(1)
  • Average time complexity: O(log(h))
  • Worst-case space complexity: O(n)
def insert(self, data):
        """이진 탐색 트리 삽입 메소드"""
    new_node = Node(data)

    if self.root is None:
        self.root = new_node
        return

    temp = self.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

5. 이진 탐색 트리 탐색

  1. 주어진 노드의 데이터와 탐색하려는 데이터를 비교한다.
  2. 탐색하려는 데이터가 더 크면 노드의 오른쪽 자식 노드로 가서 탐색하고, 아니라면 왼쪽 자식 노드로 가서 탐색한다.
  3. 탐색을 완료되지 않았다면 1단계로 이동한다.
  • Worst-case time complexity: O(h)
  • Best-case time complexity: O(1)
  • Average time complexity: O(log(h))
  • Worst-case space complexity: O(n)
def search(self, data):
    """이진 탐색 트리 탐색 메소드, 찾는 데이터를 갖는 노드가 없으면 None을 리턴한다"""
    temp = self.root

    while temp is not None:
        if data == temp.data:
            return temp
        elif data < temp.data:
            temp = temp.left_child
        else:
            temp = temp.right_child

    return None

6. 이진 탐색 트리 삭제

  1. 삭제하려는 노드를 탐색한다. (O(h))
  • leaf 노드를 삭제하려 할 때
    1. leaf 노드의 부모 노드의 left_child 또는 right_child 레퍼런스를 삭제한다. 부모 노드가 없을 경우(root node) root node를 삭제한다. (O(1))
  • 하나의 자식 노드만 있는 노드를 삭제하려 할 때
    1. 자식 노드가 삭제하려는 노드의 자리를 차지하도록 레퍼런스를 조정한다.(O(1))
  • 두 개의 자식이 있는 노드를 삭제하려 할 때
    1. 삭제하려는 노드의 오른쪽 서브 트리에서 가장 작은 값을 가진 노드(Successor) 혹은 왼쪽 서브 트리에서 가장 큰 값을 가진 노드(Predecessor)를 탐색한다. (O(h))
    2. Successor 혹은 Predecessor와 삭제하려는 노드의 데이터를 서로 바꾼다. (O(1))
    3. 데이터가 바뀐 Successor 혹은 Predecessor의 부모의 left_child 또는 right_child 레퍼런스를 삭제한다. (O(1))
  • Worst-case time complexity: O(h)
  • Best-case time complexity: O(1)
  • Average time complexity: O(log(h))
  • Worst-case space complexity: O(n)
class Node:
    def __init__(self, data):
        self.data = data
        self.parent = None
        self.left_child = None
        self.right_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 delete(self, data):
        """이진 탐색 트리 삭제 메소드"""
        node_to_delete = self.search(data)
        parent_node = node_to_delete.parent

        # 경우 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

        # 경우 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

        # 경우 3: 지우려는 노드가 2개의 자식이 있을 때
        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

    @staticmethod
    def find_min(node):
        """(부분)이진 탐색 트리의 가장 작은 노드 리턴"""
        temp = node

        while temp.left_child is not None:
            temp = temp.left_child

        return temp

    def search(self, data):
        """이진 탐색 트리 탐색 메소드, 찾는 데이터를 갖는 노드가 없으면 None을 리턴한다"""
        if self.root is None:
            return None

        temp = self.root

        while temp is not None:
            if data == temp.data:
                return temp
            elif data < temp.data:
                temp = temp.left_child
            else:
                temp = temp.right_child

        return None

    def insert(self, data):
        """이진 탐색 트리에 데이터를 삽입해주는 메소드"""
        new_node = Node(data)

        if self.root is None:
            self.root = new_node
            return

        temp = self.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)
        
# 빈 이진 탐색 트리 생성
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.delete(7)
bst.delete(11)

bst.print_sorted_tree()
2
3
4
5
8
9
14
17
19

7. 이진 탐색 트리 높이 h 분석

  • 이진 탐색 트리의 높이:
    • Worst-case space complexity: O(n)
    • Best-case space complexity: O(log(n))
    • Average space complexity: O(log(n))

시간 복잡도 정리

  • 이진 탐색 트리 삽입, 탐색, 삭제
    • Worst-case time complexity: O(n)
    • Best-case time complexity: O(1)
    • Average time complexity: O(log(n))
    • Worst-case space complexity: O(n)

8. 이진 탐색 트리로 딕셔너리 구현하기

  • data에 key-value 값을 넣도록 정의하면 이진 탐색 트리로 딕셔너리를 구현할 수 있다.

이진 탐색 트리 딕셔너리 시간복잡도

  • key-value 쌍 삽입
    • Worst-case time complexity: O(n)
    • Best-case time complexity: O(1)
    • Average time complexity: O(log(n))
  • key를 이용한 노드 또는 value 탐색
    • Worst-case time complexity: O(n)
    • Best-case time complexity: O(1)
    • Average time complexity: O(log(n))
  • key-value 데이터 쌍 삭제
    • Worst-case time complexity: O(n)
    • Best-case time complexity: O(1)
    • Average time complexity: O(log(n))

해시 테이블과 비교

  • 세트나 딕셔너리의 삽입, 탐색, 삭제 모두 이진 탐색트리보다 해시 테이블을 사용하는 게 더 효율적이다.
  • 하지만 세트의 데이터나 딕셔너리의 key를 정렬된 상태로 사용하고 싶을 때는 이진 탐색 트리를 활용할 수 있다.

Feedback

  1. 이진 탐색 트리 연산의 시간, 공간 복잡도를 분석해보자.
  2. 언어별로 이진 탐색 트리를 구현해보자.
  3. 이진 탐색 트리로 추상 자료형을 구현해보자.

참고 자료

profile
Jeris
job's done
이전 포스트

힙

다음 포스트

[TIL] 04/18

0개의 댓글