Trees

  배열, 링크드리스트 같은 linear 자료구조는 "앞-뒤" 관계만 표현할 수 있다. 트리는 계층적(hierarchical) 관계를 표현할 수 있는 첫 번째 nonlinear 자료구조다. 파일 시스템, 데이터베이스, GUI 등 실제로 굉장히 많은 곳에 쓰인다.

---

1. 용어 정리

        A          ← level 0
       / \
      B   C        ← level 1
         / \
        D   E      ← level 2
           / \
          F   G    ← level 3

용어	설명	예시
Root	트리의 최상단 노드. 부모가 없다	A
Leaf / External node	자식이 없는 노드	B, D, F, G
Internal node	자식이 있는 노드	A, C, E
Sibling	같은 부모를 가진 노드	B와 C
Ancestor	위로 올라가는 모든 노드	G의 ancestor = E, C, A
Descendant	아래로 내려가는 모든 노드	C의 descendant = D, E, F, G
Level / Depth	root에서 해당 노드까지의 거리. root = level 0	G의 level = 3
Height	트리 전체에서 가장 큰 level	위 트리의 height = 3
Degree	해당 노드의 자식 수	C의 degree = 2

---

2. Binary Tree

  모든 노드가 최대 2개의 자식을 가지는 트리. 자식은 왼쪽(left child)과 오른쪽(right child)으로 구분된다.

• Proper binary tree: 모든 노드가 자식을 0개 또는 2개 가짐
• Improper binary tree: 자식이 1개인 노드가 존재

    Proper          Improper
      A                A
     / \              / \
    B   C            B   C
   / \                \
  D   E                D

Properties

  n개의 노드, nE개의 외부 노드, nI개의 내부 노드, height h인 binary tree T에 대해:

항목	범위	최솟값 이유	최댓값 이유
n	h+1 ≤ n ≤ 2^(h+1)-1	한쪽으로만 치우친 트리	모든 레벨이 꽉 찬 트리
nE	1 ≤ nE ≤ 2^h	root만 있는 트리	level h의 노드가 전부 leaf
h	log(n+1)-1 ≤ h ≤ n-1	균형잡힌 full binary tree	한쪽 자식만 있는 트리

---

3. 구현 방법

Linked Structure

  각 노드가 element, parent, left child, right child를 저장하는 포인터를 가진다.

[ parent | element | left | right ]

Array-Based (Level Numbering)

  노드의 위치를 index로 표현한다. root의 index = 0.

• 왼쪽 자식: 2f(p) + 1
• 오른쪽 자식: 2f(p) + 2
• 부모: ⌊(f(p) - 1) / 2⌋

        A(0)
       /    \
     B(1)   C(2)
    /    \
  D(3)   E(4)

	Linked	Array-Based
장점	메모리 효율적, 삽입/삭제 O(1)	부모/자식 접근이 산술 계산으로 O(1)
단점	포인터 overhead	치우친 트리일수록 메모리 낭비, 삽입/삭제 O(n)

 
트리의 operations는 크게 두 가지로 나뉜다.

Accessor Methods (트리를 변경하지 않음)

Method	설명
T.root()	root 노드 반환
T.parent(p)	p의 부모 반환
T.children(p)	p의 자식들 반환
T.num_children(p)	p의 자식 수 반환
T.is_root(p)	p가 root인지 확인
T.is_leaf(p)	p가 leaf인지 확인
len(T)	노드 수 반환
T.is_empty()	트리가 비어있는지 확인

Update Methods (트리를 변경함) — Binary Tree 전용

Method	설명
T.add_root(e)	빈 트리에 root 추가
T.add_left(p, e)	p의 왼쪽 자식 추가
T.add_right(p, e)	p의 오른쪽 자식 추가
T.replace(p, e)	p의 element를 e로 교체
T.delete(p)	p 삭제 (자식이 2개면 불가)
T.attach(p, T1, T2)	leaf p에 T1, T2를 왼쪽/오른쪽 서브트리로 붙임

Time Complexity

Operation	Running Time
len, is_empty	O(1)
root, parent, left, right, children, num_children	O(1)
is_root, is_leaf	O(1)
depth(p)	O(d+1)
height	O(n)
add_root, add_left, add_right, replace, delete, attach	O(1)

  대부분이 O(1)인 이유는 각 노드가 parent, left child, right child를 직접 포인터로 저장하고 있어서 바로 접근이 가능하기 때문이다. depth는 root까지 올라가야 하고, height는 모든 노드를 확인해야 해서 예외적으로 더 걸린다.

---

4. Traversal

  트리의 모든 노드를 방문하는 방법. 목적에 따라 순서가 달라진다.

Preorder — 부모 → 왼쪽 → 오른쪽

부모를 먼저 방문한다. 목차처럼 구조를 순서대로 출력할 때 적합하다.

Postorder — 왼쪽 → 오른쪽 → 부모

자식을 먼저 방문한다. 사칙연산 트리에서 값을 계산할 때처럼, 자식의 결과가 있어야 부모를 처리할 수 있을 때 적합하다.

Inorder — 왼쪽 → 부모 → 오른쪽 (binary tree 전용)

왼쪽 서브트리 → 루트 → 오른쪽 서브트리 순으로 방문한다. BST(binary search tree)에서 inorder traversal을 하면 오름차순 정렬된 결과가 나온다.

Breadth-First (BFS) — 레벨 순서대로

같은 레벨을 전부 방문한 뒤 다음 레벨로 내려간다. 재귀가 아닌 Queue로 구현한다.

각 노드를 방문할 때 그 자식들을 Queue에 넣어두면, 현재 레벨을 다 처리한 뒤 자연스럽게 다음 레벨로 넘어간다.

Algorithm breadthfirst(T):
    Q.enqueue(T.root())
    while Q not empty:
        p = Q.dequeue()
        visit p
        for each child c of p:
            Q.enqueue(c)

게임 트리처럼 "앞으로 h수 안에 가능한 모든 경우의 수"를 탐색할 때 유용하다.

---

5. Binary Search Tree (BST)

BST는 binary tree에 다음 조건을 추가한 것이다:

• 왼쪽 서브트리의 모든 값 < root
• 오른쪽 서브트리의 모든 값 > root

        13
       /  \
      9   20
     / \  / \
    3  10 19 23

이 조건 덕분에 inorder traversal을 하면 항상 정렬된 순서로 출력된다.

삭제

• Leaf 삭제: 그냥 제거
• 자식이 1개: 해당 노드를 자식으로 대체
• 자식이 2개: 왼쪽 서브트리의 최댓값 또는 오른쪽 서브트리의 최솟값으로 대체
  • 최솟값 찾기: 오른쪽 서브트리에서 왼쪽으로 계속 내려가면 된다

Time Complexity

Operation	Sorted Array	BST
Search	O(log n)	O(h)
Insert	O(n)	O(h)
Delete	O(n)	O(h)

  BST의 h는 log(n+1)-1 ≤ h ≤ n-1이다. 트리가 균형잡혀 있으면 h ≈ log n이라 sorted array보다 삽입/삭제가 훨씬 빠르지만, 한쪽으로 치우치면 h = n-1이 되어 O(n)으로 나빠진다. 이를 해결하려면 트리의 균형을 유지해야 한다 → Chapter 11에서 다룸.

---

6. 정리

  트리는 단순히 빠른 자료구조가 아니다. 데이터가 가진 계층적 관계 자체를 표현하기 위한 구조다. BST처럼 순서 관계를 트리 구조에 얹으면, 삽입/삭제가 O(n)인 sorted array의 한계를 넘을 수 있다.