TechCodeview

Pred pochopením Červeno-čierny strom a strom AVL rozdiely, mali by sme vedieť o červeno-čiernom strome a AVL strome oddelene.

Čo je to červeno-čierny strom?

Červeno-čierny strom je vyrovnaný binárny vyhľadávací strom v ktorej každý uzol obsahuje jeden bit informácie navyše, ktorý označuje farbu uzla. Farba uzla môže byť buď červená alebo čierna, v závislosti od bitovej informácie uloženej uzlom.

Vlastnosti

Nasledujúce vlastnosti sú spojené s červeno-čiernym stromom:

• Koreňový uzol stromu by mal byť čierny.
• Červený uzol môže mať iba čierne deti. Alebo môžeme povedať, že dva susedné uzly nemôžu mať červenú farbu.
• Ak uzol nemá ľavé alebo pravé dieťa, potom sa tento uzol nazýva listový uzol. Takže ľavé a pravé dieťa umiestnime pod listový uzol známy ako nula

Čierna hĺbka alebo čierna výška listového uzla môže byť definovaná ako počet čiernej, s ktorým sa stretneme, keď sa presunieme z listového uzla ku koreňovému uzlu. Jednou z kľúčových vlastností červeno-čierneho stromu je, že každý listový uzol by mal mať rovnakú hĺbku čiernej.

Poďme pochopiť túto vlastnosť na príklade.

Vo vyššie uvedenom strome je päť uzlov, z ktorých jeden je červený a ďalšie štyri uzly sú čierne. Vo vyššie uvedenom strome sú tri listové uzly. Teraz vypočítame hĺbku čiernej farby každého uzla listu. Ako môžeme pozorovať, hĺbka čiernej farby všetkých troch listových uzlov je 2; teda je to červeno-čierny strom.

Ak strom nespĺňa žiadnu z vyššie uvedených troch vlastností, potom to nie je červeno-čierny strom.

mylivericket

Výška červeno-čierneho stromu

Uvažujme h ako výšku stromu s n uzlami. Aká by bola najmenšia hodnota n?. Hodnota n je najmenšia, keď sú všetky uzly čierne. Ak strom obsahuje všetky čierne uzly, potom by bol strom úplným binárnym stromom. Ak je výška úplného binárneho stromu h, potom počet uzlov v strome je:

n = 2h-1

Aká by bola najväčšia hodnota n?

Hodnota n je najväčšia, keď každý čierny uzol má dve červené deti, ale červený uzol nemôže mať červené deti, takže bude mať čierne deti. Takto sa striedajú vrstvy čiernych a červených detí. Takže, ak je počet čiernych vrstiev h, potom počet červených vrstiev je tiež h; preto je celková výška stromu 2h. Celkový počet uzlov je:

n = 2 x 2 h-1

Čo je strom AVL?

An AVL strom je samovyvažovací binárny vyhľadávací strom, ak pozorujeme nižšie uvedený prípad, ktorým je binárny vyhľadávací strom a vyvážený strom.

Vo vyššie uvedenom strome je najhorší prípad časovej zložitosti pre vyhľadávanie prvku O(h), t.j. výška stromu. Vo vyššie uvedenom prípade je počet porovnaní vykonaných pre prvok vyhľadávania 17 4 a výška stromu je tiež 4.

Ak vezmeme do úvahy skosený binárny strom, ako je uvedené nižšie:

Vo vyššie uvedenom skosom strome vpravo je počet porovnaní vykonaných na vyhľadanie prvku 17 5 a počet prvkov prítomných v strome je tiež 5. Preto môžeme povedať, že ak je strom skosený binárny strom, potom časová zložitosť by bolo O(n).

Teraz musíme tieto zošikmené stromy vyvážiť tak, aby mali časovú zložitosť O(h). Existuje pojem známy ako a faktor rovnováhy , ktorý sa používa na samovyvažovanie binárneho vyhľadávacieho stromu. Faktor rovnováhy možno vypočítať takto:

Hodnota bilančného faktora môže byť buď 1, 0 alebo -1. Ak má každý uzol v binárnom strome hodnotu buď 1, 0 alebo -1, potom sa tento strom považuje za vyvážený binárny strom alebo AVL strom.

Strom je známy ako dokonale vyvážený strom, ak je faktor rovnováhy každého uzla 0. Strom AVL je takmer vyrovnaný strom, pretože každý uzol v strome má hodnotu faktora rovnováhy buď 1, 0 alebo -1.

Rozdiely medzi červeno-čiernym stromom a AVL stromom.

Nasledujú rozdiely medzi stromom Red-Black a stromom AVL:

sqrt java matematika

Binárny vyhľadávací strom

Červeno-čierny strom je binárny vyhľadávací strom a strom AVL je tiež binárny vyhľadávací strom.

pravidlá

V červeno-čiernom strome platia nasledujúce pravidlá:

1. Uzol v červeno-čiernom strome je buď červenej alebo čiernej farby.
2. Farba koreňového uzla by mala byť čierna.
3. Priľahlé uzly by nemali byť červené. Inými slovami, môžeme povedať, že červený uzol nemôže mať červené deti, ale čierny uzol môže mať čierne deti.
4. V každej ceste by mal byť rovnaký počet čiernych uzlov; potom sa za červeno-čierny strom môže považovať iba strom.
5. Vonkajšie uzly sú nulové uzly, ktoré sú vždy čiernej farby.

Pravidlo AVL stromu:

Každý uzol by mal mať koeficient rovnováhy buď -1, 0 alebo 1.

Príklad

Na obrázku vyššie musíme skontrolovať, či je strom červeno-čierny strom alebo nie. Aby sme to mohli skontrolovať, najprv musíme skontrolovať, či strom je binárny vyhľadávací strom alebo nie. Ako môžeme vidieť na obrázku vyššie, spĺňa všetky vlastnosti binárneho vyhľadávacieho stromu; ide teda o binárny vyhľadávací strom. Po druhé, musíme overiť, či spĺňa vyššie uvedené pravidlá alebo nie. Vyššie uvedený strom spĺňa všetkých vyššie uvedených päť pravidiel; preto dospel k záveru, že vyššie uvedený strom je červeno-čierny strom.

Na obrázku vyššie musíme skontrolovať, či strom je strom AVL alebo nie. Keďže každý uzol má hodnotu balančného faktora buď ako -1, 0 alebo 1, ide teda o strom AVL.

Ako možno strom považovať za vyvážený strom alebo nie?

V prípade červeno-čierneho stromu, ak sú splnené všetky vyššie uvedené pravidlá, za predpokladu, že strom je binárny vyhľadávací strom, potom sa strom považuje za červeno-čierny strom.

V prípade stromu AVL, ak je faktor rovnováhy -1, 0 alebo 1, potom sa vyššie uvedený strom považuje za strom AVL.

Nástroje používané na vyváženie

Ak strom nie je vyvážený, potom sa na vyváženie stromu v červeno-čiernom strome používajú dva nástroje:

Prefarbenie Rotácia

Ak strom nie je vyvážený, potom sa na vyváženie stromu v strome AVL použije jeden nástroj:

Rotácia

Efektívne pre ktorú operáciu

V prípade červeno-čierneho stromu sú operácie vkladania a vymazávania efektívne. Ak sa strom vyváži prefarbením, operácie vkladania a vymazávania sú v červeno-čiernom strome efektívne.

V prípade stromu AVL je operácia vyhľadávania efektívna, pretože vyžaduje iba jeden nástroj na vyváženie stromu.

Časová zložitosť

V prípade červeno-čierneho stromu je časová zložitosť pre všetky operácie, t.j. vkladanie, mazanie a vyhľadávanie O(logn).

V prípade AVL stromu je časová zložitosť pre všetky operácie, t.j. vkladanie, mazanie a vyhľadávanie O(logn).

Poďme pochopiť rozdiely v tabuľkovej forme.