Geometrie binárních vyhledávacích stromů - Geometry of binary search trees

v počítačová věda, jeden přístup k dynamická optimálnost problém na online algoritmy pro binární vyhledávací stromy zahrnuje přeformulování problému geometricky, pokud jde o zvětšení sady bodů v rovině s co nejmenším počtem dalších bodů, aby se zabránilo obdélníkům s pouze dvěma body na jejich hranici.^[1]

Přístupové sekvence a konkurenční poměr

Jak je obvykle formulováno, problém online binárního vyhledávacího stromu zahrnuje vyhledávací stromy definované přes sadu pevných klíčů (1, 2, ..., n). An sekvence přístupu je sekvence ${ displaystyle x_ {1}, x_ {2},}$ ... kde každé číslo X_i je jedním z daných klíčů.

Jakýkoli konkrétní algoritmus pro udržování binárních vyhledávacích stromů (například rozložit strom algoritmus nebo Struktura pracovní sady Iacono ) má náklady pro každou přístupovou sekvenci, která modeluje množství času, které by trvalo použít strukturu k vyhledání každé z kláves v přístupové sekvenci. Cena vyhledávání je modelována za předpokladu, že algoritmus vyhledávacího stromu má jediný ukazatel do binárního vyhledávacího stromu, který na začátku každého hledání ukazuje na kořen stromu. Algoritmus pak může provádět libovolnou sekvenci následujících operací:

Přesuňte ukazatel na levé dítě.
Přesuňte ukazatel na jeho pravé dítě.
Přesuňte ukazatel na nadřazený.
Proveďte jeden rotace stromu na ukazatel a jeho nadřazený prvek.

Hledání je povinné, v určitém okamžiku v této posloupnosti operací přesunout ukazatel na uzel obsahující klíč, a cena za vyhledávání je počet operací, které jsou prováděny v posloupnosti. Celkové náklady_A(X) pro algoritmus A o přístupové sekvenci X je součet nákladů na vyhledávání každého následujícího klíče v pořadí.

Jak je standardem v konkurenční analýza, konkurenční poměr algoritmu A je definován jako maximum poměru ceny za všechny přístupové sekvence A za nejlepší cenu, jaké by jakýkoli algoritmus mohl dosáhnout:

{ displaystyle rho _ {A} = sup _ {X} { frac { mathrm {cost} _ {A} (X)} { mathrm {cost} _ { mathrm {opt}} (X) }}.}

The domněnka dynamické optimality tvrdí, že roztáhnout stromy mít konstantní konkurenční poměr, ale to zůstává neprokázané. Geometrický pohled na binární vyhledávací stromy poskytuje jiný způsob chápání problému, který vedl k vývoji alternativních algoritmů, které by také mohly (konjektivně) mít konstantní konkurenční poměr.

Překlad do geometrické množiny bodů

V geometrickém pohledu na problém online binárního vyhledávacího stromu, an sekvence přístupu ${ displaystyle x_ {1}, ..., x_ {m}}$ (posloupnost vyhledávání prováděných na binárním vyhledávacím stromu (BST) se sadou klíčů ${ displaystyle {1,2, ..., n}}$ ) je namapován na množinu bodů ${ displaystyle {(x_ {i}, i)}}$ , kde osa X představuje klíčový prostor a osa Y představuje čas; ke kterému soubor dotkl uzly jsou přidány. Podle dotkl uzly máme na mysli následující. Zvažte přístupový algoritmus BST s jediným ukazatelem na uzel ve stromu. Na začátku přístupu k danému klíči ${ displaystyle x_ {i}}$ , tento ukazatel je inicializován na kořen stromu. Kdykoli se ukazatel přesune na uzel nebo je inicializován, řekneme, že se uzlu dotkne.^[2]Představujeme algoritmus BST pro danou vstupní sekvenci nakreslením bodu pro každou položku, které se dotkne.

Předpokládejme například, že je uveden následující BST na 4 uzlech: Sada klíčů je {1, 2, 3, 4}.

Mapování pouze přístupové sekvence 3, 1, 4, 2.

Geometrický pohled na algoritmus binárního vyhledávacího stromu.

Nechť 3, 1, 4, 2 je přístupová sekvence.

Při prvním přístupu se dotkne pouze uzel 3.
V druhém přístupu se dotknou uzly 3 a 1.
Ve třetím přístupu se dotknou 3 a 4.
Ve čtvrtém přístupu stiskněte 3, poté 1 a poté 2.

Dotyky jsou znázorněny geometricky: Pokud je položka X se dotýká operací pro ith přístup, pak bod (X,i) je vynesen.

Stromově spokojené bodové sady

Obdélník překlenutý o dva body. Tato sada bodů je ne stromově spokojený.

Toto je příklad stromově uspokojené sady bodů.

Bodová sada se říká, že je stromově spokojený pokud platí následující vlastnost: pro libovolný pár bodů, které neleží na stejné vodorovné nebo svislé linii, existuje třetí bod, který leží v obdélníku překlenutém prvními dvěma body (buď uvnitř, nebo na hranici).

Teorém

Sada bodů obsahující body ${ displaystyle (x_ {i}, i)}$ je stromově spokojen, právě když odpovídá platnému BST pro vstupní sekvenci ${ displaystyle x_ {1}, x_ {2}, ..., x_ {m}}$ .

Důkaz

Nejprve prokažte, že bod nastavený pro jakýkoli platný algoritmus BST je stromově splněn. Zvažte body ${ displaystyle (x, i)}$ a ${ displaystyle (y, j)}$ , kde $X$ se dotkne v čase $i$ a $y$ se dotkne v čase $j$ . Předpokládejme to symetrií ${ displaystyle x$ a ${ displaystyle i$ . Je třeba ukázat, že v obdélníku existuje třetí bod s rohy jako ${ displaystyle (x, i)}$ a ${ displaystyle (y, j)}$ . Také nechte ${ displaystyle mathrm {LCA} _ {t} (a, b)}$ označit nejnižší společný předek uzlů $A$ a $b$ těsně před časem $t$ . Existuje několik případů:

Li ${ displaystyle mathrm {LCA} _ {i} (x, y) neq x}$ , pak použijte bod ${ displaystyle ( mathrm {LCA} _ {i} (x, y), i)}$ , od té doby ${ displaystyle mathrm {LCA} _ {i} (x, y)}$ muselo se to dotknout, pokud $X$ byl.
Li ${ displaystyle mathrm {LCA} _ {j} (x, y) neq y}$ , pak bod ${ displaystyle ( mathrm {LCA} _ {j} (x, y), j)}$ může být použito.
Pokud ani jeden z výše uvedených dvou případů neplatí, pak $X$ musí být předchůdcem $y$ těsně před časem $i$ a $y$ být předchůdcem $X$ těsně před časem $j$ . Pak někdy $k$ ${ displaystyle (i leq k$ , $y$ muselo být otočeno výše $X$ , takže jde o to ${ displaystyle (y, k)}$ může být použito.

Dále ukažte druhý směr: vzhledem k arborálně uspokojené množině bodů lze sestavit platný BST odpovídající dané množině bodů. Uspořádejte naše BST do treapu, který je organizován v hromadě podle next-touch-time. Všimněte si, že čas příštího dotyku má vazby, a proto není jednoznačně definován, ale to není problém, pokud existuje způsob, jak vazby přerušit. Když čas $i$ dosáhly uzly, kterých se dotkla forma připojeného podstromu nahoře, pomocí vlastnosti uspořádání haldy. Nyní tomuto podstromu přiřaďte nové časy dotyku a změňte jeho uspořádání na nový místní treap. Pokud pár uzlů, $X$ a $y$ , obkročit hranici mezi dotykovou a nedotčenou částí treapu, pak pokud $y$ je třeba se dotknout dříve než $X$ pak ${ displaystyle (x, nyní) to (y, další dotyk (y))}$ je neuspokojený obdélník, protože nejvíce vlevo by tento bod byl pravým potomkem $X$ , ne $y$ .

Důsledek

Nalezení nejlepšího provedení BST pro vstupní sekvenci ${ displaystyle x_ {1}, x_ {2}, ..., x_ {m}}$ je ekvivalentní k nalezení minimální nadmnožiny mohutnosti bodů (která obsahuje vstup v geometrické reprezentaci), která je stromově uspokojena. Obecnější problém nalezení minimální mohutnosti arborally uspokojené nadmnožiny obecné sady vstupních bodů (neomezeno na jeden vstupní bod za $y$ je známo, že je NP-kompletní.^[1]

Chamtivý algoritmus

Následující chamtivý algoritmus buduje stromově vyhovující sady:

Posuňte nastavený bod vodorovnou čarou zvětšením $y$ koordinovat.
V čase $i$ , umístěte minimální počet bodů na ${ displaystyle y = i}$ aby byl bod nastaven na ${ displaystyle y geq i}$ stromově spokojený. Tato minimální sada bodů je jednoznačně definována: pro jakýkoli neuspokojený obdélník vytvořený pomocí ${ displaystyle (x_ {i}, i)}$ v jednom rohu přidejte druhý roh na ${ displaystyle y = i}$ .

Algoritmus byl předpokládán jako optimální v rámci aditivního termínu.^[3]

Další výsledky

Geometrie binárních vyhledávacích stromů byla použita k poskytnutí algoritmu, který je dynamicky optimální, pokud je jakýkoli algoritmus binárního vyhledávacího stromu dynamicky optimální.^[4]

Viz také

Reference

^ ^A ^b Demaine, Erik D.; Harmon, Dion; Iacono, Johne; Kane, Daniel; Pătraşcu, Mihai (2009), „Geometrie binárních vyhledávacích stromů“, ve sborníku z 20. ročníku sympozia ACM-SIAM o diskrétních algoritmech (SODA 2009), New York: 496–505, doi:10.1137/1.9781611973068.55
^ Demaine, Erik D.; Harmon, Dion; Iacono, Johne; Pătraşcu, Mihai (2007), „Dynamická optimálnost - téměř“, SIAM Journal on Computing, 37 (1): 240–251, CiteSeerX 10.1.1.99.4964, doi:10.1137 / S0097539705447347, PAN 2306291
^ Fox, Kyle (15. – 17. Srpna 2011). Horní hranice pro maximálně chamtivé binární vyhledávací stromy (PDF). Algoritmy a datové struktury: 12. mezinárodní sympozium, WADS 2011. Přednášky z informatiky. 6844. New York: Springer. 411–422. arXiv:1102.4884. doi:10.1007/978-3-642-22300-6_35.
^ Iacono, Johne (2013). „Ve snaze o hypotézu dynamické optimality“. Prostorově efektivní datové struktury, toky a algoritmy. Přednášky z informatiky. 8066: 236–250. arXiv:1306.0207. Bibcode:2013arXiv1306.0207I. doi:10.1007/978-3-642-40273-9_16. ISBN 978-3-642-40272-2.

[DHIKP09-1] A ^b Demaine, Erik D.; Harmon, Dion; Iacono, Johne; Kane, Daniel; Pătraşcu, Mihai (2009), „Geometrie binárních vyhledávacích stromů“, ve sborníku z 20. ročníku sympozia ACM-SIAM o diskrétních algoritmech (SODA 2009), New York: 496–505, doi:10.1137/1.9781611973068.55

[2] Demaine, Erik D.; Harmon, Dion; Iacono, Johne; Pătraşcu, Mihai (2007), „Dynamická optimálnost - téměř“, SIAM Journal on Computing, 37 (1): 240–251, CiteSeerX 10.1.1.99.4964, doi:10.1137 / S0097539705447347, PAN 2306291

[3] Fox, Kyle (15. – 17. Srpna 2011). Horní hranice pro maximálně chamtivé binární vyhledávací stromy (PDF). Algoritmy a datové struktury: 12. mezinárodní sympozium, WADS 2011. Přednášky z informatiky. 6844. New York: Springer. 411–422. arXiv:1102.4884. doi:10.1007/978-3-642-22300-6_35.

[Iacono2013-4] Iacono, Johne (2013). „Ve snaze o hypotézu dynamické optimality“. Prostorově efektivní datové struktury, toky a algoritmy. Přednášky z informatiky. 8066: 236–250. arXiv:1306.0207. Bibcode:2013arXiv1306.0207I. doi:10.1007/978-3-642-40273-9_16. ISBN 978-3-642-40272-2.

[1]

[2]

[3]

[4]