트리란?

▷ 트리는 일반적으로 대상 정보의 각 항목들을 계층적으로 연관되도록 구조화시키고자 할 때 사용하는 비선형 자료구조이다.

▶ 데이터 요소들의 단순한 나열이 아닌 부모-자식 관계의 계층적 구조로 표현이 된다. 트리는 그래프의 한 종류이며 사이클이 없다.

트리와 관련된 용어

▷ 루트 노드(root node) : 부모가 없는 노드, 트리는 하나의 루트 노드만을 가진다.

▶ 노드(node) : 트리를 구성하고 있는 각 요소

▷ 간선(edge) : 노드를 연결하는 선(link, branch 라고도 부름)

▶ 형제(sibling) : 같은 부모를 가지는 노드

▷ 노드의 레벨(level) : 트리의 특정 깊이를 가지는 노드의 집합

▶ 노드의 차수(degree) : 하위 트리 개수 / 간선 수(degree) = 각 노드가 지닌 가지의 수

트리의 종류

이진 트리🎄🌲(Binary Tree)

⊙ 각 노드가 최대 두 개의 자식을 갖는 트리
⊙ 모든 트리가 이진 트리는 아니다.
⊙ 이진트리는 완전 이진 트리(Complete Binary Tree)와 포화 이진 트리(Perfect Binary Tree), 전 이진 트리(Full Binary Tree)라고 하는 특별한 트리 구조를 정의할 수 있다.

🎄 완전 이진 트리(Complete Binary Tree)

⊙ 트리의 모든 높이에서 노드가 꽉 차 있는 이진 트리. 즉, 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있다.
⊙ 마지막 레벨은 꽉 차 있지 않아도 되지만 노드가 왼쪽에서 오른쪽으로 채워져야 한다.

🌲 전 이진 트리(Full Binary Tree or Strictly Binary Tree)

⊙ 모든 노드가 0개 또는 2개의 자식 노드를 갖는 트리

🌳 포화 이진 트리(Perfect Binary Tree)

⊙ 모든 레벨에 노드가 차있는 상태로 최대 노드 수인 2^k-1개로 채워져 있는 트리
⊙ 전 이진 트리이면서 완전 이진 트리인 경우

🔎 이진 트리 순회

a. 중위 순회(in-order traversal) : 왼쪽 가지 -> 현재 노드(루트) -> 오른쪽 가지

def inorder(node) :
    if node.left != None :
        inorder(tree[node.left])
    print(node.item, end = ' ')
    if node.right != None :
        inorder(tree[node.right])

b. 전위 순회(pre-order traversal) : 현재 노드(루트) -> 왼쪽 가지 -> 오른쪽 가지

def preorder(node) :
    print(node.item, end = ' ')
    if node.left != None :
        inorder(tree[node.left])
    if node.right != None :
        inorder(tree[node.right])

c. 후위 순회(post-order traversal) : 왼쪽 가지 -> 오른쪽 가지 -> 현재 노드(루트)

def postorder(node) :
    if node.left != None :
        inorder(tree[node.left])
    if node.right != None :
        inorder(tree[node.right])
    print(node.item, end = ' ')

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

모든 노드가 자신의 왼쪽 서브트리에는 현재노드보다 작은 키값이, 오른쪽 서브트리에는 현재 노드보다 큰 값이 오는 규칙을 만족하는 이진트리이다.

📌 모든 왼쪽 자식들 <= n < 모든 오른쪽 자식들 (모든 노드 n에 대해서 반드시 참)

힙(heap)

🔑 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조이다.
여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조이다.

📍 트리의 마지막 단계에서 오른쪽 부분을 뺀 나머지 부분이 가득 채워져 있는 완전 이진 트리이다.

최소 힙(min heap)
부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리
key(부모 노드) <= key(자식 노드)

최대 힙(max heap)
부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리
key(부모 노드) >= key(자식 노드)

MAX - Heapify
트리의 전체 모양은 complete binary tree이다. 왼쪽 부트리(subtree)는 그 자체로 heap이고, 오른쪽 부트리(subtree)도 그 자체로 heap일 때 유일하게 루트만이 heap property를 만족하지 않을 때 heap property를 만족하도록 만들어주는 것이다.
⭐ 방법 : 두 자식들 중 더 큰 쪽과 exchange 한다. 이걸 반복하면 된다.

💥 heap sort

1. 주어진 데이터로 힙을 만든다

2. 힙에서 최대값(루트)을 가장 마지막 값과 바꾼다

3. 힙의 크기가 1 줄어든 것으로 간주한다. 즉, 가장 마지막 값은 힙의 일부가 아닌 것으로 간주한다

4. 루트 노드에 대해서 Heapify(1)한다

5. 2~4번을 반복한다

🔥 완전 이진 트리, 이진 탐색 트리, heap의 정의를 정확히 알아두고 헷갈리지 않도록 하자! 🔥