5. Tree (3) - Types of Binary Trees

Types of Binary Trees (이진 트리의 종류)

 어떤 상황에서 어떤 트리를 쓰면 좋을까?

---

1.  Threaded Binary Tree (스레드 이진 트리)

일반 이진 트리에서는 대부분의 NULL 포인터(자식이 없는 포인터)가 많음.
이 NULL 포인터들을 이용해서 트리 순회를 쉽게 할 수 있도록 만든 구조가 스레드 이진 트리(Threaded Binary Tree)

 

예를 들어, 중위 순회를 할 때 재귀나 스택 없이 ‘다음 노드(next inorder)’ 로 바로 이동할 수 있음.

 

구조

각 노드는 왼쪽/오른쪽 포인터 외에 그 포인터가 자식인지, 스레드인지 구분하는 플래그를 가짐.

typedef struct ThreadedNode {
    int data;
    struct ThreadedNode* left;
    struct ThreadedNode* right;
    int lthread; // 왼쪽이 자식(0)인지 스레드(1)인지 표시
    int rthread; // 오른쪽도 동일
} ThreadedNode;

 

작동 원리

• 노드의 왼쪽 스레드: 해당 노드의 중위 순회 시 바로 이전 노드
• 노드의 오른쪽 스레드: 해당 노드의 중위 순회 시 바로 다음 노드

 => 이 구조 덕분에 스택 없이 순회 가능 + 메모리 낭비 줄이고, 순회 속도 향상.

장점	단점
스택이나 재귀 호출 없이 순회 가능 NULL 포인터를 효율적으로 활용 중위 순회가 매우 빠름	구현 복잡 삽입/삭제 시 스레드 재연결 필요

---

2.  Heap (힙)

힙은 완전 이진 트리(Complete Binary Tree) 기반의 구조로,

부모 노드의 키 값이 자식보다 크거나 작도록 정렬된 형태임.

종류	조건
Max Heap	부모 ≥ 자식
Min Heap	부모 ≤ 자식

힙은 우선순위 큐(Priority Queue) 구현에 자주 사용됨.

 

특징

• 완전 이진 트리이므로 배열로 표현하기에 적합
• 인덱스 관계:
• 왼쪽 자식 = 2 * i 오른쪽 자식 = 2 * i + 1 부모 = i / 2
• 삽입과 삭제 모두 O(log n)

 

Heap 삽입 (Insertion)

1. 트리의 마지막 위치에 노드 삽입
2. 부모 노드와 비교하여 Heap 속성 위반 시 교환 (heapify-up)

 

Heap 삭제 (Deletion)

1. 루트 노드(최댓값 or 최솟값) 제거
2. 마지막 노드를 루트로 올리고
3. Heap 속성이 유지되도록 아래로 교환 (heapify-down)

->  정렬에 활용하면 Heap Sort 알고리즘이 됨.

---

3.  Binary Search Tree (BST, 이진 탐색 트리)

모든 왼쪽 서브트리의 값 < 루트 < 오른쪽 서브트리의 값을 만족하는 트리 구조.

        8
       / \
      3   10
     / \    \
    1   6    14
       / \   /
      4  7  13

-> 중위 순회하면 항상 오름차순 정렬 결과가 나옴.

 

 1) 탐색 (Search)

TreeNode* search(TreeNode* root, int key) {
    if (root == NULL || root->data == key) return root;
    if (key < root->data)
        return search(root->left, key);
    else
        return search(root->right, key);
}

시간복잡도 : 평균 O(log n) / 최악(편향 트리) O(n)

 

 2) 삽입 (Insertion)

TreeNode* insert(TreeNode* root, int key) {
    if (root == NULL) {
        TreeNode* node = malloc(sizeof(TreeNode));
        node->data = key;
        node->left = node->right = NULL;
        return node;
    }
    if (key < root->data)
        root->left = insert(root->left, key);
    else if (key > root->data)
        root->right = insert(root->right, key);
    return root;
}

 

 3) 삭제 (Deletion)

삭제할 노드의 자식 수에 따라 3가지 경우로 나눔:

1. 자식 없음(leaf) → 바로 삭제
2. 자식 1개 → 부모가 자식과 직접 연결
3. 자식 2개 → 오른쪽 서브트리의 최소값으로 교체

=> 구조 유지가 중요하므로 단순 삭제보다 재배열(logic) 이 핵심

 

BST의 단점

삽입 순서에 따라 편향 트리(skewed tree) 가 될 수 있음
(예: 정렬된 데이터 순서로 삽입 시 한쪽으로 쏠림 → O(n))

=> 이를 보완하기 위해 등장한 것이 AVL Tree

---

4.  AVL Tree (균형 이진 탐색 트리)

AVL 트리는 높이 균형(height-balanced) 을 유지하는 BST의 확장형임.
모든 노드에 대해

  |왼쪽 서브트리 높이 - 오른쪽 서브트리 높이| ≤ 1

을 만족함.

=> 삽입/삭제 시 자동으로 회전(rotation) 을 수행해 균형 유지.

 

회전의 종류

상황	회전 방법
Left-Left (LL)	Right Rotation
Right-Right (RR)	Left Rotation
Left-Right (LR)	Left → Right Rotation
Right-Left (RL)	Right → Left Rotation

 

예시

삽입 순서: 30 → 20 → 10

• 일반 BST로는 한쪽으로 치우친 트리:
• 30 / 20 / 10
• AVL 트리는 자동으로 Right Rotation 수행:
• 20 / \ 10 30

=> 균형 유지로 탐색, 삽입, 삭제 모두 O(log n) 보장

---

 정리

트리 종류	특징	장점	단점
Threaded Binary Tree	NULL 포인터 활용, 빠른 중위 순회	순회 빠름, 메모리 효율 ↑	삽입/삭제 복잡
Heap	완전 이진 트리 기반, 부모-자식 규칙	O(log n) 삽입/삭제, PQ 구현	탐색에는 부적합
BST	정렬된 탐색 구조	탐색 빠름(평균 O(log n))	편향 시 성능 저하
AVL Tree	균형 유지 BST	항상 O(log n) 보장	회전 연산 복잡