TechCodeview

Před pochopením Červeno-černý strom a strom AVL rozdíly, měli bychom vědět o Red-Black stromu a AVL stromu zvlášť.

Co je to červeno-černý strom?

Červeno-černý strom je vyrovnaný binární vyhledávací strom ve kterém každý uzel obsahuje jeden bit informace navíc, který označuje barvu uzlu. Barva uzlu může být buď červená nebo černá, v závislosti na bitové informaci uložené uzlem.

Vlastnosti

Níže jsou uvedeny vlastnosti spojené s červeno-černým stromem:

• Kořenový uzel stromu by měl být černý.
• Červený uzel může mít pouze černé děti. Nebo můžeme říci, že dva sousední uzly nemohou mít červenou barvu.
• Pokud uzel nemá levého nebo pravého potomka, pak se tento uzel nazývá listový uzel. Vložili jsme tedy levé a pravé potomky pod listový uzel známý jako nula

Hloubku černé nebo výšku černé listového uzlu lze definovat jako počet černých, se kterými se setkáme, když se přesuneme z listového uzlu ke kořenovému uzlu. Jednou z klíčových vlastností stromu Red-Black je, že každý listový uzel by měl mít stejnou hloubku černé.

Pojďme pochopit tuto vlastnost na příkladu.

tostring metoda java

Ve výše uvedeném stromě je pět uzlů, z nichž jeden je červený a další čtyři uzly jsou černé. Ve výše uvedeném stromu jsou tři listové uzly. Nyní vypočítáme černou hloubku každého uzlu listu. Jak můžeme pozorovat, hloubka černé barvy všech tří listových uzlů je 2; proto je to červeno-černý strom.

Pokud se strom neřídí žádnou z výše uvedených tří vlastností, pak to není červeno-černý strom.

Výška červeno-černého stromu

Uvažujme h jako výšku stromu, který má n uzlů. Jaká by byla nejmenší hodnota n?. Hodnota n je nejmenší, když jsou všechny uzly černé. Pokud strom obsahuje všechny černé uzly, pak by strom byl úplný binární strom. Pokud je výška úplného binárního stromu h, pak počet uzlů ve stromu je:

beran herec

n = 2h-1

Jaká by byla největší hodnota n?

Hodnota n je největší, když každý černý uzel má dvě červené děti, ale červený uzel nemůže mít červené děti, takže bude mít černé děti. Takto se střídají vrstvy černých a červených dětí. Je-li tedy počet černých vrstev h, pak počet červených vrstev je také h; proto se celková výška stromu stane 2h. Celkový počet uzlů je:

n = 2 x 2 h-1

Co je strom AVL?

An strom AVL je samovyrovnávací binární vyhledávací strom, pokud dodržíme níže uvedený případ, což je binární vyhledávací strom a vyvážený strom.

Ve výše uvedeném stromu je nejhorší časová složitost pro vyhledávání prvku O(h), tj. výška stromu. Ve výše uvedeném případě je počet porovnání provedených pro vyhledání prvku 17 4 a výška stromu je také 4.

Pokud vezmeme v úvahu zkosený binární strom, jak je znázorněno níže:

Ve výše uvedeném vpravo zkoseném stromu je počet porovnání provedených pro vyhledání prvku 17 5 a počet prvků přítomných ve stromu je také 5. Můžeme tedy říci, že pokud je strom zkoseným binárním stromem, pak časová složitost by bylo O(n).

síťová vrstva v počítačových sítích

Nyní musíme tyto zkosené stromy vyvážit tak, aby měly časovou složitost O(h). Existuje termín známý jako a faktor rovnováhy , který se používá k samovyvažování binárního vyhledávacího stromu. Faktor rovnováhy lze vypočítat takto:

Hodnota faktoru rovnováhy může být buď 1, 0 nebo -1. Pokud má každý uzel v binárním stromu hodnotu buď 1, 0 nebo -1, pak se tento strom považuje za vyvážený binární strom nebo AVL strom.

Strom je známý jako dokonale vyvážený strom, pokud je faktor vyvážení každého uzlu 0. Strom AVL je téměř vyrovnaný strom, protože každý uzel ve stromu má hodnotu faktoru vyvážení buď 1, 0 nebo -1.

Rozdíly mezi stromem Red-Black a stromem AVL.

Níže jsou uvedeny rozdíly mezi stromem Red-Black a stromem AVL:

Binární vyhledávací strom

Červeno-černý strom je binární vyhledávací strom a strom AVL je také binární vyhledávací strom.

filmy z Indie

Pravidla

V červeno-černém stromě platí následující pravidla:

1. Uzel v červeno-černém stromě má červenou nebo černou barvu.
2. Barva kořenového uzlu by měla být černá.
3. Sousední uzly by neměly být červené. Jinými slovy, můžeme říci, že červený uzel nemůže mít červené děti, ale černý uzel může mít černé děti.
4. V každé cestě by měl být stejný počet černých uzlů; pak lze za červeno-černý strom považovat pouze strom.
5. Externí uzly jsou nulové uzly, které mají vždy černou barvu.

Pravidlo stromu AVL:

Každý uzel by měl mít vyvážený faktor buď -1, 0 nebo 1.

Příklad

Na obrázku výše musíme zkontrolovat, zda je strom červeno-černý nebo ne. Abychom to mohli zkontrolovat, musíme nejprve zkontrolovat, zda je strom binárním vyhledávacím stromem nebo ne. Jak můžeme vidět na obrázku výše, splňuje všechny vlastnosti binárního vyhledávacího stromu; jedná se tedy o binární vyhledávací strom. Zadruhé musíme ověřit, zda splňuje výše uvedená pravidla či nikoliv. Výše uvedený strom splňuje všech výše uvedených pět pravidel; proto dochází k závěru, že výše uvedený strom je červeno-černý strom.

Na výše uvedeném obrázku musíme zkontrolovat, zda je strom AVL strom nebo ne. Protože každý uzel má hodnotu faktoru rovnováhy buď -1, 0 nebo 1, jedná se o strom AVL.

Jak lze strom považovat za vyrovnaný strom nebo ne?

V případě červeno-černého stromu, jsou-li splněna všechna výše uvedená pravidla, za předpokladu, že strom je binárním vyhledávacím stromem, pak je strom považován za červeno-černý strom.

V případě stromu AVL, pokud je faktor vyvážení -1, 0 nebo 1, pak se o výše uvedeném stromu říká, že je stromem AVL.

Nástroje používané pro vyvážení

Pokud strom není vyvážený, pak se pro vyvážení stromu v červeno-černém stromě používají dva nástroje:

Přebarvování Otáčení

Pokud strom není vyvážený, pak se pro vyvážení stromu ve stromu AVL použije jeden nástroj:

rekurze java

Otáčení

Efektivní pro který provoz

V případě stromu Red-Black jsou operace vkládání a mazání efektivní. Pokud se strom přebarvením vyrovná, pak operace vkládání a mazání jsou v červeno-černém stromě účinné.

V případě stromu AVL je operace vyhledávání efektivní, protože k vyvážení stromu vyžaduje pouze jeden nástroj.

Časová složitost

V případě Red-Black stromu je časová složitost pro všechny operace, tj. vkládání, mazání a vyhledávání O(logn).

V případě stromu AVL je časová složitost pro všechny operace, tj. vkládání, mazání a vyhledávání O(logn).

Pojďme pochopit rozdíly v tabulkové formě.