이 섹션에서는 (2,4)-트리가 레벨 링크를 도입하여 효율적인 손가락 검색을 지원할 수 있는 방법을 설명합니다. 이 섹션에서 설명하는 아이디어는 b ≥ 2a에 대해 (a, b)-트리로 표시되는 보다 일반적인 높이 균형 트리 클래스에도 구현됩니다.
(2,4)-트리는 모든 잎의 깊이가 동일하고 모든 내부 노드의 차수가 2, 3 또는 4인 높이 균형 탐색 트리로 정의됩니다. 요소는 리프에 저장되고 내부 노드는 검색 안내를 위한 검색 키만 저장합니다. 각 내부 노드는 차수가 2 이상이므로 (2,4)-트리는 높이가 O(log n)이고 O(log n) 시간에 검색을 지원합니다. (2,4)-트리의 중요한 속성은 손가락에 의해 제공된 삽입 및 삭제가 상각된 O(1) 시간이 걸린다는 것입니다(이 속성은 m개의 삽입 및 삭제 시퀀스가 있는 (2,3)-트리에서 공유되지 않습니다. Θ(m log m) 시간이 필요한 삭제). 또한 m개의 잎을 가진 (2,4)-트리는 상각된 O(log min(m1, m2)) 시간에 크기가 m1 및 m2인 두 개의 트리로 분할될 수 있습니다. 마찬가지로 크기가 m1 및 m2인 두(2,4)개의 트리를 분할 상환 O(log min(m1, m2)) 시간에 결합(연결)할 수 있습니다.
손가락 검색을 지원하기 위해 (2,4)-트리는 동일한 깊이를 가진 모든 노드가 이중 연결 목록에서 함께 연결되도록 레벨 링크로 보강됩니다. 다음 그림은 레벨 링크로 보강된 (2,4) 트리를 표시합니다. 모든 모서리는 양방향 링크를 나타냅니다. 추가 레벨 링크는 (2,4)-트리의 삽입, 삭제, 분할 및 조인 동안 유지하기 쉽습니다.
X에서 Y로 손가락 검색을 수행하려면 먼저 Y가 X의 왼쪽 또는 오른쪽에 있는지 확인합니다. 일반성을 잃지 않고 Y가 X의 오른쪽에 있다고 가정합니다. 그런 다음 검사하는 동안 X에서 루트를 향한 경로를 방문합니다. Y가 V 또는 V의 오른쪽 이웃에 뿌리를 둔 하위 트리 내에 포함된다는 것이 확립될 때까지 경로의 노드 V와 오른쪽 이웃. 그런 다음 위쪽 검색이 종료되고 각각 V 및/또는 V의 오른쪽 이웃에서 y에 대한 최대 두 번의 아래쪽 검색이 시작됩니다. 그림 1에서 j에서 t까지의 손가락 검색 중에 따라가는 포인터는 굵은 선으로 표시됩니다.
O(log d) 탐색 시간은 상위 탐색을 노드 V의 부모로 진행하면 Y가 V의 오른쪽 이웃의 가장 왼쪽 하위 트리의 오른쪽에 있다는 관찰에서 따릅니다. 즉, d는 다음에서 최소한 지수입니다. 높이에 도달했습니다.
그림 1에서 "l n"이라는 레이블이 지정된 내부 노드에서 "h"라는 레이블이 지정된 노드로 진행합니다. "s"에서 Y가 노드 "q r"에 루트된 하위 트리의 오른쪽에 있다는 것을 알고 있기 때문입니다.
레벨 링크(2,4) 트리의 구성은 외부 메모리에서 구현할 수 있는 레벨 링크(a, b) 트리로 직접 일반화됩니다. 내부 노드가 외부 메모리의 블록에 맞도록 a =2b 및 b를 선택하여 O(1) 메모리 전송에서 삽입 및 삭제를 지원하는 외부 메모리 핑거 탐색 트리를 달성하고 O(logb n) 메모리 전송으로 핑거 탐색을 지원합니다. .