---

• 동적 손가락 검색 데이터 구조는 손가락 검색 외에도 손가락이 제공하는 위치에서 요소의 삽입 및 삭제를 수행해야 합니다.
• 핑거 검색 트리는 O(1)개의 움직일 수 있는 손가락만 유지된다는 가정 하에 O(log d) 시간에 손가락 검색을 지원하고 O(1) 시간에 업데이트를 지원하는 B-트리의 변형으로 정의됩니다.
• 손가락 d개의 위치를 ​​이동하려면 O(log d) 시간이 필요합니다.
• 핑거 검색 트리(AVL-트리, 레드-블랙 트리를 의미함) 구성은 고정된 고정 수의 핑거를 고려하거나 상각된 일정 시간의 업데이트만 지원합니다.
• 임의의 손가락 수와 최악의 경우 업데이트를 지원하는 구조가 생성되었습니다.
• 최악의 경우 O(1) 시간에 임의의 위치에서 업데이트를 지원하지만 O(log n) 시간에만 검색을 지원하는 검색 트리입니다.
• O(log d) 시간 검색 및 O(log d n) 시간 삽입 및 삭제를 지원하는 구성.
• 핑거 검색 트리는 최악의 경우 상수 시간 삽입과 O(log d n) 시간 삭제를 사용합니다.
• 링크된 (2,4)-트리에 대한 공간 효율적인 대안 솔루션에 따르면, (2,4)-트리와 동일한 성능 비용으로 진행할 수 있는 단일 손가락이 허용됩니다. 이 솔루션에서는 레벨 링크와 부모 포인터가 필요하지 않으며 대신 손가락을 효율적으로 통과할 수 있도록 손가락에 대해 특별한 O(log n) 공간 데이터 구조인 손이 생성됩니다.
• 스프레이 트리는 분할 O(log n) 시간에 검색, 삽입 및 삭제를 지원하는 자체 조정 이진 검색 트리 클래스로 정의됩니다. 그 스플레이 트리는 효율적인 손가락 검색 트리로 구현될 수 있습니다.
• 초기화 비용이 O(n)인 경우, 스플레이 트리에서 이전 액세스로부터 거리 d에 있는 액세스의 상각 비용은 O(log d)이며 액세스는 검색, 삽입 및 삭제로 구성됩니다.
• 문은 항상 마지막으로 액세스한 요소를 가리키는 한 손가락이 있는 경우에만 구현됩니다.
• 위에 언급된 모든 구성은 요소에 대해 허용되는 유일한 작업이 두 요소의 비교인 포인터 시스템에 적용할 수 있습니다.
• RAM(Random Access Machine) 모델의 경우 지속적인 업데이트 시간과 O(log d) 검색 시간을 사용하여 손가락 검색 트리를 개발합니다. 이 결과는 작은 트리 구조를 표로 작성하여 얻을 수 있지만 요소 비교만 수행합니다.