WAVL strom - WAVL tree

v počítačová věda, a WAVL strom nebo slabý strom AVL je samovyvažující binární vyhledávací strom. Stromy WAVL jsou pojmenovány po AVL stromy, jiný typ vyváženého vyhledávacího stromu, a úzce souvisí jak se stromy AVL, tak s červeno-černé stromy, které všechny spadají do společného rámce řadit vyvážené stromyStejně jako jiné vyvážené binární vyhledávací stromy mohou i stromy WAVL zpracovávat operace vkládání, mazání a vyhledávání v čase Ó(log n) na operaci.^[1][2]

Stromy WAVL jsou navrženy tak, aby kombinovaly některé z nejlepších vlastností stromů AVL a červeno-černých stromů. Jednou z výhod stromů AVL oproti červeno-černým stromům je vyrovnanější: mají maximálně výšku ${ displaystyle log _ { varphi} n přibližně 1,44 log _ {2} n}$ (pro strom s n datové položky, kde ${ displaystyle varphi}$ je Zlatý řez ), zatímco červeno-černé stromy mají větší maximální výšku, ${ displaystyle 2 log _ {2} n}$. Pokud je strom WAVL vytvořen pouze pomocí vložení, bez odstranění, má stejnou malou výškovou hranici, jakou má strom AVL. Na druhou stranu, červeno-černé stromy mají výhodu oproti stromům AVL v menší restrukturalizaci jejich stromů. Ve stromech AVL může každé odstranění vyžadovat logaritmický počet rotace stromu operace, zatímco červeno-černé stromy mají jednodušší operace mazání, které používají pouze konstantní počet rotací stromů. Stromy WAVL, stejně jako červeno-černé stromy, používají pouze konstantní počet rotací stromů a konstanta je ještě lepší než u červeno-černých stromů.^[1][2]

Stromy WAVL byly zavedeny Haeupler, Sen & Tarjan (2015). Stejní autoři také poskytli společný pohled na stromy AVL, stromy WAVL a červeno-černé stromy, protože všechny jsou typem stromů vyvážených podle pořadí.^[2]

Definice

Stejně jako u binárních vyhledávacích stromů obecně se strom WAVL skládá ze sbírky uzly dvou typů: interní uzly a externí uzly. Interní uzel ukládá datovou položku a je propojen s jejím nadřazeným prvkem (s výjimkou určeného kořenového uzlu, který nemá žádného nadřazeného člena) a přesně dvěma podřízenými položkami ve stromu, levým podřízeným a pravým podřízeným. Externí uzel nenese žádná data a má odkaz pouze na svého rodiče ve stromu. Tyto uzly jsou uspořádány tak, aby tvořily binární strom, takže pro jakýkoli vnitřní uzel X rodiče levého a pravého dítěte X jsou X sám. Vnější uzly tvoří listy stromu.^[3] Datové položky jsou ve stromu uspořádány tak, že: inorder traversal stromu uvádí datové položky v seřazeném pořadí.^[4]

To, co odlišuje WAVL stromy od jiných typů binárního vyhledávacího stromu, je jeho použití hodnosti. Jedná se o čísla přidružená ke každému uzlu, která poskytují přibližnou vzdálenost od uzlu k jeho nejvzdálenějšímu potomkovi. Na rozdíl od stromů AVL, kde jsou pozice definovány stejně jako výšky uzlů, pozice se ne vždy rovnají výškám ve stromech WAVL. The rozdíl v pořadí uzlu x je definován jako rozdíl mezi hodností rodiče x a hodností x. Řady jsou povinny dodržovat následující vlastnosti:^[1][2]

• Vlastnost externího uzlu: Každý externí uzel má hodnocení 0^[5]
• Vlastnost Rank-Difference: Pokud má uzel bez oprávnění root root r, potom musí být hodnost jeho rodiče buď r + 1 nebo r + 2. Jinými slovy, rozdíl v pořadí pro libovolný uzel bez oprávnění root je 1 nebo 2.^[1]
• Vlastnost Internal-Node: Interní uzel se dvěma externími podřízenými prvky musí mít hodnocení přesně 1.

Operace

Hledání

Hledání klíče k ve stromu WAVL je téměř stejný jako v jakékoli vyvážené datové struktuře binárního vyhledávacího stromu. Jeden začíná u kořene stromu a poté opakovaně porovnává k s datovou položkou uloženou v každém uzlu na cestě z kořene, sledující cestu k levému dítěti uzlu, když k je menší než hodnota v uzlu nebo místo toho sleduje cestu ke správnému dítěti, když k je větší než hodnota v uzlu. Když uzel s hodnotou rovnou k je dosaženo, nebo je dosažen externí uzel, hledání se zastaví.^[6]

Pokud se vyhledávání zastaví na interním uzlu, klíč k bylo nalezeno. Pokud se místo toho hledání zastaví na externím uzlu, pak na pozici kde k bylo vloženo (pokud bylo vloženo) bylo nalezeno.^[6]

Vložení

Vložení interního uzlu pomocí klíče k do stromu WAVL vyžaduje hledání k ve stromu, končící na externím uzlu, pak nahrazení tohoto externího uzlu novým interním uzlem se dvěma externími podřízenými a nakonec opětovné vyvážení stromu. Krok vyvážení lze provést buď shora dolů nebo zdola nahoru,^[2] ale verze rebalancingu zdola nahoru je ta, která nejvíce odpovídá stromům AVL.^[1][2]

Vyvažování zdola nahoru začíná zvážením rozdílu mezi uzlem - původně nově vloženým uzlem - a průhledným. Pokud není rodič, rovnováha se obnoví. Před začátkem vložení byl rozdíl mezi rodiči a uzlem 1 nebo 2, ale tento rozdíl byl snížen o 1, protože subtreeroot v uzlu vzrostl. Pokud je nový rozdíl mezi rodiči a uzlem 1, rovnováha se obnoví. V opačném případě, pokud má dítě, druhé dítě rodiče, u rodičů rozdíl v pořadí 1, povýší rodiče - zvýší jejich hodnocení zvýšením rozdílů mezi nimi a každým z jeho dětí - a bude pokračovat v rovnováze se starým rodičem jako novým uzel.

A konečně, s rozdílem v pořadí 0 a 2 pro uzel a sourozence, jedno nebo dvě rotace stromu, s přidruženými úpravami rozdílů v pořadí, mohou obnovit rovnováhu. Mezi dítětem uzlu je ten, který má klíče mezi klíči uzlu a rodiči. Pokud je rozdíl v pořadí pro toto dítě a uzel 2, otočením posunete uzel nahoru ve stromu a nadřazeným prvkem, poté degradujete nadřazeného - snížíte jeho pořadí úpravou rozdílů kolem sebe - a rovnováha se obnoví. V opačném případě otočením posunete dítě nahoru a uzel dolů a poté znovu otočíte, aby se dítě zvedlo nahoru a rodič dolů. Povýšte dítě, degradujte uzel a rodiče a rovnováha se obnoví.

Procedura vložení tedy celkově sestává z vyhledávání, vytváření konstantního počtu nových uzlů, logaritmického počtu změn pořadí a konstantního počtu rotací stromů.^[1][2]

Vymazání

Odstranění interního uzlu ze stromu WAVL začíná běžnýmvymazání binárního vyhledávacího stromu. Pro interní uzel s noexternal potomkem to znamená najít jeho následníka ve stromu, vyměnit uzel s jeho následníkem a poté odebrat uzel z jeho nové pozice stromu, kde jeho levé dítě je nutně externí uzel. Chcete-li odebrat interní uzel s externím podřízeným prvkem, nahraďte uzel druhým podřízeným prvkem.

Vyvažování zdola nahoru začíná zvážením rozdílu mezi uzly - zpočátku uzlem, který nahradil odstraněný uzel - a jeho nadřazeným prvkem. Pokud není rodič, rovnováha se obnoví. Před zahájením mazání byl rozdíl mezi rodiči a uzlem 1 nebo 2, ale tento rozdíl byl zvýšen o 1, protože podřízený cíl v uzlu se zkrátil. Pokud má nadřazený objekt nyní dvě externí děti, je vlastnost interního uzlu porušena, protože nadřazený má pořadí 2. Nadřazený prvek musí být degradován a rebalancování pokračuje s nadřazeným uzlem, který je kořenem příliš krátkého podstromu.

Pokud uzel nemá žádného rodiče, rovnováha se obnoví. Pokud se rozdíl mezi uzlem a rodičem zvýšil z 1 na 2, rovnováha se obnoví. V opačném případě, pokud má sourozenec, druhé dítě rodiče, rozdíl v pořadí 2 s rodičem, degradovat rodiče - snížit jeho pořadí snížením rozdílu v pořadí mezi ním a každým z jeho dětí - a pokračovat v rovnováze se starým rodičem jako nový uzel. V opačném případě, pokud dvě děti sourozence mají rozdíl 2 se sourozencem, degradujte rodiče a sourozence a pokračujte ve vyvážení se starým rodičem jako novým uzlem.

A konečně, s rozdílem v pořadí 3 a 1 pro uzel a sourozence a se sourozencem, který má dítě s rozdílem v pořadí 1, může jedna nebo dvě treerotace s přidruženými úpravami rozdílů v pořadí obnovit rovnováhu. Identifikujte děti sourozence jako neteř a synovec, kde klíč neteře leží mezi klíči rodiče a sourozence a klíč synovce ne. Pokud je terapeutický rozdíl mezi sourozencem a synovcem 1, otočte jej tak, aby se pohyboval nahoru a nadřazený dolů, propagujte sourozence a alespoň v případě potřeby degradujte nadřazenou položku, aby nedošlo k porušení vlastnosti interního uzlu. Jinak s rozdílem mezi hodnostmi mezi synovcem a synovcem 1, otočením posunete neteř nahoru a sourozencem, otočením znovu posunete neteř nahoru a rodičem dolů, dvakrát povýšíte neteř, jednou degradujete sourozence a dvakrát degradujete rodiče.

Celkově smazání spočívá v hledání směrem dolů, aby se našel uzel s externím dítětem, v odstranění konstantního počtu nových uzlů, v logaritmickém počtu změn pořadí a v konstantním počtu rotací stromů. [1] [2]

Stojí za to porovnat výsledek mazání, které by způsobilo rotace na více úrovních ve stromu AVL, se změnami rotace a pořadí provedenými ve stromu WAVL. Na druhém obrázku byl odstraněn uzel s hodnotou 12 následovaný pravou rotací a přiřazením všech externích uzlů pořadí nula.

Fibonacciho strom s řadami

Fibonacciho strom s řadami po odstranění

Výpočetní složitost

Každé hledání, vložení nebo odstranění ve stromu WAVL zahrnuje sledování jedné cesty ve stromu a provedení konstantního počtu kroků pro každý uzel v cestě. Ve stromu WAVL s n u položek, které prošly pouze vložením, je maximální délka cesty ${ displaystyle log _ { varphi} n přibližně 1,44 log _ {2} n}$. Pokud mohlo dojít k vložení i smazání, je maximální délka cesty ${ displaystyle 2 log _ {2} n}$. Proto v obou případech nejhorší čas pro každé hledání, vložení nebo odstranění ve stromu WAVL s n datových položek je Ó(log n).

Navíc po nalezení uzlu pro vložení a odstranění je amortizovaná složitost operací restrukturalizace stromu konstantní. Přidání nebo odstranění samotného uzlu je konstantní čas, množství rotací je vždy nanejvýš konstantní a je možné ukázat, že celkový počet změn pořadí v uzlech je lineární v počtu vložení i odstranění.

Související struktury

Stromy WAVL jsou úzce spjaty s oběma AVL stromy a červeno-černé stromy Každý strom AVL může mít k jeho uzlům přiřazeny pozice takovým způsobem, který z něj dělá strom WAVL. A každý strom WAVL může mít své uzly zbarvené červeně a černě (a jeho řady znovu přiřazeny) způsobem, který z něj dělá červeno-černý strom. Některé stromy WAVL však nepocházejí ze stromů AVL tímto způsobem a některé červeno-černé stromy nepocházejí ze stromů WAVL tímto způsobem.

AVL stromy

Strom AVL je druh vyváženého binárního vyhledávacího stromu, ve kterém dvě děti každého vnitřního uzlu musí mít výšky, které se liší maximálně o jeden.^[7] Výška externího uzlu je nula a výška jakéhokoli interního uzlu je vždy jedna plus maximum výšek jeho dvou podřízených. Výšková funkce stromu AVL se tedy řídí omezeními stromu WAVL a můžeme libovolný strom AVL převést na strom WAVL pomocí výšky každého uzlu jako jeho pořadí.^[1][2]

Klíčový rozdíl mezi stromem AVL a stromem WAVL vzniká, když má uzel dvě děti se stejnou hodností nebo výškou. Ve stromu AVL, pokud je uzel X má dvě děti stejné výšky h jako každý jiný, pak výška X musí být přesně h + 1. Naproti tomu ve stromu WAVL, pokud je to uzel X má dvě děti stejné hodnosti r jako každý jiný, pak hodnost X může být buď r + 1 nebo r + 2. Důvodem je, že pozice se striktně nerovná výšce ve stromu WAVL. Tato větší flexibilita v řadách také vede k větší flexibilitě struktur: některé stromy WAVL nelze změnit na stromy AVL ani úpravou jejich řad, protože obsahují uzly, jejichž výšky dětí se liší o více než jeden.^[2] Můžeme však říci, že všechny stromy AVL jsou stromy WAVL. Stromy AVL jsou stromy WAVL bez typu uzlu, který má obě děti v rozdílu 2.^[1]

Pokud je strom WAVL vytvořen pouze pomocí operací vložení, bude jeho struktura stejná jako struktura stromu AVL vytvořeného stejnou sekvencí vložení a jeho pozice budou stejné jako pozice odpovídajícího stromu AVL. Pouze pomocí operací odstranění se strom WAVL může lišit od stromu AVL. Z toho zejména vyplývá, že strom WAVL vytvořený pouze prostřednictvím vložení má maximálně výšku ${ displaystyle log _ { varphi} n přibližně 1,44 log _ {2} n}$.^[2]

Červeno-černé stromy

A červeno-černý strom je vyvážený binární vyhledávací strom, ve kterém má každý uzel barvu (červenou nebo černou) a splňuje následující vlastnosti:

• Externí uzly jsou černé.
• Pokud je vnitřní uzel červený, jeho dvě podřízené položky jsou černé.
• Všechny cesty od kořene k externímu uzlu mají stejný počet černých uzlů.

Červeno-černé stromy lze ekvivalentně definovat z hlediska systému řad uložených v uzlech, které splňují následující požadavky (odlišné od požadavků na řady ve stromech WAVL):

• Hodnost externího uzlu je vždy 0 a hodnost jeho rodiče je vždy 1.
• Pořadí libovolného kořenového uzlu se rovná buď hodnocení jeho rodiče, nebo hodnocení jeho rodiče mínus 1.
• Žádné dva po sobě jdoucí okraje na žádné cestě kořenových listů nemají rozdíl 0.

Ekvivalenci mezi definicemi založenými na barvě a pořadí lze vidět v jednom směru zbarvením uzlu černou barvou, pokud má její nadřazená hodnost vyšší a červenou barvou, pokud má její nadřazená hodnost stejná. V opačném směru lze barvy převést na hodnosti tak, že se pořadí černého uzlu bude rovnat počtu černých uzlů na jakékoli cestě k vnějšímu uzlu a že se hodnost červeného uzlu bude rovnat jeho nadřazenému prvku.^[8]

Řady uzlů ve stromu WAVL lze převést na systém řad uzlů, který splňuje požadavky na červeno-černé stromy, dělením každé úrovně dvěma a zaokrouhlením nahoru na nejbližší celé číslo.^[9] Kvůli této konverzi existuje pro každý strom WAVL platný červeno-černý strom se stejnou strukturou. Protože červeno-černé stromy mají maximální výšku ${ displaystyle 2 log _ {2} n}$, totéž platí pro stromy WAVL.^[1][2] Existují však červeno-černé stromy, kterým nelze poskytnout platnou funkci pořadí stromů WAVL.^[2]

Navzdory skutečnosti, že z hlediska jejich stromových struktur jsou stromy WAVL zvláštními případy červeno-černých stromů, jejich aktualizační operace se liší. Rotace stromů používané při operacích aktualizace stromu WAVL mohou provádět změny, které by nebyly povoleny v červeno-černém stromu, protože by ve skutečnosti způsobily přebarvení velkých podstromů červeno-černého stromu, spíše než provádět barevné změny pouze na jednom cesta ve stromu.^[2] To umožňuje stromům WAVL provádět méně rotací stromů na odstranění, v nejhorším případě, než červeno-černé stromy.^[1][2]

Reference