Roztáhnout strom - Splay tree
Roztáhnout strom | |||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Typ | strom | ||||||||||||||||||||
Vynalezeno | 1985 | ||||||||||||||||||||
Vynalezl | Daniel Dominic Sleator a Robert Endre Tarjan | ||||||||||||||||||||
Časová složitost v velká O notace | |||||||||||||||||||||
|
A rozložit strom je binární vyhledávací strom s další vlastností, ke které se nedávno přistupovalo k prvkům, je rychlý přístup znovu. Jako samovyvažující binární vyhledávací stromy, splay strom provádí základní operace, jako je vkládání, vyhledávání a odebírání Ó (log n) amortizovaný čas. U mnoha sekvencí nenáhodných operací fungují splay stromy lépe než jiné vyhledávací stromy, dokonce i lépe než O (log n) pro dostatečně nenáhodné vzory, to vše bez nutnosti předchozí znalosti vzorce. Strom roztažení vynalezl Daniel Sleator a Robert Tarjan v roce 1985.[1]
Všechny běžné operace na binárním vyhledávacím stromu jsou kombinovány s jednou základní operací, tzv splaying. Umístěním stromu pro určitý prvek se strom přeskupí tak, aby byl prvek umístěn v kořeni stromu. Jedním ze způsobů, jak to provést pomocí operace základního vyhledávání, je nejprve provést standardní hledání binárního stromu pro daný prvek a poté použít rotace stromů konkrétním způsobem, aby se prvek dostal na vrchol. Alternativně může algoritmus shora dolů kombinovat vyhledávání a reorganizaci stromu do jedné fáze.
Výhody
Dobrý výkon stromu splay závisí na skutečnosti, že se samooptimalizuje, protože často přístupné uzly se přesunou blíže ke kořenu, kde k nim bude možné přistupovat rychleji. Nejhorší výška - i když nepravděpodobná - je O (n), přičemž průměr je O (log nMít často používané uzly v blízkosti kořenového adresáře je výhodou pro mnoho praktických aplikací (viz také referenční lokalita ), a je zvláště užitečný při provádění mezipaměti a odvoz odpadu algoritmy.
Mezi výhody patří:
- Srovnatelný výkon: Průměrný výkon je stejně efektivní jako jiné stromy.[2]
- Malá paměťová stopa: Splay stromy nemusí ukládat žádná data účetnictví.
Nevýhody
Nejvýznamnější nevýhodou stromů je, že výška stromu může být lineární. Bude tomu tak například po přístupu ke všem n prvky v neklesajícím pořadí. Jelikož výška stromu odpovídá nejhorší době přístupu, znamená to, že skutečné náklady na jednu operaci mohou být vysoké. Nicméně amortizovaný cena přístupu v tomto nejhorším případě je logaritmická, O (log n). Očekávané náklady na přístup lze také snížit na O (log n) pomocí randomizované varianty.[3]
Reprezentace stromů rozložení se může změnit, i když k nim přistupujete způsobem „jen pro čtení“ (tj nalézt operace). To komplikuje použití takových splay stromů v prostředí s více vlákny. Konkrétně je nutná další správa, pokud je povoleno provádět více vláken nalézt operace souběžně. To je také činí nevhodnými pro obecné použití v čistě funkčním programování, i když i tam je lze omezeným způsobem použít k implementaci prioritních front.
Konečně, když přístupový vzor je náhodně, další rozkládací režie přidává k nákladům významný konstantní faktor ve srovnání s méně dynamickými alternativami.
Operace
Splaying
Když uzel X je přístupný, provede se operace rozložení X přesunout do kořenového adresáře. Abychom provedli operaci roztažení, provedeme sekvenci rozložit kroky, z nichž každý se pohybuje X blíže ke kořenu. Provedením operace rozložení na zájmovém uzlu po každém přístupu se nedávno přístupné uzly udržují poblíž kořene a strom zůstává zhruba vyvážený, takže dosáhneme požadovaných časových mezí.
Každý konkrétní krok závisí na třech faktorech:
- Zda X je levé nebo pravé dítě svého nadřazeného uzlu, p,
- zda p je kořen nebo ne, a pokud ne
- zda p je levé nebo pravé dítě své rodič, G (dále jen prarodič z x).
Je důležité pamatovat na nastavení např (dále jen prarodič of x) to now point to x after any splay operation. Li např je null, pak x je zjevně nyní root a musí být aktualizováno jako takové.
Existují tři typy kroků rozložení, z nichž každý má dvě symetrické varianty: levá a pravá ruka. Kvůli stručnosti je pro každý typ zobrazen pouze jeden z těchto dvou. (V následujících diagramech kruhy označují zájmové uzly a trojúhelníky sub-stromy libovolné velikosti.) Tři typy kroků rozložení jsou:
Zig krok: tento krok se provádí, když p je kořen. Strom se otáčí na okraji mezi X a p. Zig kroky existují k řešení problému parity, budou provedeny pouze jako poslední krok operace splay, a pouze když X má na začátku operace lichou hloubku.
Krok cik-cak: tento krok se provádí, když p není kořen a X a p jsou buď pravými dětmi, nebo jsou oběmi levými dětmi. Obrázek níže ukazuje případ, kdy X a p jsou obě levé děti. Strom se otáčí na spojovací hraně p s své rodič G, pak se otočil na spojovací hraně X s p. Všimněte si, že zig-zig kroky jsou jediná věc, která odlišuje rozložené stromy od otočit na root metoda zavedená Allenem a Munrem[4] před zavedením stromů.
Krok cik-cak: tento krok se provádí, když p není kořen a X je správné dítě a p je levé dítě nebo naopak. Strom se otáčí na okraji mezi p a x, a pak se otočil na výsledné hraně mezi X a g.
Připojit se
Vzhledem k tomu, že dva stromy S a T jsou takové, že všechny prvky S jsou menší než prvky T, lze k jejich připojení k jednomu stromu použít následující kroky:
- Přehrajte největší položku v S. Nyní je tato položka v kořenu S a má nulové pravé dítě.
- Nastavte správné dítě nového kořene na T.
Rozdělit
Vzhledem k tomu, strom a prvek X, vrátit dva nové stromy: jeden obsahující všechny prvky menší nebo rovné X a další obsahující všechny prvky větší než X. To lze provést následujícím způsobem:
- Splay X. Nyní je v kořenovém adresáři, takže strom nalevo obsahuje všechny prvky menší než X a strom napravo obsahuje všechny prvky větší než X.
- Rozdělte pravý podstrom od zbytku stromu.
Vložení
Chcete-li vložit hodnotu X do rozloženého stromu:
- Vložit X jako u normálu binární vyhledávací strom.
- když je vložena položka, provede se rozložení.
- Výsledkem je nově vložený uzel X se stane kořenem stromu.
Alternativně:
- Pomocí operace rozdělení rozdělíte strom na hodnotu X do dvou sub-stromů: S a T.
- Vytvořte nový strom, ve kterém X je kořen, S je jeho levý podstrom a T pravý podstrom.
Vymazání
Chcete-li odstranit uzel X, použijte stejnou metodu jako u binárního vyhledávacího stromu:
- Li X má dvě děti:
- Zaměňte jeho hodnotu za hodnotu buď nejpravějšího uzlu levého pod stromečka (jeho předchůdce v pořadí), nebo nejlevějšího uzlu pravého podstromu (jeho následného pořadí).
- Místo toho tento uzel odstraňte.
Tímto způsobem je odstranění omezeno na problém odstranění uzlu s 0 nebo 1 dětmi. Na rozdíl od binárního vyhledávacího stromu ve stromu rozložení po odstranění rozložíme rodiče odstraněného uzlu na vrchol stromu.
Alternativně:
- Uzel, který má být odstraněn, je nejprve rozložen, tj. Přenesen do kořenového adresáře stromu a poté odstraněn. opouští strom se dvěma podrostly.
- Dva dílčí stromy jsou poté spojeny pomocí operace „spojení“.
Implementace a varianty
Přehrávání, jak je uvedeno výše, se provádí během druhého průchodu zdola nahoru přes přístupovou cestu uzlu. Je možné zaznamenat přístupovou cestu během prvního průchodu pro použití během druhého, ale to vyžaduje další prostor během operace přístupu. Další alternativou je ponechat nadřazený ukazatel v každém uzlu, čímž se vyhnete potřebě dalšího prostoru během operací přístupu, ale můžete snížit celkovou časovou efektivitu z důvodu nutnosti aktualizovat tyto ukazatele.[1]
Další metoda, která může být použita, je založena na argumentu, že můžeme provést restrukturalizaci stromu cestou dolů po přístupové cestě namísto druhého průchodu. Tato rutina rozložení shora dolů používá tři sady uzlů - levý strom, pravý strom a střední strom. První dva obsahují všechny položky původního stromu, o nichž je známo, že jsou menší než nebo větší než aktuální položka. Prostřední strom se skládá z dílčího stromu zakořeněného v aktuálním uzlu. Tyto tři sady jsou aktualizovány dolů po přístupové cestě, přičemž udržují operace splay pod kontrolou. Další metoda, semisplaying, upravuje případ cik-cak, aby se snížila míra restrukturalizace provedené ve všech operacích.[1][5]
Níže je implementace splay stromů v C ++, která používá ukazatele k reprezentaci každého uzlu ve stromu. Tato implementace je založena na verzi rozložení zdola nahoru a používá druhou metodu odstranění ve stromu rozložení. Na rozdíl od výše uvedené definice tato verze C ++ také funguje ne rozložit strom na nálezy - rozdělí se pouze na vkládání a mazání a operace nálezu má proto lineární časovou složitost.
#zahrnout <functional>#ifndef SPLAY_TREE#define SPLAY_TREEšablona<typename T, typename Comp = std::méně<T>>třída splay_tree {soukromé: Comp komp; nepodepsaný dlouho p_size; struktur uzel { uzel *vlevo, odjet, *že jo; uzel *rodič; T klíč; uzel(konst T& inic = T()) : vlevo, odjet(nullptr), že jo(nullptr), rodič(nullptr), klíč(inic) { } ~uzel() { } } *vykořenit; prázdnota left_rotate(uzel *X) { uzel *y = X->že jo; -li (y) { X->že jo = y->vlevo, odjet; -li (y->vlevo, odjet) y->vlevo, odjet->rodič = X; y->rodič = X->rodič; } -li (!X->rodič) vykořenit = y; jiný -li (X == X->rodič->vlevo, odjet) X->rodič->vlevo, odjet = y; jiný X->rodič->že jo = y; -li (y) y->vlevo, odjet = X; X->rodič = y; } prázdnota right_rotate(uzel *X) { uzel *y = X->vlevo, odjet; -li (y) { X->vlevo, odjet = y->že jo; -li (y->že jo) y->že jo->rodič = X; y->rodič = X->rodič; } -li (!X->rodič) vykořenit = y; jiný -li (X == X->rodič->vlevo, odjet) X->rodič->vlevo, odjet = y; jiný X->rodič->že jo = y; -li (y) y->že jo = X; X->rodič = y; } prázdnota roztáhnout(uzel *X) { zatímco (X->rodič) { -li (!X->rodič->rodič) { -li (X->rodič->vlevo, odjet == X) right_rotate(X->rodič); jiný left_rotate(X->rodič); } jiný -li (X->rodič->vlevo, odjet == X && X->rodič->rodič->vlevo, odjet == X->rodič) { right_rotate(X->rodič->rodič); right_rotate(X->rodič); } jiný -li (X->rodič->že jo == X && X->rodič->rodič->že jo == X->rodič) { left_rotate(X->rodič->rodič); left_rotate(X->rodič); } jiný -li (X->rodič->vlevo, odjet == X && X->rodič->rodič->že jo == X->rodič) { right_rotate(X->rodič); left_rotate(X->rodič); } jiný { left_rotate(X->rodič); right_rotate(X->rodič); } } } prázdnota nahradit(uzel *u, uzel *proti) { -li (!u->rodič) vykořenit = proti; jiný -li (u == u->rodič->vlevo, odjet) u->rodič->vlevo, odjet = proti; jiný u->rodič->že jo = proti; -li (proti) proti->rodič = u->rodič; } uzel* podstrom_minimum(uzel *u) { zatímco (u->vlevo, odjet) u = u->vlevo, odjet; vrátit se u; } uzel* podstrom_maximum(uzel *u) { zatímco (u->že jo) u = u->že jo; vrátit se u; }veřejnost: splay_tree() : vykořenit(nullptr), p_size(0) { } prázdnota vložit(konst T &klíč) { uzel *z = vykořenit; uzel *p = nullptr; zatímco (z) { p = z; -li (komp(z->klíč, klíč)) z = z->že jo; jiný z = z->vlevo, odjet; } z = Nový uzel(klíč); z->rodič = p; -li (!p) vykořenit = z; jiný -li (komp(p->klíč, z->klíč)) p->že jo = z; jiný p->vlevo, odjet = z; roztáhnout(z); p_size++; } uzel* nalézt(konst T &klíč) { uzel *z = vykořenit; zatímco (z) { -li (komp(z->klíč, klíč)) z = z->že jo; jiný -li (komp(klíč, z->klíč)) z = z->vlevo, odjet; jiný vrátit se z; } vrátit se nullptr; } prázdnota vymazat(konst T &klíč) { uzel *z = nalézt(klíč); -li (!z) vrátit se; roztáhnout(z); -li (!z->vlevo, odjet) nahradit(z, z->že jo); jiný -li (!z->že jo) nahradit(z, z->vlevo, odjet); jiný { uzel *y = podstrom_minimum(z->že jo); -li (y->rodič != z) { nahradit(y, y->že jo); y->že jo = z->že jo; y->že jo->rodič = y; } nahradit(z, y); y->vlevo, odjet = z->vlevo, odjet; y->vlevo, odjet->rodič = y; } vymazat z; p_size--; }/ * // alternativní implementace void erase (const T & key) { uzel * z = najít (klíč); if (! z) návrat; splay (z); uzel * s = z-> vlevo; uzel * t = z-> pravý; smazat z; uzel * sMax = NULL; pokud (y) { s-> rodič = NULL; sMax = podstrom_maximum (y); splay (sMax); root = sMax; } pokud (t) { pokud (y) sMax-> doprava = t; jiný root = t; t-> rodič = sMax; } p_size--; }*/ konst T& minimální() { vrátit se podstrom_minimum(vykořenit)->klíč; } konst T& maximum() { vrátit se podstrom_maximum(vykořenit)->klíč; } bool prázdný() konst { vrátit se vykořenit == nullptr; } nepodepsaný dlouho velikost() konst { vrátit se p_size; }};#endif // SPLAY_TREE
Analýza
Jednoduchý amortizovaná analýza statických splay stromů lze provést pomocí potenciální metoda. Definovat:
- velikost(r) = počet uzlů v podstromu zakořeněném v uzlu r (počítaje v to r).
- hodnost(r) = log2(velikost(r)).
- Φ = součet řad všech uzlů ve stromu.
Φ bude mít tendenci být vysoká u špatně vyvážených stromů a nízká u dobře vyvážených stromů.
Chcete-li použít potenciální metoda, nejprve vypočítáme ΔΦ: změnu potenciálu způsobenou splay operací. Každý případ kontrolujeme zvlášť. Po operaci označte pořadím funkci pořadí. x, p a g jsou uzly ovlivněné operací rotace (viz obrázky výše).
Zig krok
ΔΦ = pořadí ′ (p) - pořadí (p) + pořadí ′ (X) - pořadí (X) [protože se mění pouze řady p a x] = pořadí ′ (p) - pořadí (X) [od hodnosti ′ (X) = pořadí (p)] ≤ pozice ′ (X) - pořadí (X) [od hodnosti ′ (p) X)]
Krok cik-cak
ΔΦ = pořadí ′ (G) - pořadí (G) + pořadí ′ (p) - pořadí (p) + pořadí ′ (X) - pořadí (X) = pořadí ′ (G) + pořadí ′ (p) - pořadí (p) - pořadí (X) [od pořadí ′ (x) = hodnocení (g)] ≤ pozice ′ (G) + pořadí ′ (X) - 2 pozice (X) [od hodnosti (X) p) a pořadí ′ (X)> pořadí ′ (p)] ≤ 3 (pořadí ′ (X) −rank (X)) − 2 [kvůli konkávnosti logovací funkce]
Krok cik cak
ΔΦ = pořadí ′ (G) - pořadí (G) + pořadí ′ (p) - pořadí (p) + pořadí ′ (X) - pořadí (X) ≤ pozice ′ (G) + pořadí ′ (p) - 2 pozice (X) [od hodnosti ′ (X) = pořadí (G) a pořadí (X) p)] ≤ 3 (pořadí ′ (X) −rank (X)) − 2 [kvůli konkávnosti logovací funkce]
Amortizovaná cena jakékoli operace je ΔΦ plus skutečná cena. Skutečná cena jakékoli operace cik-cak nebo cik-cak je 2, protože je třeba provést dvě rotace. Proto:
amortizovaná cena = náklady + ΔΦ ≤ 3 (pořadí ′ (X) −rank (X))
Když se to spočítá za celou operaci rozložení, toto dalekohledy do 3 (pořadí (root) −rank (X)), což je O (log n). Operace Zig přidává amortizovanou cenu 1, ale existuje maximálně jedna taková operace.
Takže teď víme, že celkem amortizovaný čas na sekvenci m operace je:
Chcete-li přejít z amortizovaného času na skutečný čas, musíme před provedením jakékoli operace přidat snížení potenciálu z počátečního stavu (Φi) do konečného stavu po dokončení všech operací (ΦF).
kde poslední nerovnost pochází ze skutečnosti, že pro každý uzel X, minimální hodnocení je 0 a maximální hodnocení je log (n).
Nyní můžeme konečně svázat skutečný čas:
Vážená analýza
Výše uvedenou analýzu lze zobecnit následujícím způsobem.
- Přiřadit každému uzlu r váha w(r).
- Definovat velikost (r) = součet hmotností uzlů v podstromu zakořeněném v uzlu r (počítaje v to r).
- Definovat pořadí (r) a Φ přesně jako výše.
Platí stejná analýza a amortizovaná cena operace rozložení je opět:
kde Ž je součet všech vah.
Pokles z počátečního na konečný potenciál je omezen:
protože maximální velikost jednoho uzlu je Ž a minimum je w (x).
Skutečný čas je tedy omezen:
Věty o výkonu
Existuje několik vět a domněnek týkajících se nejhoršího běhového období pro provedení sekvence S z m přistupuje do splay stromu obsahujícího n elementy.
Věta o rovnováze — Náklady na provedení sekvence S je .
Vezměte konstantní váhu, např. pro každý uzel X. Pak .
Tato věta znamená, že splay stromy fungují stejně dobře jako staticky vyvážené binární vyhledávací stromy na sekvenci alespoň n přístupy.[1]
Věta o statické optimitě — Nechat být počet opakování prvku X je přístupný v S. Pokud je každý prvek přístupný alespoň jednou, pak náklady na provedení S je
Nechat . Pak .
Tato věta znamená, že splay stromy fungují stejně dobře jako optimální statický binární vyhledávací strom v sekvenci alespoň n přístupy. Tráví méně času častějšími předměty.[1]
Věta o statickém prstu — Předpokládejme, že položky jsou očíslovány od 1 do n ve vzestupném pořadí. Nechat F být jakýkoli pevný prvek („prst“). Pak náklady na provedení S je .
Nechat . Pak . Čistý potenciální pokles je Ó (n log n) protože váha jakékoli položky je minimálně .[1]
Veta o dynamických prstech — Předpokládejme, že „prst“ pro každý krok přístupu k prvku y je prvek přístupný v předchozím kroku, X. Náklady na provedení S je .[6][7]
Věta o pracovní sadě — Kdykoli během sekvence nechte být počet odlišných prvků přístupných před přístupem k předchozímu časovému prvku x. Náklady na provedení S je
Nechat . Všimněte si, že zde se váhy během sekvence mění. Pořadí vah je však stále permutací . Tak jako předtím . Čistý potenciální pokles je Ó (n log n).
Tato věta je ekvivalentní s rozložitými stromy optimita nezávislá na klíči.[1]
Skenovací věta — Také známý jako Věta o sekvenčním přístupu nebo Věta o frontě. Přístup k n prvky stromu rozložení v symetrickém pořadí trvá Ó(n) čas, bez ohledu na počáteční strukturu rozloženého stromu.[8] Dosud prokázaná nejtěsnější horní hranice .[9]
Domněnka o dynamické optimitě
Nevyřešený problém v informatice: Fungují splay stromy stejně dobře jako jakýkoli jiný algoritmus binárního vyhledávacího stromu? (více nevyřešených problémů v informatice) |
Kromě osvědčených záruk výkonu pro rozložené stromy existuje i neprokázaná domněnka velkého zájmu z původního papíru Sleator a Tarjan. Tato domněnka je známá jako domněnka dynamické optimality a v podstatě tvrdí, že splay stromy fungují stejně jako jakýkoli jiný algoritmus binárního vyhledávacího stromu až do konstantního faktoru.
- Domněnka dynamické optimality:[1] Nechat být libovolný algoritmus binárního vyhledávacího stromu, který přistupuje k prvku přejetím cesty od kořene k za cenu , a to mezi přístupy může provádět jakékoli rotace ve stromu za cenu 1 za rotaci. Nechat být cenou za provést sekvenci přístupů. Pak je cena za to, že strom splay provede stejné přístupy .
Existuje několik důsledků domněnky dynamické optimality, které zůstávají neprokázané:
- Traverzální domněnka:[1] Nechat a být dva rozložené stromy obsahující stejné prvky. Nechat být sekvence získaná návštěvou prvků v v předobjednávce (tj. pořadí vyhledávání podle hloubky). Celkové náklady na provedení sekvence přístupů zapnuto je .
- Deque domněnka:[8][10][11] Nechat být posloupností oboustranná fronta operace (push, pop, inject, eject). Pak náklady na provedení na rozevřeném stromu je .
- Split dohad:[5] Nechat být jakákoli obměna prvků rozloženého stromu. Pak náklady na odstranění prvků v objednávce je .
Varianty
Aby se snížil počet restrukturalizačních operací, je možné splaying nahradit částečně rozložené, ve kterém je prvek roztažen pouze do poloviny směrem ke kořenu.[1][12]
Dalším způsobem, jak omezit restrukturalizaci, je úplné rozložení, ale pouze v některých přístupových operacích - pouze když je přístupová cesta delší než prahová hodnota, nebo pouze v první m operace přístupu.[1]
Viz také
- Prst strom
- Propojit / vyříznout strom
- Obětní beránek strom
- Zip (datová struktura)
- Stromy
- Střídání stromů
- Strom AVL
- B-strom
- T-strom
- Seznam datových struktur
- Struktura pracovní sady Iacono
- Geometrie binárních vyhledávacích stromů
- Splaysort, třídicí algoritmus využívající rozložené stromy
- Šlapat
Poznámky
Reference
- Albers, Susanne; Karpinski, Marek (28. února 2002). „Randomizované rozložené stromy: teoretické a experimentální výsledky“ (PDF). Dopisy o zpracování informací. 81 (4): 213–221. doi:10.1016 / s0020-0190 (01) 00230-7.CS1 maint: ref = harv (odkaz)
- Allen, Brian; Munro, Ian (říjen 1978). "Samoorganizující se binární vyhledávací stromy". Deník ACM. 25 (4): 526–535. doi:10.1145/322092.322094. S2CID 15967344.CS1 maint: ref = harv (odkaz)
- Brinkmann, Gunnar; Degraer, Jan; De Loof, Karel (leden 2009). „Rehabilitace nemilovaného dítěte: napůl rozepjatá“ (PDF). Software - praxe a zkušenosti. 39 (1): 33–45. CiteSeerX 10.1.1.84.790. doi:10.1002 / spe.v39: 1. hdl:11382/102133.
Výsledky ukazují, že semi-splaying, který byl zaveden na stejném papíru jako splaying, funguje lépe než splaying za téměř všech možných podmínek. Díky tomu je semi-splaying dobrou alternativou pro všechny aplikace, kde by se normálně používalo splaying. Důvod, proč se splaying stal tak výrazným, zatímco semi-splaying je relativně neznámý a mnohem méně studovaný, je těžké pochopit.
CS1 maint: ref = harv (odkaz)
- Cole, Richard; Mishra, Bud; Schmidt, Jeanette; Siegel, Alan (leden 2000). „O dohadech dynamických prstů pro roztahovací stromy. Část I: Splay třídění log n-Block sekvence“. SIAM Journal on Computing. 30 (1): 1–43. CiteSeerX 10.1.1.36.4558. doi:10.1137 / s0097539797326988.CS1 maint: ref = harv (odkaz)
- Cole, Richard (leden 2000). „O dohadech dynamických prstů pro rozložené stromy. Část II: Důkaz“. SIAM Journal on Computing. 30 (1): 44–85. CiteSeerX 10.1.1.36.2713. doi:10.1137 / S009753979732699X.CS1 maint: ref = harv (odkaz)
- Elmasry, Amr (duben 2004), „O teorému sekvenčního přístupu a domněnce Deque pro rozložené stromy“, Teoretická informatika, 314 (3): 459–466, doi:10.1016 / j.tcs.2004.01.019CS1 maint: ref = harv (odkaz)
- Goodrich, Michael; Tamassia, Roberto; Goldwasser, Michael (2014). Datové struktury a algoritmy v Javě (6. vyd.). Wiley. p. 506. ISBN 978-1-118-77133-4.CS1 maint: ref = harv (odkaz)
- Knuth, Donald (1997). Umění počítačového programování. 3: Třídění a vyhledávání (3. vydání). Addison-Wesley. p. 478. ISBN 0-201-89685-0.CS1 maint: ref = harv (odkaz)
- Lucas, Joan M. (1991). „O konkurenceschopnosti stromů Splay: vztahy k problému Unie - najít“. On-line algoritmy: Sborník workshopů DIMACS, 11. – 13. Února 1991. Seriály v diskrétní matematice a teoretické informatice. 7. Centrum diskrétní matematiky a teoretické informatiky. str. 95–124. ISBN 0-8218-7111-0.CS1 maint: ref = harv (odkaz)
- Pettie, Seth (2008), „Splay Trees, Davenport-Schinzel Sequences, and the Deque Conjecture“ (PDF), Proc. 19. ACM-SIAM Symposium on Discrete Algorithms, 0707: 1115–1124, arXiv:0707.2160, Bibcode:2007arXiv0707.2160PCS1 maint: ref = harv (odkaz)
- Kráječ, Daniel D.; Tarjan, Robert E. (1985). „Samonastavitelné binární vyhledávací stromy“ (PDF). Deník ACM. 32 (3): 652–686. doi:10.1145/3828.3835. S2CID 1165848.CS1 maint: ref = harv (odkaz)
- Sundar, Rajamani (1992). "Na hypotéze Deque pro splay algoritmus". Combinatorica. 12 (1): 95–124. doi:10.1007 / BF01191208. S2CID 27422556.CS1 maint: ref = harv (odkaz)
- Tarjan, Robert E. (1985). "Sekvenční přístup ve splay stromech trvá lineárně". Combinatorica. 5 (4): 367–378. doi:10.1007 / BF02579253. S2CID 34757821.CS1 maint: ref = harv (odkaz)