레벨 링크를 활용한 (2,4)-트리의 핑거 탐색
이 절에서는 레벨 링크(level link)를 도입하여 (2,4)-트리가 어떻게 효율적인 핑거 탐색(finger search)을 지원할 수 있는지 설명합니다. 여기서 소개하는 아이디어는 b ≥ 2a를 만족하는 보다 일반적인 높이 균형 트리(height-balanced tree), 즉 (a,b)-트리 클래스에도 그대로 적용됩니다.
(2,4)-트리는 모든 리프 노드가 동일한 깊이를 가지며, 모든 내부 노드의 차수(degree)가 2, 3 또는 4인 높이 균형 탐색 트리입니다. 실제 원소들은 리프에 저장되고, 내부 노드에는 탐색 경로를 안내하기 위한 검색 키만 저장됩니다. 각 내부 노드의 차수가 최소 2이므로 (2,4)-트리의 높이는 O(log n)이며, 탐색 역시 O(log n) 시간에 수행됩니다. (2,4)-트리의 중요한 특성 중 하나는, 핑거(finger)가 주어졌을 때 삽입과 삭제가 분할 상환(amortized) O(1) 시간에 이루어진다는 점입니다. 이 특성은 (2,3)-트리에는 존재하지 않는데, (2,3)-트리에서는 m번의 삽입과 삭제에 Θ(m log m) 시간이 필요한 연속 연산이 존재합니다. 또한 리프가 m개인 (2,4)-트리는 분할 상환 O(log min(m₁, m₂)) 시간 안에 크기 m₁과 m₂인 두 개의 트리로 분할(split)할 수 있으며, 마찬가지로 크기가 m₁, m₂인 두 (2,4)-트리도 분할 상환 O(log min(m₁, m₂)) 시간에 하나로 병합(concatenate)할 수 있습니다.
핑거 탐색을 지원하기 위해 (2,4)-트리에는 레벨 링크가 추가됩니다. 즉, 같은 깊이에 있는 모든 노드들이 이중 연결 리스트(doubly linked list) 형태로 서로 연결됩니다. 아래 그림은 레벨 링크가 추가된 (2,4)-트리를 보여줍니다. 모든 간선은 양방향 링크를 나타낸다는 점에 유의하세요. 추가된 레벨 링크는 (2,4)-트리의 삽입, 삭제, 분할, 병합 과정에서도 손쉽게 유지할 수 있습니다.
X에서 Y로 향하는 핑거 탐색을 수행하려면 먼저 Y가 X의 왼쪽에 있는지 오른쪽에 있는지 확인합니다. 일반성을 잃지 않고 Y가 X의 오른쪽에 있다고 가정하면, X에서 루트 방향으로 올라가는 경로를 따라가면서 경로 위의 노드 V와 V의 오른쪽 이웃 노드들을 검사하여, Y가 V 또는 V의 오른쪽 이웃에 뿌리를 둔 서브트리 내부에 포함되어 있음이 확인될 때까지 진행합니다. 그 지점에서 상향 탐색을 종료하고, V와 V의 오른쪽 이웃 각각에서 Y를 향한 하향 탐색을 최대 두 번 시작합니다. 그림 1에서 j부터 t까지의 핑거 탐색 과정에서 따라간 포인터는 굵은 선으로 표시되어 있습니다.
O(log d)의 탐색 시간은 다음 관찰에서 비롯됩니다. 상향 탐색을 노드 V의 부모까지 진행했다면, Y는 V의 오른쪽 이웃의 가장 왼쪽 서브트리보다 더 오른쪽에 위치하게 됩니다. 즉, d는 지금까지 도달한 높이에 대해 최소 지수적으로(exponentially) 커진다는 의미입니다.
그림 1에서 내부 노드 "l n"에서 노드 "h"로 이동하는 이유는, "s" 위치에서 이미 Y가 노드 "q r"에 뿌리를 둔 서브트리의 오른쪽에 있음을 알 수 있기 때문입니다.
레벨 링크가 적용된 (2,4)-트리를 위한 이러한 구성 방식은 외부 메모리(external memory)에 구현할 수 있는 레벨 링크 (a,b)-트리로 자연스럽게 일반화됩니다. 내부 노드 하나가 외부 메모리의 한 블록에 들어가도록 b = 2a로 선택하면, 삽입과 삭제를 O(1) 메모리 전송(memory transfer)으로 처리하고, 핑거 탐색을 O(log_b n) 메모리 전송으로 수행하는 외부 메모리 핑거 탐색 트리를 얻을 수 있습니다.