Strom pro vyhledávání prstů - Finger search tree

Tento článek je o vyhledávacích stromech, které umožňují vyhledávání z vnitřních uzlů. Čistě funkční datovou strukturu viz prst strom.

V počítačové vědě stromy pro vyhledávání prstů jsou typem binární vyhledávací strom který udržuje ukazatele na vnitřní uzly, tzv prsty. Prsty zrychlují vyhledávání, vkládání a mazání prvků blízko prstů, čímž se amortizují Ó (log n) vyhledávání a amortizované O (1) vložení a odstranění. To by nemělo být zaměňováno s prst strom ani a rozložit strom, ačkoli oba lze použít k implementaci stromů pro vyhledávání prstů.

Guibas a kol.[1]představil stromy pro vyhledávání prstů, a to na B-stromy. Původní verze podporuje vyhledávání prstem v čase O (log d), kde d je počet prvků mezi prstem a cílem vyhledávání. Aktualizace vyžadují O (1) čas, kdy jsou udržovány pouze pohyblivé prsty O (1). Pohyb pozic prstu p vyžaduje čas O (log p). Huddleston a Mehlhorn tuto myšlenku vylepšili jako B-stromy spojené s úrovní.[2]

Tsakalidis navrhl verzi založenou na AVL stromy který usnadňuje vyhledávání z konců stromu; lze ji použít k implementaci datové struktury několika prsty pomocí více takových stromů.[3]

Chcete-li provést vyhledávání prstem na binárním stromu, je ideálním způsobem začít od prstu a hledat nahoru ke kořenu, dokud nedosáhneme nejméně společný předek,[4][5] také volal otočný uzel,[3] z x a y, a pak jděte dolů a najděte prvek, který hledáme. Určení, zda je uzel předkem jiného, ​​není triviální.

Příklad provádění vyhledávání prstů na treap.

Treaps, randomizovaná stromová struktura navržená Seidelem a Aragonem,[5] má vlastnost, že očekávaná délka cesty dvou prvků vzdálenosti d je O (log d). Pro vyhledávání prstem navrhli přidání ukazatelů k určení nejméně společný předek(LCA) rychle nebo v každém uzlu udržujte minimální a maximální hodnoty svého podstromu.

Byla napsána kapitola o knize, která do hloubky pokrývá stromy pro vyhledávání prstů.[4] Ve kterém Brodal navrhl algoritmus pro provádění prstového vyhledávání na treaps v čase O (log d), aniž by potřeboval nějaké další informace o účetnictví; tento algoritmus toho dosahuje současným hledáním dolů od posledního kandidátského LCA.

Viz také

Reference

  1. ^ Guibas, L. J. (1977), „Nová reprezentace pro lineární seznamy“, Sborník příspěvků z devátého výročního sympózia ACM o teorii práce s počítačem: 49–60, CiteSeerX  10.1.1.527.7294, doi:10.1145/800105.803395
  2. ^ Huddleston; Mehlhorn, Kurt (1982). "Nová datová struktura pro reprezentaci seřazených seznamů". Acta Informatica. 17 (2): 157–184. doi:10.1007 / BF00288968.
  3. ^ A b Tsakalidis, Athanasios K. (1985). „Stromy AVL pro lokalizované vyhledávání“. Informace a kontrola. 67 (1–3): 173–194. doi:10.1016 / S0019-9958 (85) 80034-6.
  4. ^ A b Brodal, Gerth Stølting (2005). "11. Hledání prstem" (PDF). In Mehta, Dinesh P .; Sahni, Sartaj (eds.). Příručka datových struktur a aplikací. Chapman & Hall / CRC Press. ISBN  978-1584884354. Citováno 1. ledna 2013.
  5. ^ A b Seidel, R.; Aragon, C.R. (1996). Msgstr "Náhodné vyhledávací stromy". Algorithmica. 16 (4–5): 464–497. CiteSeerX  10.1.1.122.6185. doi:10.1007 / BF01940876.