Rozvětvené stromy jsou samovyvažující nebo samoupravitelné binární vyhledávací stromy. Jinými slovy, můžeme říci, že rozvětvené stromy jsou variantami binárních vyhledávacích stromů. Předpoklad pro rozvětvené stromy, které bychom měli vědět o binárních vyhledávacích stromech.
Jak již víme, časová složitost binárního vyhledávacího stromu v každém případě. Časová složitost binárního vyhledávacího stromu v průměrném případě je O(logn) a časová složitost v nejhorším případě je O(n). V binárním vyhledávacím stromu je hodnota levého podstromu menší než kořenový uzel a hodnota pravého podstromu je větší než kořenový uzel; v takovém případě by byla časová složitost O(logn) . Pokud je binární strom zkosený doleva nebo doprava, pak by časová složitost byla O(n). Chcete-li omezit šikmost, AVL a červeno-černý strom vstoupil do obrazu, majíc O(logn ) časová složitost pro všechny operace ve všech případech. Tuto časovou složitost můžeme také zlepšit provedením praktičtějších implementací, takže nový strom Co je rozvětvený strom?
Rozvětvený strom je samovyvažující strom, ale AVL a Red-Black stromy jsou také samovyvažující stromy. Co dělá rozvětvený strom jedinečným dvěma stromy. Má jednu vlastnost navíc, díky které je jedinečný, a to rozpínání.
Strom zobrazení obsahuje stejné operace jako a Binární vyhledávací strom , tedy Vkládání, mazání a vyhledávání, ale obsahuje ještě jednu operaci, tedy zobrazení. Tak. po všech operacích ve stromu zobrazení následuje zobrazení.
Rozvětvené stromy nejsou striktně vyrovnané stromy, ale jsou to zhruba vyrovnané stromy. Pojďme pochopit vyhledávací operaci v rozkládacím stromu.
Předpokládejme, že chceme prohledat 7 prvků ve stromu, který je zobrazen níže:
Chcete-li prohledat jakýkoli prvek ve stromu zobrazení, nejprve provedeme standardní operaci binárního vyhledávacího stromu. Protože 7 je menší než 10, dostaneme se nalevo od kořenového uzlu. Po provedení vyhledávací operace musíme provést splaying. Zde rozprostření znamená, že operace, kterou provádíme na libovolném prvku, by se po provedení některých přeuspořádání měla stát kořenovým uzlem. Přeskupení stromu bude provedeno pomocí rotací.
Poznámka: Strom zobrazení lze definovat jako samoupravený strom, ve kterém jakákoli operace provedená na prvku změní uspořádání stromu tak, aby se prvek, na kterém byla operace provedena, stal kořenovým uzlem stromu.
Rotace
Existuje šest typů rotací používaných pro splaying:
- Zig rotace (pravá rotace)
- Rotace zag (rotace doleva)
- Zig zag (Cik následovaný cak)
- Zag zig (Zag následovaný cik)
- Zig zig (dvě rotace doprava)
- Cak cak (dvě rotace vlevo)
Faktory potřebné pro výběr typu rotace
Pro výběr typu rotace se používají následující faktory:
- Má uzel, který se snažíme otočit, prarodiče?
- Je uzel levý nebo pravý potomek rodiče?
- Je uzel levé nebo pravé dítě prarodiče?
Pouzdra pro rotace
Případ 1: Nemá-li uzel prarodiče a je-li pravým potomkem rodiče, provedeme rotaci vlevo; jinak se provede pravá rotace.
Případ 2: Pokud má uzel prarodiče, pak na základě následujících scénářů; rotace bude provedena:
Scénář 1: Pokud je uzel právem rodiče a rodič je také právem svého rodiče, pak cik cik pravá rotace se provádí.
Scénář 2: Pokud je uzel vlevo od rodiče, ale rodič je vpravo od svého rodiče, pak cik cak pravá rotace vlevo se provádí.
Scénář 3: Pokud je uzel právem rodiče a rodič je právem svého rodiče, pak cik cik levá rotace se provádí.
Scénář 4: Pokud je uzel vpravo od rodiče, ale rodič je vlevo od svého rodiče, pak cik cak rotace vpravo-vlevo se provádí.
Nyní pochopme výše uvedené rotace s příklady.
Abychom strom uspořádali, musíme provést několik rotací. Následují typy rotací ve stromu zobrazení:
Zig rotace se používají, když je hledaná položka buď kořenový uzel, nebo potomek kořenového uzlu (tj. levý nebo pravý potomek).
Následující případy mohou existovat ve stromu zobrazení při vyhledávání:
Případ 1: Pokud je hledaná položka kořenovým uzlem stromu.
Případ 2: Pokud je hledaná položka potomkem kořenového uzlu, budou existovat tyto dva scénáře:
- Pokud je dítě levým dítětem, byla by provedena rotace doprava, známá jako rotace cik doprava.
- Pokud je dítě pravé dítě, byla by provedena rotace doleva, známá jako rotace zig doleva.
Podívejme se na výše uvedené dva scénáře prostřednictvím příkladu.
Zvažte níže uvedený příklad:
Ve výše uvedeném příkladu musíme prohledat 7 prvků ve stromu. Budeme postupovat podle následujících kroků:
Krok 1: Nejprve porovnáme 7 s kořenovým uzlem. Protože 7 je menší než 10, jedná se o levého potomka kořenového uzlu.
Krok 2: Jakmile je prvek nalezen, provedeme roztažení. Pravá rotace se provede tak, že 7 se stane kořenovým uzlem stromu, jak je znázorněno níže:
Podívejme se na další příklad.
Ve výše uvedeném příkladu musíme prohledat 20 prvků ve stromu. Budeme postupovat podle následujících kroků:
Krok 1: Nejprve porovnáme 20 s kořenovým uzlem. Protože 20 je větší než kořenový uzel, jedná se o pravého potomka kořenového uzlu.
Krok 2: Jakmile je prvek nalezen, provedeme roztažení. Otočení doleva se provede tak, že se prvek 20 stane kořenovým uzlem stromu.
Někdy nastává situace, kdy hledaný předmět má rodiče i prarodiče. V tomto případě musíme provést čtyři rotace pro rozehrání.
Pojďme pochopit tento případ na příkladu.
Předpokládejme, že musíme prohledat 1 prvek ve stromu, který je zobrazen níže:
Krok 1: Nejprve musíme provést standardní operaci vyhledávání BST, abychom prohledali prvek 1. Protože 1 je menší než 10 a 7, bude nalevo od uzlu 7. Proto má prvek 1 rodiče, tj. 7, stejně jako prarodič, tj. 10.
Krok 2: V tomto kroku musíme provést roztažení. Potřebujeme udělat uzel 1 jako kořenový uzel pomocí několika rotací. V tomto případě nemůžeme jednoduše provést cik nebo cak rotaci; musíme zavést cik-cik rotaci.
Aby se uzel 1 stal kořenovým uzelem, musíme provést dvě pravé rotace známé jako cik-cik rotace. Když provedeme pravou rotaci, pak se 10 posune dolů a uzel 7 půjde nahoru, jak je znázorněno na obrázku níže:
Opět provedeme rotaci cik doprava, uzel 7 se posune dolů a uzel 1 se posune nahoru, jak je znázorněno níže:
Jak vidíme na obrázku výše, uzel 1 se stal kořenovým uzlem stromu; proto je vyhledávání dokončeno.
Předpokládejme, že chceme hledat 20 ve stromu níže.
Abychom mohli hledat 20, musíme provést dvě rotace doleva. Níže jsou uvedeny kroky potřebné k prohledání 20 uzlů:
Krok 1: Nejprve provedeme standardní operaci vyhledávání BST. Protože 20 je větší než 10 a 15, bude napravo od uzlu 15.
Krok 2: Druhým krokem je provedení splayingu. V tomto případě by byly provedeny dvě rotace doleva. Při prvním otočení se uzel 10 posune dolů a uzel 15 se posune nahoru, jak je znázorněno níže:
Při druhé rotaci vlevo se uzel 15 posune dolů a uzel 20 se stane kořenovým uzlem stromu, jak je znázorněno níže:
Jak jsme pozorovali, provádějí se dvě rotace doleva; takže je to známé jako rotace cik cik vlevo.
Doposud jsme četli, že jak rodič, tak prarodič jsou buď ve vztahu RR nebo LL. Nyní uvidíme vztah RL nebo LR mezi rodičem a prarodičem.
Pojďme pochopit tento případ na příkladu.
Předpokládejme, že chceme prohledat 13 prvků ve stromu, který je zobrazen níže:
Krok 1: Nejprve provedeme standardní operaci vyhledávání BST. Protože 13 je větší než 10, ale menší než 15, uzel 13 bude levým potomkem uzlu 15.
Krok 2: Protože uzel 13 je nalevo od uzlu 15 a uzel 15 je napravo od uzlu 10, existuje vztah RL. Nejprve provedeme pravou rotaci na uzlu 15 a 15 se bude pohybovat dolů a uzel 13 půjde nahoru, jak je znázorněno níže:
Přesto uzel 13 není kořenový uzel a 13 je napravo od kořenového uzlu, takže provedeme rotaci doleva známou jako rotace zag. Uzel 10 se posune dolů a 13 se stane kořenovým uzlem, jak je znázorněno níže:
Jak můžeme vidět ve výše uvedeném stromu, uzel 13 se stal kořenovým uzlem; proto je vyhledávání dokončeno. V tomto případě jsme nejprve provedli cik rotaci a poté cak rotaci; tak, to je známé jako cik cak rotace.
Pojďme pochopit tento případ na příkladu.
Předpokládejme, že chceme prohledat 9 prvků ve stromu, který je zobrazen níže:
Krok 1: Nejprve provedeme standardní operaci vyhledávání BST. Protože 9 je menší než 10, ale větší než 7, bude to správný potomek uzlu 7.
Krok 2: Protože uzel 9 je napravo od uzlu 7 a uzel 7 je nalevo od uzlu 10, existuje vztah LR. Nejprve provedeme rotaci doleva na uzlu 7. Uzel 7 se bude pohybovat dolů a uzel 9 nahoru, jak je znázorněno níže:
Stále uzel 9 není kořenový uzel a 9 je vlevo od kořenového uzlu, takže provedeme pravou rotaci známou jako cik rotace. Po provedení pravé rotace se uzel 9 stane kořenovým uzlem, jak je znázorněno níže:
Jak můžeme pozorovat ve výše uvedeném stromu, uzel 13 je kořenový uzel; proto je vyhledávání dokončeno. V tomto případě jsme nejprve provedli zag rotaci (otáčení doleva) a poté jsme provedli zig rotaci (pravou rotaci), takže je známá jako rotace zag zig.
Výhody Splay stromu
- Ve stromě zobrazení nepotřebujeme ukládat dodatečné informace. Naproti tomu ve stromech AVL musíme uložit faktor vyvážení každého uzlu, který vyžaduje prostor navíc, a stromy Červeno-černé také vyžadují uložení jednoho bitu informace navíc, který označuje barvu uzlu, buď červenou nebo černou.
- Je to nejrychlejší typ stromu binárního vyhledávání pro různé praktické aplikace. Používá se v Kompilátory Windows NT a GCC .
- Poskytuje lepší výkon, protože často používané uzly se přesunou blíže ke kořenovému uzlu, díky čemuž mohou být prvky rychle přístupné ve stromech zobrazení. Používá se v implementaci mezipaměti, protože nedávno zpřístupněná data se ukládají do mezipaměti, takže pro přístup k datům nemusíme chodit do paměti a trvá to méně času.
Nevýhoda stromu Splay
Hlavní nevýhodou rozvětveného stromu by bylo, že stromy nejsou přísně vyvážené, tj. jsou zhruba vyvážené. Někdy jsou rozvětvené stromy lineární, takže to bude vyžadovat O(n) časovou složitost.
Operace vložení do stromu Splay
V vložení operaci nejprve vložíme prvek do stromu a poté provedeme operaci roztažení na vložený prvek.
15, 10, 17, 7
Krok 1: Nejprve vložíme uzel 15 do stromu. Po vložení musíme provést roztažení. Protože 15 je kořenový uzel, nemusíme provádět rozkládání.
Krok 2: Dalším prvkem je 10. Protože 10 je menší než 15, uzel 10 bude levým potomkem uzlu 15, jak je znázorněno níže:
Nyní vystupujeme rozlévání . Chcete-li vytvořit 10 jako kořenový uzel, provedeme správnou rotaci, jak je znázorněno níže:
Krok 3: Dalším prvkem je 17. Protože 17 je větší než 10 a 15, stane se správným potomkem uzlu 15.
Nyní provedeme splaying. Protože 17 má rodiče i prarodiče, budeme provádět rotace cik-cik.
Na obrázku výše můžeme pozorovat, že 17 se stává kořenovým uzlem stromu; proto je vkládání dokončeno.
Krok 4: Dalším prvkem je 7. Protože 7 je menší než 17, 15 a 10, uzel 7 zůstane potomkem 10.
Teď musíme roztáhnout strom. Protože 7 má rodiče i prarodiče, provedeme dvě rotace doprava, jak je uvedeno níže:
Uzel 7 stále není kořenový uzel, je to levý potomek kořenového uzlu, tj. 17. Musíme tedy provést ještě jednu rotaci doprava, aby se uzel 7 stal kořenovým uzlem, jak je ukázáno níže:
Algoritmus pro operaci vkládání
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)
Ve výše uvedeném algoritmu je T strom a n je uzel, který chceme vložit. Vytvořili jsme proměnnou temp, která obsahuje adresu kořenového uzlu. Spustíme cyklus while, dokud se hodnota temp nestane NULL.
Jakmile je vložení dokončeno, bude provedeno roztažení
Algoritmus pro operaci 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
Ve výše uvedené implementaci je x uzel, na kterém se provádí rotace, zatímco y je levý potomek uzlu x.
Implementace left.rotation(T, x)
left.rotation(T, x) y=x->right x->right = y->left y->left = x return y
Ve výše uvedené implementaci je x uzel, na kterém se provádí rotace, a y je pravým potomkem uzlu x.
Smazání ve stromu Splay
Jak víme, že stromy zobrazení jsou varianty stromu binárního vyhledávání, takže operace odstranění ve stromu zobrazení by byla podobná BST, ale jediný rozdíl je v tom, že po operaci výmazu ve stromech zobrazení následuje operace zobrazení.
Typy smazání:
Ve stromech zobrazení existují dva typy odstranění:
- Roztahování zdola nahoru
- Roztahování shora dolů
Roztahování zdola nahoru
Při zobrazení zdola nahoru nejprve odstraníme prvek ze stromu a poté provedeme zobrazení na odstraněném uzlu.
Pojďme pochopit smazání ve stromu Splay.
Předpokládejme, že chceme odstranit 12, 14 ze stromu zobrazeného níže:
náhodné pořadí sql
- Nejprve jednoduše provedeme standardní operaci odstranění BST pro odstranění 12 prvků. Protože 12 je listový uzel, uzel jednoduše odstraníme ze stromu.
Smazání stále není dokončeno. Potřebujeme rozložit rodiče odstraněného uzlu, tj. 10. Musíme provést Roztáhnout (10) na stromě. Jak můžeme ve výše uvedeném stromu pozorovat, že 10 je napravo od uzlu 7 a uzel 7 je nalevo od uzlu 13. Nejprve tedy provedeme rotaci vlevo na uzlu 7 a poté provedeme rotaci vpravo na uzlu 13, jak je uvedeno níže:
Přesto uzel 10 není kořenový uzel; uzel 10 je levým potomkem kořenového uzlu. Musíme tedy provést správnou rotaci na kořenovém uzlu, tj. 14, abychom z uzlu 10 udělali kořenový uzel, jak je znázorněno níže:
- Nyní musíme odstranit 14 prvků ze stromu, který je zobrazen níže:
Jak víme, nemůžeme jednoduše odstranit vnitřní uzel. Hodnotu uzlu nahradíme buď pomocí řádný předchůdce nebo řádový nástupce . Předpokládejme, že použijeme následníka pořadí, ve kterém nahradíme hodnotu nejnižší hodnotou, která existuje v pravém podstromu. Nejnižší hodnota v pravém podstromu uzlu 14 je 15, takže hodnotu 14 nahradíme 15. Protože se uzel 14 stává listovým uzlem, můžeme jej jednoduše smazat, jak je ukázáno níže:
Smazání však není dokončeno. Potřebujeme provést ještě jednu operaci, tj. roztažení, ve kterém musíme jako kořenový uzel udělat rodiče odstraněného uzlu. Před smazáním byl rodič uzlu 14 kořenový uzel, tj. 10, takže v tomto případě musíme provést jakékoli rozprostření.
Roztahování shora dolů
Při zobrazení shora dolů nejprve provedeme zobrazení, na kterém se má smazání provést, a poté odstraníme uzel ze stromu. Jakmile je prvek odstraněn, provedeme operaci spojení.
Pojďme pochopit rozložení shora dolů na příkladu.
Předpokládejme, že chceme odstranit 16 ze stromu, který je zobrazen níže:
Krok 1: Při rozložení shora dolů nejprve provedeme rozložení na uzel 16. Uzel 16 má rodiče i prarodiče. Uzel 16 je napravo od svého rodiče a nadřazený uzel je také napravo od svého rodiče, takže toto je situace zag zag. V tomto případě nejprve provedeme rotaci doleva na uzlu 13 a poté 14, jak je znázorněno níže:
Uzel 16 stále není kořenový uzel a je pravým potomkem kořenového uzlu, takže potřebujeme provést rotaci doleva na uzlu 12, aby se uzel 16 stal kořenovým uzlem.
Jakmile se uzel 16 stane kořenovým uzlem, odstraníme uzel 16 a získáme dva různé stromy, tj. levý podstrom a pravý podstrom, jak je ukázáno níže:
Jak víme, hodnoty levého podstromu jsou vždy menší než hodnoty pravého podstromu. Kořen levého podstromu je 12 a kořen pravého podstromu je 17. Prvním krokem je nalezení maximálního prvku v levém podstromu. V levém podstromu je maximální prvek 15 a potom musíme provést operaci roztažení na 15.
Jak můžeme pozorovat ve výše uvedeném stromu, prvek 15 má rodiče i prarodiče. Uzel je vpravo od svého rodiče a nadřazený uzel je také vpravo od svého rodiče, takže musíme provést dvě rotace doleva, aby se uzel 15 stal kořenovým uzlem, jak je znázorněno níže:
Po provedení dvou rotací na stromě se uzel 15 stane kořenovým uzlem. Jak vidíme, pravý potomek 15 je NULL, takže připojíme uzel 17 k pravé části 15, jak je znázorněno níže, a tato operace je známá jako připojit úkon.
Poznámka: Pokud prvek není přítomen ve stromu zobrazení, který má být odstraněn, provede se zobrazení. Rozložení by se provedlo na posledním prvku, ke kterému se přistoupilo před dosažením hodnoty NULL.
Algoritmus operace mazání
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
Ve výše uvedeném algoritmu nejprve zkontrolujeme, zda je kořen Null nebo ne; pokud je kořen NULL, znamená to, že strom je prázdný. Pokud strom není prázdný, provedeme operaci zobrazení na prvku, který má být smazán. Jakmile je operace zobrazení dokončena, porovnáme kořenová data s prvkem, který má být odstraněn; pokud se oba nerovnají, znamená to, že prvek není ve stromu přítomen. Pokud jsou stejné, mohou nastat následující případy:
Případ 1 : Levá část kořene je NULL, pravá část kořene se stává kořenovým uzlem.
Případ 2 : Pokud existuje levý i pravý, pak rozložíme maximální prvek v levém podstromu. Po dokončení rozprostření se maximální prvek stane kořenem levého podstromu. Pravý podstrom by se stal pravým potomkem kořene levého podstromu.