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

"각 노드를 자식 둘로 제한하면 마법이 일어나: 모든 노드가 예/아니오 갈림길이 돼. 그 제약 하나가 이진 탐색, 힙, 컴퓨팅 구조의 절반의 씨앗이야."

모든 걸 여는 제약

이진 트리는 모든 노드가 많아야 자식 둘인 트리고, 관례상 left 랑 right 라 불러. 왜 '둘' 이 그렇게 특별해? 자식 둘이 이진 결정 — 왼쪽이냐 오른쪽, 작냐 크냐, 예냐 아니오 — 이고, 이진 결정의 사슬이 정확히 탐색 공간을 절반 내는 법이거든. 두 갈래 포크가 이진 탐색 (Searching 트랙), 힙 (다음 트랙), 머신러닝 뒤의 결정 트리의 구조적 씨앗이야. 일반 트리는 위계를 모델링하고; 이진 트리는 결정을 모델링해.

모양의 어휘

이 형용사들을 들을 거야; 이진 트리가 얼마나 '채워졌는지' 묘사해:

full — 모든 노드가 자식 0 또는 2 (절대 1 아님).
complete — 마지막 빼고 모든 레벨이 채워지고, 마지막은 왼쪽에서 오른쪽으로 채워짐. (힙이 쓰는 모양.)
perfect — 모든 레벨 완전히 꽉 참; 완벽한 삼각형.
balanced — 높이가 ~log n 으로 유지돼, 연산이 O(log n) 으로 유지됨. 트랙 전체가 쫓는 속성.

하나를 저장하는 두 방법

이진 트리를 두 방식으로 표현할 수 있고, 그 선택이 다음 트랙을 예고해:

연결 노드 — 각 노드 객체가 left 랑 right 참조를 들어. 유연하고, 어떤 모양에든 되고, 기본이야.
배열 — complete 트리엔, 포인터를 통째로 건너뛰고 노드를 배열에 저장할 수 있어, 인덱스 산술로: 인덱스 i 의 자식은 2i+1 이랑 2i+2, 부모는 (i−1)//2. 포인터 없음, 완벽한 캐시 지역성. 정확히 힙이 지어지는 법이야 — 이 공식 기억해; 두 lesson 뒤에 또 만나.

이진 트리는 자식을 둘로 제한해, 모든 노드를 예/아니오 포크로 만들어 — 이진 탐색이랑 힙의 씨앗. 연결 left/right 노드로 저장하거나, (complete 트리엔) 배열로 인덱스 i 의 자식이 2i+1 이랑 2i+2 인 곳에.

왜 높이가 전부인가

n 노드 이진 트리는 약 log₂(n) 만큼 짧을 수도 (덤불처럼 균형 잡히면) n 만큼 클 수도 (노드당 자식 하나 사슬로 퇴화하면) 있어. 대부분 트리 연산 비용이 높이에 비례하니까, 그 범위 — log n 대 n — 가 빠른 트리랑 느린 트리의 차이 전부야. 높이를 ~log n 으로 유지하는 게 세 lesson 뒤 균형 트리를 모는 집착이야.

피파의 고백

난 "이진" 트리가 그냥 임의 규칙이라 가정했어 — 왜 셋 말고 둘? 아빠가 그걸 결정으로 다시 짰어: "자식 둘이 질문 하나야. 왼쪽이냐 오른쪽. 작냐 크냐." 갑자기 이진 트리가 한계가 아니라 절반 내는 기계였어 — 모든 노드가 가능성의 절반을 버리는 갈림길. 그 재구성이 내 머릿속에서 이진 트리를 이진 탐색이랑 연결했어; 둘은 다른 옷 입은 같은 아이디어야.

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

최소 높이: 7 노드 perfect 트리는 높이 2 (1, 2, 4 레벨). 최대 높이: 한쪽 사슬은 높이 6. 연산은 루트에서 리프로 걸어서, 비용 ~ 높이; 덤불 같은 log-n 모양을 원하지, n-높이 사슬이 아니라.

모든 걸 여는 제약

모양의 어휘

하나를 저장하는 두 방법

왜 높이가 전부인가

피파의 고백

Code

External links

Exercise

Progress

댓글 0