1. 업다운 게임 (Up & Down Game)

친구와 1부터 100 사이 숫자를 맞추는 게임을 한다고 상상해 봅시다. 정답은 70입니다.

멍청한 전략 (Linear Search - 선형 탐색)

가장 단순무식한 방법은 1부터 차례대로 물어보는 것입니다. "1이야?" "아니." "2야?" "아니." ... "69야?" "아니." "70이야?" "정답!" 최악의 경우 100번을 물어봐야 합니다. 시간 복잡도는 O(N)입니다. 데이터가 100만 개라면 100만 번 확인해야 합니다. 만약 데이터베이스가 이렇다면 여러분은 로그인 한번 할 때마다 1분씩 기다려야 할 겁니다.

똑똑한 전략 (Binary Search - 이진 탐색)

가운데를 찌릅니다.

1. "50보다 커?" (Yes) -> 150 버림. 남은 건 51100. (50개 남음)
2. "75보다 커?" (No) -> 76100 버림. 남은 건 5175. (25개 남음)
3. "62보다 커?" ...

이렇게 한 번 물어볼 때마다 범위를 절반씩 줄여나가면, 100개의 데이터도 단 7번 만에 맞출 수 있습니다 ($2^7 = 128$). 100만 개의 데이터도 20번이면 찾습니다 ($2^ \approx 1,000,000$). 이 시간 복잡도는 O(log N)입니다. 이 전략을 그대로 데이터 구조로 구현한 것이 바로 이진 탐색 트리(BST)입니다.

---

2. BST의 황금 규칙 3가지

이진 탐색 트리는 다음 규칙을 엄격하게 지키는 트리입니다.

1. 왼쪽 자식(Left Child)은 부모보다 작다. ($L < P$)
2. 오른쪽 자식(Right Child)은 부모보다 크다. ($R > P$)
3. 중복된 값은 없다 (기본적으로). (만약 중복이 필요하면 카운트를 올리거나 리스트로 저장하거나, 오른쪽 서브트리로 보냅니다).

이 규칙 덕분에 검색 로직이 단순해집니다. "찾는 값이 현재 노드(70)보다 작네(50)? 그럼 오른쪽은 볼 필요도 없어. 왼쪽으로 가!" 한 번 움직일 때마다 검색 대상이 절반으로 줄어듭니다.

---

3. 주요 연산과 구현 (Python & Java)

3.1. 노드 구조

Python

class Node:
    def __init__(self, key):
        self.val = key
        self.left = None
        self.right = None

3.2. 검색 (Search)

Python

def search(root, key):
    # Base Case: 못 찾았거나, 찾았거나
    if root is None or root.val == key:
        return root
    
    # 찾는 값이 현재보다 작으면 왼쪽으로
    if key < root.val:
        return search(root.left, key)
    
    # 크면 오른쪽으로
    return search(root.right, key)

재귀(Recursion)를 사용하면 코드가 매우 직관적입니다. 시간 복잡도: $O(h)$ (트리의 높이).

3.3. 삽입 (Insertion)

검색과 똑같이 따라가다가, Null(없는 곳)을 만나면 거기에 새 노드를 집어넣습니다. 이미 있는 값이면? 무시하거나 에러를 내거나 카운트를 증가시킵니다.

3.4. 삭제 (Deletion) - 가장 복잡함

노드를 지울 때는 신중해야 합니다. 자식들이 미아가 되면 안 되니까요. 세 가지 케이스를 다뤄야 합니다.

1. 자식이 없는 경우 (Leaf Node):
   • 그냥 삭제하면 됩니다. 부모의 링크를 Null로 바꿉니다.
2. 자식이 하나인 경우:
   • 내 자식을 내 부모에게 입양시키고 떠납니다. (링크 연결만 바꿔줌).
   • Linked List 삭제와 비슷합니다.
3. 자식이 둘인 경우:
   • 가장 중요한 케이스입니다.
   • 누군가 내 빈자리를 채워야 트리가 유지됩니다.
   • 오른쪽 서브트리에서 가장 작은 값 (In-order Successor)을 찾아옵니다. (또는 왼쪽에서 가장 큰 값).
   • 내 자리에 그 값을 덮어씌웁니다.
   • 그리고 그 값을 원래 가지고 있던 노드를 삭제합니다(재귀적으로).

def delete_node(root, key):
    if not root: return root
    
    if key < root.val:
        root.left = delete_node(root.left, key)
    elif key > root.val:
        root.right = delete_node(root.right, key)
    else:
        # 찾았다! 지우자.
        if not root.left: return root.right # 자식 하나 or 0
        if not root.right: return root.left
        
        # 자식 둘: Successor 찾기
        temp = find_min(root.right)
        root.val = temp.val
        root.right = delete_node(root.right, temp.val)
        
    return root

---

4. 구현 디테일 - 재귀(Recursive) vs 반복(Iterative)

많은 교과서가 재귀로 BST를 설명하지만, 실제나 성능이 중요한 환경에서는 반복문(Iterative)을 선호합니다. 재귀는 함수 호출 오버헤드와 스택 메모리를 소모하기 때문입니다.

Iterative Search 예시 (Python)

def search_iterative(root, key):
    current = root
    while current:
        if key == current.val:
            return current
        elif key < current.val:
            current = current.left
        else:
            current = current.right
    return None

이 방식은 공간 복잡도가 O(1)입니다. 재귀는 O(h)죠. 트리 높이가 10만이라도 스택 오버플로우 걱정이 없습니다. 실무에서 "재귀 말고 반복문으로 짜보세요"라는 요청이 나오면 바로 이렇게 전환할 수 있어야 합니다.

---

5. BST vs 힙(Heap) 자세히 살펴보기

둘 다 이진 트리 형태지만 목적과 규칙이 완전히 다릅니다.

특징	BST (이진 탐색 트리)	Heap (힙)
목적	검색 (Search)	최댓값/최솟값 빠르게 찾기
규칙	왼쪽 < 부모 < 오른쪽	부모 > 자식 (Max Heap)
정렬	중위 순회 시 정렬됨	정렬 안 됨 (느슨한 정렬)
검색 시간	O(log N)	O(N) (랜덤 검색 시)
삽입/삭제	O(log N)	O(log N)
사용처	DB 인덱스, Map/Set	우선순위 큐 (Priority Queue)

"우선순위 큐를 구현할 때 BST를 써도 되나요?" 가능은 하지만 비효율적입니다. 힙은 배열(Array)로 구현 가능해서 메모리 효율과 캐시 지역성(Cache Locality)이 훨씬 뛰어난 반면, BST는 포인터 기반이라 오버헤드가 큽니다.

---

6. 치명적인 단점 - 편향 트리 (Skewed Tree)

만약 데이터가 정렬된 상태로 1, 2, 3, 4, 5 순서대로 들어오면 어떻게 될까요?

• 1은 루트.
• 2는 1보다 크니까 오른쪽.
• 3은 2보다 크니까 오른쪽...

결과적으로 트리가 아니라 그냥 오른쪽으로 기울어진 막대기(Linked List)가 되어버립니다. 이 모양을 편향 트리(Skewed Tree)라고 합니다. 이때의 트리 높이 $h$는 $N$이 됩니다. 검색 시간 복잡도는 O(N)으로 퇴화합니다. 비싼 스포츠카(BST)를 샀는데 자전거(Linked List) 속도가 나오는 셈입니다.

해결책 - 자가 균형 트리 (Self-Balancing Tree)

데이터가 입력될 때마다 트리의 회전(Rotation)을 수행하여 높이를 낮게 유지하는 알고리즘들이 있습니다.

1. AVL 트리:
   • 최초의 자가 균형 트리.
   • 왼쪽/오른쪽 높이 차이를 1 이하로 엄격하게 유지합니다.
   • 검색은 빠르지만, 삽입/삭제 시 회전이 많이 일어나 느립니다.
2. Red-Black 트리:
   • 노드에 빨강/검정 색칠을 하고 규칙을 따릅니다.
   • AVL보다 덜 엄격해서 회전이 적게 일어납니다.
   • Java의 TreeMap, C++의 std::map이 내부적으로 이걸 씁니다. 실제 표준입니다.
   • 리눅스 커널 스케줄러 (CFS)와 가상 메모리 관리 (VMA)에서도 쓰입니다.

4.1. 왜 리눅스 커널은 BST를 쓸까요?

리눅스는 운영체제입니다. 수천 개의 프로세스가 메모리를 달라고 아우성칩니다. 각 프로세스가 사용하는 메모리 영역(VMA, Virtual Memory Area)을 관리해야 하는데, 이 VMA 리스트를 어떻게 저장할까요?

1. Linked List: 검색에 O(N)이 걸립니다. 프로세스가 메모리 영역을 1000개 쓰면, 매번 메모리 접근할 때마다 느려집니다.
2. 배열 (Array): 검색은 빠르지만, 메모리 영역이 추가/삭제될 때마다 데이터를 밀고 당겨야 해서 O(N)입니다. 끔찍하죠.
3. Red-Black Tree: 검색도 O(log N), 추가/삭제도 O(log N)입니다. 그래서 리눅스 커널의 mm_struct 안에는 vm_area_struct를 관리하는 Red-Black Tree가 들어있습니다. 여러분이 지금 브라우저를 띄우고 유튜브를 보는 것도, 결국 이 이진 탐색 트리가 메모리를 효율적으로 관리해주기 때문에 가능한 일입니다.

---

---

7. 트리 순회 (Traversals)와 스택 오버플로우의 위험

트리의 모든 노드를 빠짐없이 방문하는 방법입니다.

1. 전위 순회 (Pre-order): Root -> Left -> Right (트리 복사용)
2. 중위 순회 (In-order): Left -> Root -> Right (정렬된 결과)
3. 후위 순회 (Post-order): Left -> Right -> Root (트리 삭제용)

⚠️ 재귀의 위험성

순회 코드를 짤 때 보통 재귀(Recursion)를 씁니다.

def inorder(root):
    if root:
        inorder(root.left)
        print(root.val)
        inorder(root.right)

하지만 트리가 매우 깊다면? (Depth > 10,000). Stack Overflow가 발생합니다. 실제로는 이를 방지하기 위해 Morris Traversal (Link를 임시으로 수정해서 스택 없이 순회)이나 Threaded Binary Tree를 사용하기도 합니다. Threaded Binary Tree는 Null 포인터를 낭비하지 않고, 다음 방문할 노드(Successor)를 가리키게 하여 재귀 없이 순회할 수 있게 만든 최적화된 자료구조입니다. 임베디드 시스템처럼 메모리가 귀한 곳에서 쓰입니다.

---

6. 고급 변형 - Splay Tree와 Treap

일반적인 BST가 지루한 당신을 위한 고급 자료구조입니다.

6.1. Splay Tree

"한 번 찾은 놈은 또 찾을 확률이 높다" (Temporal Locality)는 원리를 이용합니다. 어떤 노드를 검색하거나 삽입하면, 그 노드를 회전(Rotation)을 통해 루트(Root)까지 끌어올립니다. 이렇게 하면 자주 찾는 데이터는 루트 근처에 모이게 됩니다. 캐시(Cache) 구현에 아주 유용합니다. 균형을 완벽하게 맞추진 않지만, 실제적으로 매우 빠릅니다.

6.2. Treap (Tree + Heap)

BST의 규칙(왼쪽 < 부모 < 오른쪽)과, 힙(Heap)의 규칙(부모 우선순위 > 자식 우선순위)을 섞은 것입니다. 각 노드에 랜덤한 '우선순위'를 부여합니다. 이렇게 하면 데이터가 정렬된 순서로 들어와도, 우선순위가 랜덤하기 때문에 트리가 확률적으로 균형 잡힌 모양을 갖게 됩니다. 구현이 쉽고 성능이 좋습니다.

---

7. 심화: BST vs Hash Table vs B-Tree

Q: "검색 속도 O(1)인 해시 테이블(Hash Table) 쓰면 안 되나요?"

해시는 빠릅니다. 하지만 순서가 없습니다.

• "나이 20세 이상 30세 이하 유저 찾아줘" (Range Query)
• 해시 테이블은 이걸 못 합니다. 모든 데이터를 다 뒤져야(O(N)) 합니다.
• BST는 20과 30 위치만 찾으면 그 사이 데이터를 싹 긁어올 수 있습니다.

Q: "그럼 DB는 BST를 쓰나요?"

정확히는 BST의 사촌인 B-Tree (또는 B+Tree)를 씁니다.

• BST는 노드 하나에 데이터 1개입니다. 이리저리 포인터 따라가느라 메모리 점프가 심합니다.
• 디스크(HDD/SSD)는 블록 단위(페이지, 4KB)로 데이터를 읽습니다.
• B-Tree는 노드 하나에 데이터 수백 개를 꽉 채워 넣습니다.
• 트리 높이가 3~4 정도로 매우 낮아져서, 디스크를 3번만 읽으면 1억 건 중 하나를 찾을 수 있습니다.
• 데이터베이스 인덱스의 기술입니다.

---

8. 핵심 정리

Q1: BST와 Hash Table의 결정적인 차이는?

A: 해시 테이블은 검색 속도가 O(1)로 빠르지만, 순서가 없습니다. 그래서 "10보다 크고 20보다 작은 값" 같은 범위 검색(Range Query)을 할 수 없습니다. 반면 BST는 중위 순회(In-order)를 하면 정렬된 데이터를 얻을 수 있어 범위 검색에 유리합니다.

Q2: Red-Black 트리가 AVL 트리보다 많이 쓰이는 이유는?

A: AVL 트리는 균형을 너무 엄격하게(높이 차 1 이하) 맞추느라, 데이터 삽입/삭제 때마다 회전 연산을 너무 많이 합니다. 반면 Red-Black 트리는 균형 조건을 약간 느슨하게 해서 회전 횟수를 줄였습니다. 검색 속도는 AVL보다 아주 약간 느리지만, 삽입/삭제 성능이 훨씬 좋아서 범용적인 라이브러리(Java TreeMap, C++ Map, Linux Scheduler)에 채택되었습니다.

Q3: B-Tree가 DB 인덱스에 쓰이는 이유는?

A: 디스크 I/O 때문입니다. 일반 BST는 노드 하나가 메모리 여기저기에 흩어져 있지만, B-Tree는 하나의 노드(페이지)에 수백 개의 키를 꽉 채워 넣습니다. 디스크에서 한 블록(4KB)을 읽어오면 수백 개의 자식 주소를 한 번에 알 수 있어, 트리의 높이가 매우 낮아집니다. 디스크 접근 횟수를 최소화하기 위해 설계된 트리입니다.

---

9. 요약

1. BST: Up & Down 게임 전략. 검색 $O(\log N)$.
2. 약점: 정렬된 데이터 입력 시 $O(N)$ 편향 트리 발생.
3. 해결: Red-Black Tree (자가 균형) 사용.
4. 응용: DB는 B-Tree, 캐시는 Splay Tree, 리눅스 스케줄러는 Red-Black Tree 사용.

10. 마치며 - 균형 잡힌 삶을 위하여

이진 탐색 트리는 우리에게 "균형(Balance)"의 중요성을 가르쳐 줍니다. 한쪽으로 치우친 편향 트리는 데이터가 쌓일수록 느려지고 무능해집니다. 반면 스스로 균형을 맞추는 AVL이나 Red-Black 트리는 어떤 시련(데이터 폭주)이 와도 $O(\log N)$의 평정심을 유지합니다.

개발자로서의 삶도 마찬가지 아닐까요? 특정 기술 하나에만 너무 깊게 파고들면(Over-fitting), 기술 트렌드가 바뀌었을 때 적응하기 힘듭니다. 반대로 너무 얕게만 알면 깊이 있는 문제를 해결하지 못합니다. 이론(CS)과 실무(Engineering) 사이의 균형, 일과 삶의 균형(Work-Life Balance). BST가 스스로 회전하며 늘 중심을 잡듯이, 우리도 끊임없이 Self-Balancing을 해야 롱런하는 개발자가 될 수 있지 않을까 생각합니다.

---

Binary Search Tree (BST): The Basics of Data Search and Balancing Aesthetics

1. The Up & Down Game

Guess a number between 1 and 100. Target is 70.

The Dumb Strategy (O(N)) "Is it 1?" "No." "Is it 2?" "No." ... "Is it 70?" "Yes!" If the range is 1 million, you might ask 1 million questions. This is Linear Search.

The Smart Strategy (O(log N)) "Is it bigger than 50?" "Yes." (Eliminated 1-50. 50 candidates left.) "Is it bigger than 75?" "No." (Eliminated 76-100. 25 candidates left.) "Is it bigger than 62?" ... By cutting the search space in half every time, you can find the answer in just 7 steps ($2^7 = 128$). Even with 1 Billion items, it takes only 30 steps ($2^ \approx 10^9$). The Binary Search Tree is the data structure that embodies this strategy.

---

2. The Three Golden Rules

A BST is a tree that strictly follows these rules:

1. Left Child is smaller than Parent ($L < P$).
2. Right Child is bigger than Parent ($R > P$).
3. No duplicate values (typically).

Because of these rules, you act like a traffic controller: "Target 70? You are bigger than me (50). Go Right. Do not verify Left."

---

3. Operations & Implementation (Java & Python)

3.1. Node Structure

Java Example

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

3.2. Search

def search(root, key):
    # Base Case: Found or Empty
    if root is None or root.val == key:
        return root
    
    # Target is smaller? Go Left.
    if key < root.val:
        return search(root.left, key)
    
    # Target is bigger? Go Right.
    return search(root.right, key)

Recursive logic makes BST algorithms clean and elegant. Time Complexity is $O(h)$ where $h$ is the height of the tree.

3.3. Insertion

Follow the search path. When you hit a Dead End (None), plant the new node there. It naturally finds its correct sorted position. Note: You don't need to move other nodes like in an Array. just change one pointer. This is why insertion is also $O(\log N)$, unlike Array's $O(N)$.

3.4. Deletion (The Hard Part)

Removing a node has 3 scenarios:

1. Leaf Node: Just delete it. Easy.
2. One Child: The node's parent adopts the node's only child.
3. Two Children:
   • This is tricky. Who takes the empty spot?
   • We find the In-order Successor (The smallest node in the Right Subtree).
   • Why? Because that logic guarantees the BST rules are kept.
   • Copy its value to the target spot.
   • Delete the Successor node (which is usually a leaf or has one child).

---

4. The Achilles' Heel: Skewed Trees

What happens if you insert sorted data: 1, 2, 3, 4, 5?

• 1 is Root.
• 2 is Right of 1.
• 3 is Right of 2... The tree doesn't branch. It becomes a Long Line leaning right. This is called a Skewed Tree (or Degenerate Tree).

The height $h$ becomes $N$. Search time degrades to O(N). You paid for a sports car (BST) but got a bicycle (Linked List).

The Solution: Self-Balancing Trees

We need algorithms that automatically rearrange (Rotate) the tree to keep it bushy, not deep.

• AVL Tree:
  • Keep height difference between left/right subtrees $\le 1$.
  • Very strict. Fast lookups, slower updates.
• Red-Black Tree:
  • Uses colors (Red/Black) and loose rules to maintain balance.
  • Faster updates. Used in Java TreeMap, C++ std::map, Linux Kernel Scheduler.

---

5. Tree Traversals

How do we walk through every node?

5.1. In-order Traversal (Left -> Root -> Right)

• Output: 1, 5, 10, 15...
• Magic: The output is Sorted.
• This is how you turn a BST back into a sorted array.
• Used checking if a tree is valid BST.

5.2. Pre-order Traversal (Root -> Left -> Right)

• Output: 10, 5, 1, 15...
• Useful for Cloning the tree. (You process parents before children).
• Used in expression parsing (Prefix notation).

5.3. Post-order Traversal (Left -> Right -> Root)

• Output: 1, 5, 15, 10...
• Useful for Deletion (Delete children before killing the parent).
• Used in Filesystem size calculation (Sum of children = My size).

---

6. Comparison: Hash Table vs BST vs B-Tree

Q1: "Hash Tables have O(1) search. Why use BST (O(log N))?"

Hash Tables are fast but Unordered.

• "Find User ID 105" -> Hash Table wins.
• "Find Users with ID between 100 and 200" -> Hash Table fails. It must scan everything.
• BST wins for Range Queries and Ordered Data navigation.
• Also, Hash Tables have occasional $O(N)$ Resize cost. BST is smoother.

Q2: "Why do Databases use B-Trees instead of BST?"

A Standard BST stores nodes randomly in memory. Disk drives read data in Blocks (or Pages, e.g., 4KB, 8KB, 16KB).

• BST: Reading 1 node might load 1 block. To trace depth 20, you read 20 blocks. Disk IO is slow.
• B-Tree: A "Fat" BST. One node has 100 keys and children, fitting perfectly in 1 Disk Block.
• To trace depth, you only need 3-4 disk hops even for millions of records.
• B-Trees are optimized for Disk I/O.

---

7. Advanced: Threaded Binary Trees

In a normal BST implementation, leaf nodes have null pointers for left/right. Functionally, about 50% of pointers in a tree are null. That's wasted memory space.

Threaded Binary Trees use these null pointers to point to the In-order Predecessor or Successor.

• "Right null" points to the Next node in sorted order.
• "Left null" points to the Previous node. Benefit: You can iterate through the entire tree (In-order traversal) without using a Stack or Recursion. It becomes highly memory efficient for traversal-heavy tasks.

---

8. Advanced Variants: Splay Trees & Treaps

8.1. Splay Tree

Uses the principle of Temporal Locality: "If I accessed it now, I'll likely access it again soon." Whenever you search/insert a node, you Splay (Rotate) it all the way to the Root. Frequently accessed hot nodes stay near the top. Very efficient for Cache implementation, even without strict balancing.

8.2. Treap (Randomized BST)

Tree + Heap. Each node has a Key (for BST requirement) and a Random Priority (for Heap requirement).

• BST Rule: Left < Parent < Right.
• Heap Rule: Parent Priority > Child Priority. By assigning random priorities, the tree naturally avoids worst-case skewed shapes (statistically). It provides $O(\log N)$ performance with very simple code compared to Red-Black trees.

---

9. FAQ: Common Questions

Q1: Why use BST over Hash Table?

Hash Tables are $O(1)$ but unordered. If you need Range Queries ("Find users between age 20 and 30") or Nearest Neighbor searches, Hash Tables fail. BSTs excel at this.

Q2: How does Java TreeMap work?

It uses a Red-Black Tree. It guarantees $O(\log N)$ for containsKey, get, put, and remove. It also provides methods like floorKey(K key) (greatest key less than or equal to K) which simple HashMaps cannot do.

Q3: What is the Time Complexity of building a BST?

If you insert N items one by one:

• Average: $O(N \log N)$.
• Worst (Sorted Input): $O(N^2)$.
• Red-Black Tree: Always $O(N \log N)$.