외부 이진 탐색 트리

외부 이진 탐색 트리(external binary search tree)는 모든 키(key)를 리프 노드(외부 노드)에 저장하는 이진 탐색 트리 구조이다. 내부 노드에는 실제 키 대신 탐색을 위한 비교 정보만 저장되며, 키와 연관된 실제 데이터는 리프 노드에 위치한다.

1 개념

• 외부 노드만 실제 키를 저장하고, 내부 노드는 탐색 경로를 위한 정보만 갖는다
• 삽입, 삭제, 탐색 과정에서 비교는 내부 노드를 통해 이루어지고, 실제 데이터는 외부 노드에 도달했을 때 확인된다
• 일부 문헌에서는 이를 트라이 기반 탐색 구조 또는 2-포인터 노드 구조와 비교하기도 한다

2 특징

• 모든 데이터는 리프에 존재 → 외부 노드 수 = 데이터 수
• 내부 노드는 비교 기준만 가지므로 공간 절약 가능
• 균형 잡힌 구조로 만들면 디스크 I/O를 고려한 외부 기억장치 기반 탐색 구조로도 활용 가능

3 구조 예시

삽입된 키: 10, 20, 30

트리 구조 (내부 노드: (), 외부 노드: [키])

          (20)
         /    \
     (10)      [30]
    /    \
 [10]   [20]

4 동작 예시

4.1 삽입

1. 외부 노드를 탐색해 삽입 위치를 찾는다
2. 해당 외부 노드를 분할하여 새로운 내부 노드와 두 개의 외부 노드를 생성한다

Insert(K):
    e ← Lookup(K)  // e는 외부 노드
    K1 ← e.key
    p ← e.parent

    if K1 == K: 실패 (중복 삽입 불가)
    
    // 새로운 노드 만들기
    e1 ← new external node (K)
    u ← new internal node

    if K < K1:
        u.key ← K1
        u.left ← e1
        u.right ← e
    else:
        u.key ← K
        u.left ← e
        u.right ← e1

    // 부모와 연결
    if p.left == e:
        p.left ← u
    else:
        p.right ← u

4.2 삭제

1. 삭제 대상이 있는 외부 노드를 찾는다
2. 부모 내부 노드와 그 자식을 함께 제거하고, 자식을 대체할 외부 노드를 연결

Delete(K):
    x ← Lookup(K)
    if x.key ≠ K: 실패

    u ← x.parent
    y ← x의 sibling (u.left 또는 u.right 중 x가 아닌 쪽)

    if u가 root면:
        root ← y
    else:
        p ← u.parent
        if p.left == u:
            p.left ← y
        else:
            p.right ← y

4.3 검색

Lookup(K):
    u ← root
    while u는 internal node:
        if K < u.key: u ← u.left
        else:         u ← u.right
    return u  // external node

5 장점

• 외부 노드에만 키 저장 → 탐색 구조가 단순화됨
• 일부 외부 저장구조(B-tree, B+트리)의 기초 개념으로 사용됨
• 삽입/삭제 시 리프 단에서만 변화 발생 → 병렬성 증가

6 단점

• 일반 이진 탐색 트리에 비해 깊이가 깊어질 수 있음
• 내부 노드에 값이 없기 때문에 비교 연산이 비효율적으로 될 수 있음
• 최악의 경우 균형이 무너지면 선형 구조가 될 수 있음

7 활용

• 외부 메모리 기반 탐색 알고리즘 설계
• B트리, B+트리 같은 고차원 자료구조의 기반 이론
• 네트워크 라우팅 테이블, 파일시스템 인덱스

8 같이 보기

• 이진 탐색 트리
• AVL 트리
• B트리
• B+트리
• 외부 정렬

9 참고 문헌

• Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms. MIT Press
• Knuth, D. E. (1998). The Art of Computer Programming Vol. 3: Sorting and Searching. Addison-Wesley