Rozvetvené stromy sú samovyvažujúce alebo samonastaviteľné binárne vyhľadávacie stromy. Inými slovami, môžeme povedať, že rozvetvené stromy sú variantmi binárnych vyhľadávacích stromov. Predpokladom pre rozvetvené stromy, ktoré by sme mali vedieť o binárnych vyhľadávacích stromoch.
Ako už vieme, časová zložitosť binárneho vyhľadávacieho stromu v každom prípade. Časová zložitosť binárneho vyhľadávacieho stromu v priemernom prípade je O(logn) a časová zložitosť v najhoršom prípade je O(n). V binárnom vyhľadávacom strome je hodnota ľavého podstromu menšia ako koreňový uzol a hodnota pravého podstromu je väčšia ako koreňový uzol; v takom prípade by bola časová náročnosť O(logn) . Ak je binárny strom skosený doľava alebo doprava, časová zložitosť by bola O(n). Aby sa obmedzila šikmosť, AVL a červeno-čierny strom vstúpil do obrazu, majúc O(logn ) časová zložitosť pre všetky operácie vo všetkých prípadoch. Túto časovú zložitosť môžeme zlepšiť aj praktickejšími implementáciami, takže nový strom Čo je rozvetvený strom?
Rozvetvený strom je samovyvažujúci strom, ale AVL a červeno-čierne stromy sú potom tiež samovyvažujúce stromy. Čo robí rozvetvený strom jedinečnými dvoma stromami. Má jednu vlastnosť navyše, ktorá ho robí jedinečným, a to rozpínavosť.
Strom rozloženia obsahuje rovnaké operácie ako a Binárny vyhľadávací strom , teda Vkladanie, mazanie a vyhľadávanie, ale obsahuje aj jednu operáciu navyše, teda splaying. Takže. po všetkých operáciách v strome zobrazenia nasleduje zobrazenie.
Rozvetvené stromy nie sú striktne vyvážené stromy, ale sú to zhruba vyrovnané stromy. Poďme pochopiť operáciu vyhľadávania v splay-tree.
Predpokladajme, že chceme vyhľadať 7 prvkov v strome, ktorý je zobrazený nižšie:
Ak chcete vyhľadať akýkoľvek prvok v strome zobrazenia, najprv vykonáme štandardnú operáciu binárneho vyhľadávacieho stromu. Keďže 7 je menej ako 10, prídeme naľavo od koreňového uzla. Po vykonaní operácie vyhľadávania musíme vykonať splaying. Tu rozloženie znamená, že operácia, ktorú vykonávame na akomkoľvek prvku, by sa mala stať koreňovým uzlom po vykonaní niektorých preskupení. Preskupenie stromu sa vykoná prostredníctvom rotácií.
Poznámka: Strom rozloženia možno definovať ako samostatne upravený strom, v ktorom akákoľvek operácia vykonaná na prvku zmení usporiadanie stromu tak, aby sa prvok, na ktorom bola operácia vykonaná, stal koreňovým uzlom stromu.
Rotácie
Na hranie sa používa šesť typov rotácií:
- Zig rotácia (pravá rotácia)
- Rotácia zag (otáčanie doľava)
- Cik cak (cik cak, po ktorom nasleduje cak)
- Cik cik (Cak, po ktorom nasleduje cik)
- Cik cik (dve rotácie doprava)
- Cak cak (dve rotácie vľavo)
Faktory potrebné na výber typu rotácie
Nasledujúce faktory sa používajú na výber typu rotácie:
- Má uzol, ktorý sa pokúšame otočiť, prarodiča?
- Je uzol ľavým alebo pravým potomkom rodiča?
- Je uzol ľavé alebo pravé dieťa starého rodiča?
Prípady pre rotácie
Prípad 1: Ak uzol nemá prarodiča a ak je to pravé dieťa rodiča, vykonáme rotáciu doľava; inak sa vykoná pravá rotácia.
Prípad 2: Ak má uzol starého rodiča, potom na základe nasledujúcich scenárov; rotácia sa vykoná:
Scenár 1: Ak je uzol právom rodiča a rodič je právom aj jeho rodiča, potom cik cik pravá rotácia vpravo sa vykonáva.
Scenár 2: Ak je uzol vľavo od rodiča, ale rodič je vpravo od svojho rodiča, potom cik cak pravá rotácia doľava sa vykonáva.
Scenár 3: Ak je uzol právom rodiča a rodič právom svojho rodiča, potom cik cik ľavá rotácia sa vykonáva.
Scenár 4: Ak je uzol napravo od rodiča, ale rodič je naľavo od rodiča, potom cik cak rotácia vpravo-vľavo sa vykonáva.
Teraz pochopme vyššie uvedené rotácie s príkladmi.
Ak chcete zmeniť usporiadanie stromu, musíme vykonať niekoľko rotácií. Nasledujú typy rotácií v strome zobrazenia:
Zig rotácie sa používajú, keď je položka, ktorá sa má hľadať, buď koreňový uzol, alebo potomok koreňového uzla (t. j. ľavý alebo pravý potomok).
Nasledujúce prípady môžu existovať v strome zobrazenia počas vyhľadávania:
Prípad 1: Ak je hľadaná položka koreňovým uzlom stromu.
Prípad 2: Ak je hľadaná položka potomkom koreňového uzla, potom budú existovať dva scenáre:
- Ak je dieťa ľavé dieťa, vykoná sa pravá rotácia, známa ako cik pravá rotácia.
- Ak je dieťa pravé dieťa, vykoná sa rotácia doľava, známa ako rotácia cik doľava.
Pozrime sa na vyššie uvedené dva scenáre prostredníctvom príkladu.
Zvážte nasledujúci príklad:
Vo vyššie uvedenom príklade musíme vyhľadať 7 prvkov v strome. Budeme postupovať podľa nasledujúcich krokov:
Krok 1: Najprv porovnáme 7 s koreňovým uzlom. Keďže 7 je menšie ako 10, ide o ľavého potomka koreňového uzla.
Krok 2: Po nájdení prvku vykonáme rozloženie. Pravá rotácia sa vykoná tak, že 7 sa stane koreňovým uzlom stromu, ako je znázornené nižšie:
Uvažujme o ďalšom príklade.
Vo vyššie uvedenom príklade musíme vyhľadať 20 prvkov v strome. Budeme postupovať podľa nasledujúcich krokov:
Krok 1: Najprv porovnáme 20 s koreňovým uzlom. Keďže 20 je väčšie ako koreňový uzol, je to pravý potomok koreňového uzla.
Krok 2: Po nájdení prvku vykonáme rozloženie. Ľavá rotácia sa vykoná tak, že 20 element sa stane koreňovým uzlom stromu.
Niekedy nastane situácia, keď hľadaný predmet má rodiča aj starého rodiča. V tomto prípade musíme vykonať štyri rotácie na rozohratie.
Poďme pochopiť tento prípad na príklade.
Predpokladajme, že musíme vyhľadať 1 prvok v strome, ktorý je zobrazený nižšie:
Krok 1: Najprv musíme vykonať štandardnú operáciu vyhľadávania BST, aby sme vyhľadali prvok 1. Keďže 1 je menšia ako 10 a 7, bude naľavo od uzla 7. Preto prvok 1 má rodiča, t.j. 7, ako aj starého rodiča, t.j. 10.
Krok 2: V tomto kroku musíme vykonať splaying. Musíme urobiť uzol 1 ako koreňový uzol pomocou niekoľkých rotácií. V tomto prípade nemôžeme jednoducho vykonať cik alebo cak rotáciu; musíme zaviesť cik-cik rotáciu.
Aby sa uzol 1 stal koreňovým uzlom, musíme vykonať dve pravé rotácie známe ako cik-cik rotácie. Keď vykonáme správnu rotáciu, potom sa 10 posunie nadol a uzol 7 sa posunie nahor, ako je znázornené na obrázku nižšie:
Opäť vykonáme rotáciu cik doprava, uzol 7 sa posunie nadol a uzol 1 sa posunie nahor, ako je znázornené nižšie:
Ako vidíme na obrázku vyššie, uzol 1 sa stal koreňovým uzlom stromu; preto je vyhľadávanie ukončené.
Predpokladajme, že chceme hľadať 20 v nižšie uvedenom strome.
Aby sme našli 20, musíme vykonať dve rotácie doľava. Nasledujú kroky potrebné na vyhľadávanie 20 uzlov:
Krok 1: Najprv vykonáme štandardnú operáciu vyhľadávania BST. Keďže 20 je väčšie ako 10 a 15, bude napravo od uzla 15.
Krok 2: Druhým krokom je vykonanie splayingu. V tomto prípade by sa vykonali dve rotácie doľava. Pri prvom otočení sa uzol 10 posunie nadol a uzol 15 sa bude pohybovať nahor, ako je znázornené nižšie:
Pri druhej rotácii vľavo sa uzol 15 posunie nadol a uzol 20 sa stane koreňovým uzlom stromu, ako je znázornené nižšie:
Ako sme pozorovali, vykonajú sa dve rotácie doľava; takže je to známe ako rotácia cik-cik doľava.
Doteraz sme čítali, že rodičia aj starý rodičia sú vo vzťahu RR alebo LL. Teraz uvidíme vzťah RL alebo LR medzi rodičom a starým rodičom.
Poďme pochopiť tento prípad na príklade.
Predpokladajme, že chceme vyhľadať 13 prvkov v strome, ktorý je zobrazený nižšie:
Krok 1: Najprv vykonáme štandardnú operáciu vyhľadávania BST. Keďže 13 je väčšie ako 10, ale menšie ako 15, uzol 13 bude ľavým potomkom uzla 15.
Krok 2: Pretože uzol 13 je naľavo od uzla 15 a uzol 15 je napravo od uzla 10, existuje vzťah RL. Najprv vykonáme pravú rotáciu na uzle 15 a 15 sa bude pohybovať nadol a uzol 13 pôjde hore, ako je znázornené nižšie:
Napriek tomu uzol 13 nie je koreňový uzol a 13 je napravo od koreňového uzla, takže vykonáme rotáciu doľava známu ako rotácia zag. Uzol 10 sa posunie nadol a 13 sa stane koreňovým uzlom, ako je znázornené nižšie:
Ako môžeme vidieť vo vyššie uvedenom strome, uzol 13 sa stal koreňovým uzlom; preto je vyhľadávanie ukončené. V tomto prípade sme najprv vykonali cik rotáciu a potom cik rotáciu; takže je to známe ako cik cak rotácia.
Poďme pochopiť tento prípad na príklade.
Predpokladajme, že chceme vyhľadať 9 prvkov v strome, ktorý je zobrazený nižšie:
Krok 1: Najprv vykonáme štandardnú operáciu vyhľadávania BST. Keďže 9 je menšie ako 10, ale väčšie ako 7, bude to správne dieťa uzla 7.
Krok 2: Pretože uzol 9 je napravo od uzla 7 a uzol 7 je naľavo od uzla 10, existuje vzťah LR. Najprv vykonáme rotáciu doľava na uzle 7. Uzol 7 sa bude pohybovať nadol a uzol 9 sa bude pohybovať nahor, ako je znázornené nižšie:
Napriek tomu uzol 9 nie je koreňový uzol a 9 je naľavo od koreňového uzla, takže vykonáme pravú rotáciu známu ako cik rotácia. Po vykonaní pravej rotácie sa uzol 9 stane koreňovým uzlom, ako je znázornené nižšie:
Ako môžeme vidieť vo vyššie uvedenom strome, uzol 13 je koreňový uzol; preto je vyhľadávanie ukončené. V tomto prípade sme najprv vykonali rotáciu zag (otočenie doľava) a potom sa vykoná rotácia zag (rotácia doprava), takže je známa ako rotácia zag zig.
Výhody Splay stromu
- V strome zobrazenia nepotrebujeme ukladať ďalšie informácie. Na rozdiel od toho v stromoch AVL musíme uložiť faktor vyváženia každého uzla, ktorý vyžaduje priestor navyše, a stromy Červeno-čierne tiež vyžadujú uloženie jedného bitu informácií navyše, ktorý označuje farbu uzla, buď červenú alebo čiernu.
- Je to najrýchlejší typ stromu binárneho vyhľadávania pre rôzne praktické aplikácie. Používa sa v Kompilátory Windows NT a GCC .
- Poskytuje lepší výkon, pretože často používané uzly sa presunú bližšie ku koreňovému uzlu, vďaka čomu môžu byť prvky rýchlo prístupné v roztiahnutých stromoch. Používa sa v implementácii vyrovnávacej pamäte, pretože údaje, ku ktorým sa nedávno pristupovalo, sa ukladajú do vyrovnávacej pamäte, takže na prístup k údajom nemusíme ísť do pamäte a trvá to menej času.
Nevýhoda stromu Splay
Hlavnou nevýhodou rozvetveného stromu by bolo, že stromy nie sú striktne vyvážené, t.j. sú zhruba vyvážené. Niekedy sú rastrové stromy lineárne, takže to bude trvať O(n) časovú zložitosť.
Operácia vloženia do stromu Splay
V vkladanie operáciu najskôr vložíme prvok do stromu a potom vykonáme operáciu rozloženia na vloženom prvku.
15, 10, 17, 7
Krok 1: Najprv vložíme uzol 15 do stromu. Po vložení musíme vykonať roztiahnutie. Keďže 15 je koreňový uzol, nemusíme vykonávať rozťahovanie.
Krok 2: Ďalším prvkom je 10. Keďže 10 je menšie ako 15, uzol 10 bude ľavým potomkom uzla 15, ako je uvedené nižšie:
Teraz vystupujeme rozstrekovanie . Ak chcete vytvoriť 10 ako koreňový uzol, vykonáme správnu rotáciu, ako je znázornené nižšie:
Krok 3: Ďalším prvkom je 17. Keďže 17 je väčšie ako 10 a 15, stane sa správnym potomkom uzla 15.
Teraz vykonáme splaying. Keďže 17 má rodiča aj starého rodiča, budeme vykonávať cik-cik rotácie.
Na obrázku vyššie môžeme pozorovať, že 17 sa stáva koreňovým uzlom stromu; preto je vkladanie dokončené.
Krok 4: Ďalším prvkom je 7. Keďže 7 je menšie ako 17, 15 a 10, uzol 7 zostane potomkom 10.
Teraz musíme roztiahnuť strom. Keďže 7 má rodiča aj starého rodiča, vykonáme dve rotácie doprava, ako je uvedené nižšie:
Napriek tomu uzol 7 nie je koreňový uzol, je to ľavý potomok koreňového uzla, t.
Algoritmus pre operáciu vkladania
Insert(T, n) temp= T_root y=NULL while(temp!=NULL) y=temp if(n->data data) temp=temp->left else temp=temp->right n.parent= y if(y==NULL) T_root = n else if (n->data data) y->left = n else y->right = n Splay(T, n)
Vo vyššie uvedenom algoritme je T strom a n je uzol, ktorý chceme vložiť. Vytvorili sme dočasnú premennú, ktorá obsahuje adresu koreňového uzla. Spustíme cyklus while, kým sa hodnota temp nestane NULL.
Po dokončení vkladania sa vykoná roztiahnutie
Algoritmus pre operáciu Splaying
Splay(T, N) while(n->parent !=Null) if(n->parent==T->root) if(n==n->parent->left) right_rotation(T, n->parent) else left_rotation(T, n->parent) else p= n->parent g = p->parent if(n=n->parent->left && p=p->parent->left) right.rotation(T, g), right.rotation(T, p) else if(n=n->parent->right && p=p->parent->right) left.rotation(T, g), left.rotation(T, p) else if(n=n->parent->left && p=p->parent->right) right.rotation(T, p), left.rotation(T, g) else left.rotation(T, p), right.rotation(T, g) Implementation of right.rotation(T, x) right.rotation(T, x) y= x->left x->left=y->right y->right=x return y
Vo vyššie uvedenej implementácii je x uzol, na ktorom sa vykonáva rotácia, zatiaľ čo y je ľavým potomkom uzla x.
Implementácia left.rotation(T, x)
left.rotation(T, x) y=x->right x->right = y->left y->left = x return y
Vo vyššie uvedenej implementácii je x uzol, na ktorom sa vykonáva rotácia a y je pravým potomkom uzla x.
Odstránenie v strome Splay
Ako vieme, že stromy rozloženia sú varianty stromu binárneho vyhľadávania, takže operácia vymazania v strome zobrazenia by bola podobná ako BST, ale jediný rozdiel je v tom, že po operácii vymazania v stromoch rozloženia nasleduje operácia rozloženia.
Typy vymazaní:
V stromoch rozloženia existujú dva typy odstránenia:
- Rozťahovanie zdola nahor
- Roztiahnutie zhora nadol
Rozťahovanie zdola nahor
Pri zobrazení zdola nahor najprv vymažeme prvok zo stromu a potom rozloženie vykonáme na vymazanom uzle.
Poďme pochopiť vymazanie v strome Splay.
Predpokladajme, že chceme odstrániť 12, 14 zo stromu zobrazeného nižšie:
cm na stopy a palce
- Najprv jednoducho vykonáme štandardnú operáciu vymazania BST, aby sme odstránili 12 prvkov. Keďže 12 je listový uzol, tak uzol jednoducho vymažeme zo stromu.
Výmaz stále nie je dokončený. Potrebujeme rozložiť rodiča odstráneného uzla, t.j. 10. Musíme vykonať Roztiahnuť (10) na strome. Ako môžeme vidieť vo vyššie uvedenom strome, 10 je napravo od uzla 7 a uzol 7 je naľavo od uzla 13. Najprv teda vykonáme rotáciu doľava na uzle 7 a potom vykonáme rotáciu doprava na uzle 13, ako je uvedené nižšie:
Napriek tomu uzol 10 nie je koreňový uzol; uzol 10 je ľavým potomkom koreňového uzla. Takže musíme vykonať správnu rotáciu na koreňovom uzle, t. j. 14, aby sme urobili z uzla 10 koreňový uzol, ako je znázornené nižšie:
- Teraz musíme odstrániť 14 prvkov zo stromu, ktorý je zobrazený nižšie:
Ako vieme, nemôžeme jednoducho odstrániť interný uzol. Hodnotu uzla nahradíme buď pomocou poradový predchodca alebo rádový nástupca . Predpokladajme, že použijeme následníka poradia, v ktorom nahradíme hodnotu najnižšou hodnotou, ktorá existuje v pravom podstrome. Najnižšia hodnota v pravom podstrome uzla 14 je 15, takže hodnotu 14 nahradíme 15. Keďže uzol 14 sa stáva listovým uzlom, môžeme ho jednoducho odstrániť, ako je uvedené nižšie:
Odstránenie však nie je dokončené. Musíme vykonať ešte jednu operáciu, t.j. rozloženie, v ktorom musíme urobiť rodiča odstráneného uzla ako koreňový uzol. Pred odstránením bol rodič uzla 14 koreňovým uzlom, t. j. 10, takže v tomto prípade musíme vykonať akékoľvek rozloženie.
Roztiahnutie zhora nadol
Pri zobrazení zhora nadol vykonáme najskôr zobrazenie, na ktorom sa má vymazanie vykonať a potom uzol vymažeme zo stromu. Po odstránení prvku vykonáme operáciu spojenia.
Poďme pochopiť rozloženie zhora nadol prostredníctvom príkladu.
Predpokladajme, že chceme odstrániť 16 zo stromu, ktorý je zobrazený nižšie:
Krok 1: Pri rozložení zhora nadol najprv vykonáme rozloženie na uzle 16. Uzol 16 má rodiča aj starého rodiča. Uzol 16 je napravo od svojho rodiča a nadradený uzol je tiež napravo od svojho rodiča, takže toto je situácia zag zag. V tomto prípade najprv vykonáme rotáciu doľava na uzle 13 a potom 14, ako je znázornené nižšie:
Uzol 16 stále nie je koreňovým uzlom a je pravým potomkom koreňového uzla, takže musíme vykonať rotáciu doľava na uzle 12, aby sa uzol 16 stal koreňovým uzlom.
Keď sa uzol 16 stane koreňovým uzlom, vymažeme uzol 16 a získame dva rôzne stromy, t. j. ľavý podstrom a pravý podstrom, ako je znázornené nižšie:
Ako vieme, hodnoty ľavého podstromu sú vždy menšie ako hodnoty pravého podstromu. Koreň ľavého podstromu je 12 a koreň pravého podstromu je 17. Prvým krokom je nájsť maximum prvku v ľavom podstrome. V ľavom podstrome je maximálny prvok 15 a potom musíme vykonať operáciu rozloženia na 15.
Ako môžeme vidieť vo vyššie uvedenom strome, prvok 15 má rodiča aj starého rodiča. Uzol je napravo od svojho rodiča a nadradený uzol je tiež napravo od svojho rodiča, takže musíme vykonať dve rotácie doľava, aby sa uzol 15 stal koreňovým uzlom, ako je znázornené nižšie:
Po vykonaní dvoch rotácií na strome sa uzol 15 stane koreňovým uzlom. Ako môžeme vidieť, pravý potomok 15 je NULL, takže pripojíme uzol 17 k pravej časti 15, ako je znázornené nižšie, a táto operácia je známa ako pripojiť sa prevádzka.
Poznámka: Ak sa prvok nenachádza v strome zobrazenia, ktorý sa má vymazať, vykoná sa zobrazenie. Rozloženie by sa vykonalo na poslednom prvku, ku ktorému sa pristupovalo pred dosiahnutím hodnoty NULL.
Algoritmus operácie Delete
If(root==NULL) return NULL Splay(root, data) If data!= root->data Element is not present If root->left==NULL root=root->right else temp=root Splay(root->left, data) root1->right=root->right free(temp) return root
Vo vyššie uvedenom algoritme najprv skontrolujeme, či je koreň Null alebo nie; ak je koreň NULL, znamená to, že strom je prázdny. Ak strom nie je prázdny, vykonáme operáciu zobrazenia na prvku, ktorý sa má vymazať. Po dokončení operácie rozloženia porovnáme koreňové údaje s prvkom, ktorý sa má odstrániť; ak nie sú obe rovnaké, znamená to, že prvok sa v strome nenachádza. Ak sú rovnaké, môžu nastať tieto prípady:
Prípad 1 : Ľavá časť koreňa je NULL, pravá časť koreňa sa stáva koreňovým uzlom.
Prípad 2 : Ak existuje ľavý aj pravý, potom rozložíme maximálny prvok v ľavom podstrome. Po dokončení rozloženia sa maximálny prvok stane koreňom ľavého podstromu. Pravý podstrom by sa stal pravým potomkom koreňa ľavého podstromu.