이진 트리: 자식은 많아야 둘

"노드마다 자식을 둘로 제한하면 재미있는 일이 벌어져. 모든 노드가 예 아니면 아니오를 묻는 갈림길이 되거든. 이 제약 하나에서 이진 탐색도, 힙도, 컴퓨팅 구조의 절반이 싹터."

모든 걸 여는 제약

이진 트리는 모든 노드가 자식을 많아야 둘까지만 갖는 트리야. 관례상 left와 right라고 부르지. 두 갈래 구조는 예/아니오 결정, 이진 탐색 트리, 힙 같은 걸 표현하기에 잘 맞아. 다만 자식이 둘이라는 사실만으로 탐색 공간이 절반씩 줄어드는 건 아니야. 키 순서에 대한 불변식과 균형이라는 조건이 붙어야 비로소 로그 탐색이 나와. 일반 트리든 이진 트리든 위계나 결정을 모델링할 수 있고, 결국 중요한 건 문제에 맞는 불변식을 세우는 거야.

모양의 어휘

이진 트리가 얼마나 빽빽하게 채워졌는지 묘사하는 형용사들이야. 앞으로 계속 듣게 될 거고.

full — 모든 노드의 자식이 0개 아니면 2개야. 1개인 노드는 없어.
complete — 마지막 레벨을 뺀 모든 레벨이 꽉 차 있고, 마지막 레벨은 왼쪽부터 차례로 채워져. 힙이 쓰는 모양이야.
perfect — 모든 레벨이 완전히 꽉 찬 상태. 빈틈없는 삼각형이지.
balanced — 높이가 log n 근처로 유지돼서 연산도 O(log n)에 머물러. 이 트랙이 내내 쫓는 성질이야.

하나를 저장하는 두 방법

같은 이진 트리를 두 가지 방식으로 표현할 수 있는데, 그 선택이 다음 트랙을 미리 보여줘.

연결 노드 — 노드 객체마다 left와 right 참조를 들고 있어. 유연하고 어떤 모양이든 담을 수 있어서 이게 기본이야.
배열 — complete 트리라면 포인터를 아예 없애고 노드를 배열에 담을 수 있어. 인덱스 산술로 오가면 되거든. 인덱스 i의 자식은 2i+1과 2i+2고 부모는 (i−1)//2야. 노드마다 자식 포인터를 둘 필요가 없고 캐시 지역성도 대체로 좋아. 힙이 만들어지는 방식이 정확히 이거니까 이 공식은 기억해 둬. 두 번만 더 넘기면 다시 만나.

이진 트리는 자식을 둘로 제한해서 모든 노드를 예/아니오 갈림길로 만들어. 이진 탐색과 힙의 씨앗이 여기 있지. 저장은 left/right 참조를 가진 연결 노드로 하거나, complete 트리라면 배열로 해. 배열에서는 인덱스 i의 자식이 2i+1과 2i+2야.

왜 높이가 모든 걸 좌우할까

노드가 n개인 이진 트리는 균형이 잡혀 덤불처럼 퍼지면 높이가 log₂(n) 근처까지 낮아지고, 노드마다 자식이 하나뿐인 사슬로 퇴화하면 n까지 치솟아. 트리 연산의 비용은 대부분 높이에 비례하니까, log n부터 n까지 벌어지는 이 범위가 빠른 트리와 느린 트리를 갈라놓는다고 봐도 돼. 높이를 log n 근처로 붙들어 두는 것, 그게 세 번만 더 넘기면 나올 균형 트리를 밀어붙이는 집착이고.

피파의 고백

나는 "이진"이 그냥 임의로 정한 규칙인 줄 알았어. 왜 셋도 넷도 아니고 둘이지? 아빠가 그걸 결정의 문제로 바꿔 놨어. "자식 둘이 질문 하나야. 왼쪽이냐 오른쪽. 작냐 크냐." 그러자 이진 트리가 제약이 아니라 절반씩 잘라내는 기계로 보이더라. 노드 하나하나가 가능성의 절반을 버리는 갈림길인 거지. 그 한마디가 내 머릿속에서 이진 트리와 이진 탐색을 이어 붙였어. 둘은 옷만 다르게 입은 같은 아이디어야.

Code

연결 노드와 배열 인덱스 트릭·python

class BinaryNode:
    """다들 쓰는 이진 트리 노드: 값, left, right."""
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

#        4
#       / \
#      2   6
#     / \
root = BinaryNode(4, BinaryNode(2, BinaryNode(1), BinaryNode(3)), BinaryNode(6))

def height(node):
    if node is None:
        return -1                    # 빈 서브트리: 높이 -1, 리프: 0
    return 1 + max(height(node.left), height(node.right))

print("height:", height(root))       # 2

# complete 이진 트리의 배열 표현 (포인터 없음!):
# i 의 부모 = (i-1)//2 . i 의 자식 = 2i+1, 2i+2.
arr = [4, 2, 6, 1, 3]                 # 같은 트리, 레벨별로
def children(i):
    return (2 * i + 1, 2 * i + 2)
print("children of index 0 (value 4):", [arr[j] for j in children(0)])  # [2, 6]
print("children of index 1 (value 2):", [arr[j] for j in children(1)])  # [1, 3]
# 이 인덱스 산술 기억해 — 정확히 힙이 작동하는 법 (두 lesson 앞).

Exercise

노드 7개를 이진 트리로 배치한다고 하자. 가능한 최소 높이, 그러니까 가장 덤불처럼 퍼진 배치는 얼마고, 가능한 최대 높이, 그러니까 가장 한쪽으로 쏠린 배치는 얼마일까? 그다음 트리 연산이 왜 대부분 높이에 좌우되는지, 그게 실전에서 어떤 모양을 원해야 하는지에 어떤 의미인지 설명해 봐.

Hint

최소 높이는 2야. 노드 7개짜리 perfect 트리는 레벨이 1개, 2개, 4개로 채워지거든. 최대 높이는 6이고, 한쪽으로만 이어진 사슬일 때야. 연산은 루트에서 리프까지 걸어 내려가니까 비용이 높이에 비례해. 그러니 높이가 log n인 덤불 모양을 원하지 높이가 n인 사슬을 원하진 않겠지.

모든 걸 여는 제약

모양의 어휘

하나를 저장하는 두 방법

왜 높이가 모든 걸 좌우할까

피파의 고백

Code

External links

Exercise

Progress

댓글 0