|
|
| 1번째 줄: |
1번째 줄: |
| 외부 이진 탐색 트리(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
| |
