외부 이진 탐색 트리 편집하기

외부 이진 탐색 트리(external binary search tree)는 모든 키(key)를 '''리프 노드(외부 노드)'''에 저장하는 이진 탐색 트리 구조이다. 내부 노드에는 실제 키 대신 탐색을 위한 비교 정보만 저장되며, 키와 연관된 실제 데이터는 리프 노드에 위치한다.
==개념==
*외부 노드만 실제 키를 저장하고, 내부 노드는 탐색 경로를 위한 정보만 갖는다
*삽입, 삭제, 탐색 과정에서 비교는 내부 노드를 통해 이루어지고, 실제 데이터는 외부 노드에 도달했을 때 확인된다
*일부 문헌에서는 이를 '''트라이 기반 탐색 구조''' 또는 '''2-포인터 노드 구조'''와 비교하기도 한다
==특징==
*모든 데이터는 리프에 존재 → 외부 노드 수 = 데이터 수
*내부 노드는 비교 기준만 가지므로 공간 절약 가능
*균형 잡힌 구조로 만들면 디스크 I/O를 고려한 외부 기억장치 기반 탐색 구조로도 활용 가능
==구조 예시==
삽입된 키: 10, 20, 30

트리 구조 (내부 노드: (), 외부 노드: [키])<pre>
          (20)
         /    \
     (10)      [30]
    /    \
 [10]   [20]
</pre>

== 동작 예시 ==

=== 삽입 ===
#외부 노드를 탐색해 삽입 위치를 찾는다
#해당 외부 노드를 분할하여 새로운 내부 노드와 두 개의 외부 노드를 생성한다
<syntaxhighlight lang="py3">
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
</syntaxhighlight>

=== 삭제 ===
#삭제 대상이 있는 외부 노드를 찾는다
#부모 내부 노드와 그 자식을 함께 제거하고, 자식을 대체할 외부 노드를 연결
<syntaxhighlight lang="py3">
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
</syntaxhighlight>

=== 검색 ===
<syntaxhighlight lang="py3">
Lookup(K):
    u ← root
    while u는 internal node:
        if K < u.key: u ← u.left
        else:         u ← u.right
    return u  // external node
</syntaxhighlight>

==장점==
*외부 노드에만 키 저장 → 탐색 구조가 단순화됨
*일부 외부 저장구조(B-tree, B+트리)의 기초 개념으로 사용됨
*삽입/삭제 시 리프 단에서만 변화 발생 → 병렬성 증가
==단점==
*일반 [[이진 탐색 트리]]에 비해 깊이가 깊어질 수 있음
*내부 노드에 값이 없기 때문에 비교 연산이 비효율적으로 될 수 있음
*최악의 경우 균형이 무너지면 선형 구조가 될 수 있음
==활용==
*외부 메모리 기반 탐색 알고리즘 설계
*[[B트리]], [[B+트리]] 같은 고차원 자료구조의 기반 이론
*네트워크 라우팅 테이블, 파일시스템 인덱스
==같이 보기==
*[[이진 탐색 트리]]
*[[AVL 트리]]
*[[B트리]]
*[[B+트리]]
*[[외부 정렬]]
==참고 문헌==
*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