이진 트리(Binary Tree) 순회와 이진 힙(Binary Heap) 메커니즘

**이진 트리(Binary Tree)**는 각 노드가 최대 2개의 자식 노드를 가지는 계층적 비선형 자료구조입니다. **이진 힙(Binary Heap)**은 완전 이진 트리 구조를 활용해 최댓값이나 최솟값을 $O(log N)$에 찾는 최적 자료구조입니다.

1. 이진 트리 노드 및 순회 (Preorder, Inorder, Postorder, Levelorder)

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

# 전위 순회 (V -> L -> R)
def preorder(n):
    if n:
        print(n.item, end=' ')
        preorder(n.left)
        preorder(n.right)

# 레벨 순회 (Queue 활용)
from collections import deque
def levelorder(root):
    q = deque([root])
    while q:
        n = q.popleft()
        if n:
            print(n.item, end=' ')
            q.append(n.left)
            q.append(n.right)

2. 이진 힙 (Binary Heap) 메커니즘

이진 힙은 배열(List)로 효율적으로 표현됩니다.

• 부모 노드 인덱스: i // 2
• 왼쪽 자식 인덱스: 2 * i
• 오른쪽 자식 인덱스: 2 * i + 1

class BHeap:
    def __init__(self, a):
        self.a = a  # [None] + 데이터
        self.N = len(a) - 1

    def create_heap(self):
        for i in range(self.N // 2, 0, -1):
            self.downheap(i)

    def insert(self, key):
        self.a.append(key)
        self.N += 1
        self.upheap(self.N)

    def upheap(self, j):
        while j > 1 and self.a[j // 2] > self.a[j]: # 최소 힙 조건
            self.a[j // 2], self.a[j] = self.a[j], self.a[j // 2]
            j = j // 2

    def delete_min(self):
        if self.N == 0:
            return None
        minimum = self.a[1]
        self.a[1] = self.a[self.N]
        self.a.pop()
        self.N -= 1
        self.downheap(1)
        return minimum

    def downheap(self, i):
        while 2 * i <= self.N:
            k = 2 * i
            if k < self.N and self.a[k] > self.a[k + 1]:
                k += 1
            if self.a[i] <= self.a[k]:
                break
            self.a[i], self.a[k] = self.a[k], self.a[i]
            i = k

3. 이진 힙 연산 복잡도 정리

4. 자주 묻는 질문 (Q&A)

Q. 힙 생성(Build Heap)이 $O(N log N)$이 아니라 $O(N)$인 이유는? A. 아래쪽 레벨의 노드 수(전체의 절반)는 높이가 0이어서 이동하지 않고, 위로 올라갈수록 노드 수($N/2^h$)는 절반으로 줄어듭니다. 이를 급수 계산하면 $sum (h / 2^h) = 2$가 되어 전체 연산량이 $O(N)$으로 수렴합니다.