트리, 이진탐색트리와 힙

핵심 요약

트리 용어와 순회, 이진탐색트리, 힙의 구조 및 연산을 비교한다.

본문

트리의 기본 용어

트리는 계층 관계를 표현하는 비선형 자료구조이다.

• 루트(root): 부모가 없는 최상위 노드
• 부모·자식·형제 노드
• 리프(leaf): 자식이 없는 노드
• 차수(degree): 노드의 자식 수
• 깊이(depth): 루트에서 해당 노드까지의 간선 수
• 높이(height): 해당 노드에서 가장 먼 리프까지의 간선 수
• 서브트리: 특정 노드를 루트로 하는 부분 트리

문제마다 루트의 레벨을 0 또는 1로 정의할 수 있으므로 정의를 확인해야 한다.

이진트리와 순회

이진트리는 각 노드의 자식 수가 최대 2개인 트리이다.

• 포화 이진트리: 모든 내부 노드가 자식 2개를 가지며 모든 리프의 깊이가 같다.
• 완전 이진트리: 마지막 레벨을 제외하고 모두 채워지고, 마지막 레벨은 왼쪽부터 채워진다.
• 편향 이진트리: 한 방향 자식만 이어진다.

깊이 우선 순회

전위: 루트→왼쪽 → 오른쪽중위: 왼쪽→루트 → 오른쪽후위: 왼쪽→오른쪽 → 루트

중위 순회는 이진탐색트리에서 키를 오름차순으로 출력한다.

이진탐색트리(BST)

각 노드에서 왼쪽 서브트리의 키는 노드보다 작고, 오른쪽 서브트리의 키는 노드보다 크다는 규칙을 사용한다. 평균적으로 탐색·삽입·삭제가 O(log n)이지만 트리가 한쪽으로 치우치면 O(n)이 된다.

삭제는 세 경우로 나뉜다.

1. 리프: 바로 제거한다.
2. 자식 하나: 자식을 부모와 연결한다.
3. 자식 둘: 중위 선행자 또는 중위 후속자의 값을 옮긴 뒤 해당 노드를 삭제한다.

힙

힙은 완전 이진트리이면서 부모와 자식 사이에 힙 순서를 만족한다.

• 최대 힙: 부모 키 ≥ 자식 키
• 최소 힙: 부모 키 ≤ 자식 키
• 루트만 전체 최댓값 또는 최솟값임이 보장된다. 형제나 같은 레벨의 정렬 순서는 보장되지 않는다.

배열 인덱스를 1부터 사용할 때 다음 관계가 성립한다.

부모: ⌊i/2⌋
왼쪽 자식: 2i
오른쪽 자식: 2i+1

삽입은 배열 끝에 넣고 위로 올리는 sift-up, 삭제는 루트를 제거하고 마지막 원소를 루트로 옮긴 뒤 아래로 내리는 sift-down을 수행한다. 삽입·삭제는 O(log n), 루트 확인은 O(1)이다.

BST와 힙 비교

이진트리의 수치 성질

루트를 레벨 0으로 둘 때 레벨 k의 최대 노드 수는 2^k, 높이 h인 포화 이진트리의 최대 노드 수는 2^(h+1)-1이다. 노드가 n개인 완전 이진트리의 높이는 ⌊log2 n⌋이다.

        8
      /   \
     4     12
    / \   / \
   2   6 10 14

위 트리는 BST이며 중위순회 결과는 2,4,6,8,10,12,14이다.

순회와 트리 복원

서로 다른 키를 가진 이진트리는 다음 조합으로 유일하게 복원할 수 있다.

• 전위 + 중위
• 후위 + 중위

전위와 후위만으로는 일반적으로 유일하지 않다. 전위의 첫 원소 또는 후위의 마지막 원소가 루트이며, 중위순회에서 루트 위치를 기준으로 왼쪽·오른쪽 서브트리를 나눈다.

BST 삭제 코드 흐름

자식이 둘인 노드는 오른쪽 서브트리의 최솟값인 중위 후속자를 이용할 수 있다.

def delete(root, key):
    if root is None:
        return None
    if key < root.key:
        root.left = delete(root.left, key)
    elif key > root.key:
        root.right = delete(root.right, key)
    else:
        if root.left is None: return root.right
        if root.right is None: return root.left
        succ = min_node(root.right)
        root.key = succ.key
        root.right = delete(root.right, succ.key)
    return root

균형이 보장되지 않는 BST는 정렬된 입력에서 연결 리스트처럼 편향될 수 있다. AVL·Red-Black Tree는 회전과 색·높이 규칙으로 높이를 O(log n)에 유지한다는 수준까지 구분한다.

힙 연산과 build-heap

최대 힙 배열(1-base): [ -, 90, 70, 60, 20, 50, 40 ]
                       90
                     /    \
                   70      60
                  /  \    /
                20   50  40

새 값 80을 끝에 넣으면 부모 60보다 크므로 교환하고, 루트 90보다는 작아 멈춘다. 루트 삭제 시 마지막 원소를 루트로 옮긴 뒤 더 큰 자식과 교환하며 내려간다.

원소를 하나씩 삽입해 힙을 만들면 O(n log n)이지만, 마지막 내부 노드부터 sift-down하는 bottom-up build-heap은 O(n)이다. 낮은 높이의 노드가 대부분이기 때문이다.

힙과 BST 선택

대표 선택 장면

작업 우선순위에서 가장 작은 키를 반복해서 꺼내야 하면 최소 힙이 적합하다. 힙의 루트는 최솟값이지만 배열 전체가 정렬된 것은 아니므로 중위 순회로 정렬 결과를 얻을 수 없다. 키 순서로 탐색과 범위 조회가 필요하면 이진탐색트리의 균형 여부까지 검토한다.