Červený Černý Strom, Rotace a Barvu Salta

Thamindu Dilshan Jayawickrama
Thamindu Dilshan Jayawickrama

Sledovat

Jul 11, 2020 · 6 min číst

typické vyhledávací strom Binární Vyhledávací Strom (BST), by mohl spustit do výšky O(n), což by mohlo vést v nejhorším případě časovou složitost O(n) pro základní operace, jako je vyhledávání, vkládání, mazání, atd. To zcela závisí na pořadí položek, které jsou vloženy do BST. Ale existují určité situace, kdy nemáme celou položku nastavenou při zahájení konstrukce stromu. To je místo, kde vyvážené vyhledávací stromy vstupují do hry. Ve vyváženém vyhledávacím stromu je při implementaci dynamické sady n položek zaručena výška o(log n). Červeno-černé stromy, AVL stromy, 2-3 stromy a B-stromy jsou některé z příkladů vyvážených implementací vyhledávacích stromů. Tento článek je o úpravách stromů zapojených do červeno-černých stromů.

červeno-černý strom (RB-strom) je samovyvažující binární vyhledávací strom, kde každý uzel sleduje sadu pravidel. Každý uzel v RB stromu má jeden další atribut; barva, která může být buď červená nebo černá. V typické implementaci RB-stromu bude k dispozici sada sentinelových uzlů, které označí, že je dosaženo uzlu listu. Tyto uzly jsou v tomto článku označovány jako nuly (nebo NILs) a považovány za uzly listů. Níže je uvedena sada pravidel nebo vlastností, které by měl každý uzel dodržovat.

  1. každý uzel je buď červený nebo černý.

2. Kořen a listy jsou černé.

3. Pokud je uzel červený, pak jeho rodič je černý.

4. Všechny jednoduché cesty z libovolného uzlu potomka listu mají stejný počet černých uzlů (černá-na výšku).

výška RB-Strom zůstává na O(log n) po každý strom modifikace operaci, která vyústila ve zaručenou horní mez O(log n) pro tyto operace. Operace Vložit a odstranit způsobí změny stromu RB. Po každé operaci modifikace stromu bude strom vyvážen pomocí barevných změn a rotací. Než se pustíme do těchto operací, měli bychom se seznámit s následujícím zápisem.

rotace je speciální operace, který je určen pro self-vyvažování Binárních Vyhledávacích Stromů, které lze provést v O(1) času. Zajímavou vlastností rotací je, že zachovává inorder procházení klíčů(řazení klíčů).

Rozhodnutí k provedení rotace nebo změna barvy je založen na teta za uzel (aktuální uzel). Pokud má uzel černou tetu, uděláme rotaci. Pokud má uzel červenou tetu, uděláme barevný flip. Po provedení rotace bychom měli strom barevně opravit. Po provedení těchto operací by strom měl být ukončen jako níže.

Pokud je aktuální uzel je nechal dítě jeho prarodiče dítě vlevo, máme právo otočit prarodiče kolem mateřské. Pokud je současný uzel pravým dítětem pravého dítěte jeho prarodiče, nechali jsme prarodiče otočit kolem rodiče. Pokud je aktuální uzel pravým dítětem levého dítěte jeho prarodiče, provádíme rotaci vlevo-vpravo, kde otáčíme prarodiče a dítě kolem rodiče. Pokud je aktuální uzel levým dítětem pravého dítěte jeho prarodiče, provádíme pravo-levou rotaci, kde otáčíme prarodiče a dítě kolem rodiče. Všechny rotace lze shrnout podle níže uvedeného diagramu.

Jednu důležitou skutečnost na paměti, je, že po provedení nějaké strom modifikace operace, měli byste ověřit strom proti soubor pravidel, aby zjistil, jestli nějaké porušení jsou tam. Pokud dojde k porušení (např. kořen je červený), měli byste jej opravit. Nyní pojďme postavit jednoduchý RB-strom vložením pod sadu klíčů. Všimněte si, že pro jednoduchost jsou uzly listů (NULL) v níže uvedených diagramech ignorovány.

5, 8, 1, 10, 9, 15, 20

každý klíč bychom měli vložit jako červený uzel. Proto vložíme 5 jako červený uzel a okamžitě jej zbarvíme zpět na černou, protože je to kořenový uzel. Pak vložíme 8 jako pravé dítě uzlu 5. při vkládání klíčů dodržujeme základní vlastnost BST. Vložení 1 je stejné jako vložení 8.

Next, bychom měli vložit 10 8 právo dítěte. Vložíme jej jako červený uzel a zkontrolujeme porušení. Oba 8 a 10 jsou červené uzly a porušují vlastnost 3rd. Měli bychom zkontrolovat tetu a je červená. Takže provedeme barevné převrácení. Po převrácení barvy vidíme, že kořenový uzel je červený a porušuje vlastnost 2nd. Takže to opravíme změnou barvy kořenového uzlu.

Next, měli bychom vložte klíč 9. Po vložení vidíme, že oba uzly 9 a 10 jsou červené a porušují vlastnost 2nd. Zkontrolujeme tetu a protože je černá (NULL je černá), provádíme rotaci vpravo-vlevo (porušení je v levém podstromu pravého dítěte). Po otočení bychom měli udělat barevnou opravu.

Teď pojďme vložte klíč 15. Po vložení vidíme, že existují dva po sobě jdoucí červené uzly a teta 15 je červený uzel. Takže bychom měli udělat barevné Salto. Poté zkontrolujeme případné porušení a zjistíme, že tam nejsou žádná porušení.

Teď pojďme vložte klíč od 20 do stromu. Po vložení vidíme, že teta je černá, a proto bychom měli provést levou rotaci(porušení je v pravém podstromu dítěte). Po otočení bychom měli udělat barevnou opravu.

V tomto článku jsme se zaměřili na konkrétní samovyvažující se binární vyhledávací strom; Červeno-Černý Strom. Je zaručeno, že mají výšku O (log n), proto mají pro základní stromové operace nejhorší časovou složitost O(log n). Červeno-černé stromy jsou zvláště užitečné v mnoha aplikacích informatiky. C++ Standard Template Library (STL) má set, multiset, map a multimap založený na RB-stromy. Také TreeMap v jazyce Java je implementace NavigableMap založená na RB-stromu.

Napsat komentář

Vaše e-mailová adresa nebude zveřejněna.