핑거 검색 트리
Finger search tree컴퓨터 과학에서 핑거 검색 트리는 손가락이라고 불리는 내부 노드의 포인터를 유지하는 이진 검색 트리의 일종이다.손가락은 손가락에 가까운 요소에 대한 검색, 삽입 및 삭제 속도를 높여 상각된 O(log n) 조회 및 상각된 O(1) 삽입 및 삭제 작업을 수행한다.손가락 탐색 트리를 구현하는 데 사용할 수 있지만, 손가락 트리나 스플레이 트리와 혼동해서는 안 된다.
Guibas 등은 B-tree를 기반으로 하여 핑거 검색 트리를 도입했다.[1]원본은 O(log d) 시간에 핑거 검색을 지원하며, 여기서 d는 손가락과 검색 대상 사이의 요소 수입니다.업데이트는 O(1) 이동 가능한 손가락만 유지되는 경우 O(1) 시간이 걸린다.핑거 p 위치를 이동하려면 O(log p) 시간이 필요하다.Huddleston과 Mehlhorn은 이 아이디어를 수평 연계 B-tree로 다듬었다.[2]
차칼리디스는 나무 끝에서 검색을 용이하게 하는 AVL 트리를 기반으로 한 버전을 제안했는데, 그러한 트리를 여러 개 사용하여 여러 손가락으로 데이터 구조를 구현하는 데 사용할 수 있다.[3]
바이너리 트리에 대해 손가락 검색을 수행하는 것이 가장 이상적인 방법은 손가락에서 시작하여, x와 [3]y의 터닝 노드라고도 불리는 [4][5]가장 일반적인 조상에 도달할 때까지, 그리고 나서 아래쪽으로 내려가서 우리가 찾고 있는 원소를 찾는 것이다.노드가 다른 노드의 조상인지 확인하는 것은 비경쟁적이다.
세이델과 아라곤이 제안한 무작위 트리 구조인 트레프스는 거리 d의 두 원소의 예상 경로 길이가 O(log d)라는 특성을 갖고 있다.[5]손가락 검색을 위해, 그들은 최소 공통 조상(LCA)을 신속하게 결정하거나, 모든 노드에서 하위 트리의 최소값과 최대값을 유지하기 위해 포인터를 추가할 것을 제안했다.
손가락 검색 나무를 심층적으로 다룬 책장이 작성됐다.[4]브로달은 추가 부기 정보가 필요 없이 O(log d) 시간에 트레프에서 핑거 검색을 수행할 수 있는 알고리즘을 제안했고, 이 알고리즘은 마지막 후보 LCA에서 동시에 아래쪽으로 검색함으로써 이를 실현한다.
참고 항목
참조
- ^ Guibas, L.J. (1977), "A new representation for linear lists", Proceedings of the Ninth Annual ACM Symposium on Theory of Computing: 49–60, CiteSeerX 10.1.1.527.7294, doi:10.1145/800105.803395, S2CID 2414154
- ^ Huddleston; Mehlhorn, Kurt (1982). "A New Data Structure for Representing Sorted Lists". Acta Informatica. 17 (2): 157–184. doi:10.1007/BF00288968. S2CID 10397918.
- ^ a b Tsakalidis, Athanasios K. (1985). "AVL-Trees for Localized Search". Information and Control. 67 (1–3): 173–194. doi:10.1016/S0019-9958(85)80034-6.
- ^ a b Brodal, Gerth Stølting (2005). "11. Finger Search" (PDF). In Mehta, Dinesh P.; Sahni, Sartaj (eds.). Handbook of Data Structures and Applications. Chapman & Hall / CRC Press. ISBN 978-1584884354. Retrieved 1 January 2013.
- ^ a b Seidel, R.; Aragon, C.R. (1996). "Randomized search trees". Algorithmica. 16 (4–5): 464–497. CiteSeerX 10.1.1.122.6185. doi:10.1007/BF01940876. S2CID 9370259.
