[Python/코테] 이진검색 트리, 힙 - 개념

트리

• 계층적인 구조를 표현할 떄 사용할 수 있는 자료 구조
• 기본적으로 트리의 크기가 N일 때, 전체 간선의 개수는 N - 1이다.

이진검색트리

• 왼쪽 서브트리의 모든 값은 부모의 값보다 작고, 오른쪽 서브트리의 모든 값은 부모의 값보다 큰 이진 트리 (왼쪽 < 부모 < 오른쪽)
• 배열, 연결리스트 대신 이진검색트리를 사용하는 이유는, insert, erase, find, update 등의 연산을 $O(lg N)$에 수행할 수 있기 때문
• 해시에 없는 이진검색트리의 장점은, 원소가 크기 순으로 정렬되어 있다는 것이다.
• 즉, 삽입/삭제/수정 등의 연산이 빈번하고 원소 간의 대소와 관연한 성질이 필요할 경우 이진검색트리를 사용한다.

이진 검색 트리에서의 삽입, 검색, 삭제는 높이가 $lgN$인 경우, 시간 복잡도는 $O(lgN)$이지만, 높이가 N인 경우 시간 복잡도가 $O(N)$이 된다. 그렇기 때문에 트리의 편향을 해결해 주어야 트리를 사용하는 의미가 있어진다.

• 자가 균형 트리(Self-balancing Binary Tree): 트리에서 노드의 삽입과 삭제 같은 연산이 일어날 때 자동으로 균형 트리를 유지하여 편향성을 해소해주는 트리. ex) AVL 트리, Red Black 트리
• 완전 이진 트리(Complete Binary Tree): 마지막 노드를 제외하고 모든 노드의 자식이 0이며 마지막 레벨의 노드는 왼쪽에 채워져 있는 형태. 루트 노드부터 시작해서 왼쪽 자식, 오른쪽 자식 순서대로 데이터가 삽입되는 트리.

완전 이진 트리

Find 과정

1. 루트 노드부터 방문하여 탐색을 진행한다.
2. 현재 노드와 값을 비교한다.
3. 현재 노드가 찾으려는 값보다 작으면 오른쪽으로, 크면 왼쪽으로 이동하여 비교한다.

https://hunseop2772.tistory.com/174

트리의 순회

• 트리 자료구조에 포함된 노드를 특정한 방법으로 한 번씩 방문하는 방법으로, 트리 정보를 시각적으로 확인할 수 있다.
• 대표적으로 전위 순회(루트 먼저 방문), 중위 순회(왼쪽 자식 방문 뒤 루트 방문), 후위 순회(오른쪽 자식 방문 뒤 루트 방문)이 있다.

구현 예제 (by Python)

출처: https://dkssud8150.github.io/posts/codingtestbina/

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

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

    # 전위 순회
    def preorder(self, n):
        if n != None:
            print(n.data, ' ', end=' ')
            if n.left:
                self.preorder(n.left)
            if n.right:
                self.preorder(n.right)

    def inorder(self, n):
        if n != None:
            if n.left:
                self.inorder(n.left)
            print(n.data, ' ', end='')
            if n.right:
                self.inorder(n.right)

    def postorder(self, n):
        if n != None:
            if n.left:
                self.postorder(n.left)
            if n.right:
                self.postorder(n.right)
            print(n.data, ' ', end='')

    # 트리의 높이
    def height(self, root):
        if root == None:
            return 0
        return max(self.height(root.left), self.height(root.height)) + 1

tree = BinaryTree()
n1 = Node(10)
n2 = Node(20)
n3 = Node(30)
n4 = Node(40)
n5 = Node(50)
n6 = Node(60)
n7 = Node(70)
n8 = Node(80)

tree.root = n1
n1.left = n2
n1.right = n3
n2.left = n4
n2.right = n5
n3.left = n6
n3.right = n7
n4.left = n8

print('트리 높이: {}\n전위순회: {}\n중위순회: {}\n후위순회: {}'.format(
    tree.height(tree.root),         # 트리 높이: 4
    tree.preorder(tree.root),       # 전위 순회: 10 20 40 80 50 30 60 70
    tree.inorder(tree.root),        # 중위 순회: 20 40 80 50 10 30 60 70
    tree.postorder(tree.order),     # 후위 순회: 20 40 80 50 30 60 70 10
))

---

힙 (Heap) 자료구조

C++과 달리 파이썬에서 이진 트리를 지원하는 라이브러리를 찾지 못했다. 대신 heapq라는 라이브러리를 사용하므로 힙 자료구조에 대해 간략하게 알아보자.

• 힙은 자식 노드들이 특정한 성질을 가지고 정렬된 완전 이진 트리(Complete Binary Tree)이다.
• 마지막 노드를 제외하고 모든 노드의 자식이 0이며 마지막 레벨의 노드는 왼쪽에 채워져 있는 형태를 말한다.
• 항상 루트 노드를 제거한다. (ex. 제거 시, 루트 노드 제거)
• 우선순위 큐의 구현에 많이 쓰이는 구조이다.

종류

• 최대 힙(max heap)
  : 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리. 루트 노트가 최대값이다.
• 최소 힙(min heap)
  : 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리. 루트 노드가 최소값이다.

https://wonit.tistory.com, https://nobilitycat.tistory.com

 

heapq 라이브러리

파이썬 라이브러리

최소힙만 지원하여 최대힙은 따로 구현해야 한다.

---

출처:
https://blog.encrypted.gg/1013

[실전 알고리즘] 0x16강 - 이진 검색 트리

https://www.youtube.com/watch?v=i5yHkP1jQmo

https://lgphone.tistory.com/90

13-2. 이진 탐색 트리와 자가 균형 이진 탐색 트리 (Binary Search Tree and Self-balancing Binary Tree): 파이썬

https://nobilitycat.tistory.com/entry/%ED%9E%99Heap%EA%B3%BC-%EC%99%84%EC%A0%84-%EC%9D%B4%EC%A7%84-%ED%8A%B8%EB%A6%ACComplete-binary-tree

힙(Heap)과 완전 이진 트리(Complete binary tree)

https://velog.io/@jinh2352/%ED%9E%99Heap-%EC%99%84%EC%A0%84-%EC%9D%B4%EC%A7%84-%ED%8A%B8%EB%A6%AC-%EA%B8%B0%EB%B0%98%EC%9D%98-%EC%B5%9C%EB%8C%80%EC%B5%9C%EC%86%8C-%ED%9E%99

[힙(Heap), 힙 트리] 완전 이진 트리 기반의 최대/최소 힙