트리, 이진탐색트리와 힙

1. 트리의 기본 용어

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

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

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

2. 이진트리와 순회

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

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

깊이 우선 순회

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

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

3. 이진탐색트리(BST)

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

삭제는 세 경우로 나뉜다.

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

4. 힙

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

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

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

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

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

5. BST와 힙 비교

6. 이진트리의 수치 성질

루트를 레벨 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이다.

7. 순회와 트리 복원

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

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

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

8. 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)에 유지한다는 수준까지 구분한다.

9. 힙 연산과 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)이다. 낮은 높이의 노드가 대부분이기 때문이다.

10. 힙과 BST 선택

최종 확인 문제

1. 루트를 레벨 0으로 할 때 높이 4인 포화 이진트리의 최대 노드 수를 구하시오.
2. 전위순회 M,F,C,H,T,R,Z, 중위순회 C,F,H,M,R,T,Z에서 루트와 오른쪽 서브트리의 루트를 구하시오.
3. 1-base 최대 힙 [90,70,60,20,50,40]에 80을 삽입한 뒤 배열 순서를 쓰시오.
4. bottom-up build-heap이 O(n)인 핵심 이유를 설명하시오.
5. 균형 BST와 최대 힙에서 키 45의 존재 여부 탐색 복잡도를 비교하시오.