V následujícím tutoriálu se seznámíme s datovou strukturou B Tree a zvážíme její vizualizaci.
Takže, pojďme začít.
Co je to strom B?
The B strom je speciální typ vícecestného vyhledávacího stromu , běžně známý jako M-cesta strom, který se sám vyrovnává. Díky své vyvážené struktuře se tyto stromy běžně používají k provozu a správě obrovských databází a zjednodušují vyhledávání. Ve stromu B může mít každý uzel nejvýše n podřízených uzlů. B Tree je příkladem víceúrovňového indexování v systému správy databází (DBMS). Listový a vnitřní uzly budou mít oba záznamy. Strom B je známý jako Balanced Stored Tree, protože všechny uzly listů jsou na stejné úrovni.
Následující diagram je příkladem B stromu:
Obrázek 1. A B Strom s objednávkou 3
Pochopení pravidel stromu B
Níže jsou uvedeny důležité vlastnosti stromu B:
- Všechny uzly listů jsou na stejné úrovni.
- Datová struktura stromu B je definována pojmem minimální stupeň 'd'. Hodnota 'd' závisí na velikosti bloku disku.
- Každý uzel, kromě kořene, musí obsahovat alespoň d-1 klíčů. Kořenový uzel může obsahovat minimálně 1 klíč.
- Všechny uzly (včetně kořenového uzlu) se mohou skládat nejvýše z (2d-1) klíče.
- Počet potomků uzlu je roven přidání počtu klíčů v něm přítomných a .
- Všechny klíče uzlu jsou seřazeny ve vzestupném pořadí. Dítě mezi dvěma klávesami, k1 a k2, se skládá ze všech kláves v rozsahu mezi k1 a k2.
- Na rozdíl od stromu binárního vyhledávání datová struktura stromu B roste a zmenšuje se od kořene. Zatímco binární vyhledávací strom roste směrem dolů a zmenšuje se směrem dolů.
- Podobně jako u jiných samovyvážených binárních vyhledávacích stromů je časová složitost datové struktury B stromu pro operace, jako je vyhledávání, vkládání a mazání, O(log?n) .
- Vložení uzlu do stromu B se děje pouze v listovém uzlu.
Podívejme se na následující příklad stromu B minimálního řádu 5.
Obrázek 2 A B Strom řádu 5
Poznámka: Hodnota minimální objednávky je mnohem vyšší než 5 v praktickém stromě B.
Ve výše uvedeném diagramu můžeme pozorovat, že všechny listové uzly jsou na stejné úrovni a všechny nelistové uzly nemají žádný prázdný podstrom a sestávají z klíčů o jeden méně, než je počet jejich potomků.
Nastavená formulace B stromu pravidla:
Každý B strom závisí na kladném konstantním celém čísle známém jako MINIMÁLNÍ , který se používá k určení počtu datových prvků, které mohou být drženy v jednom uzlu.
Pravidlo 1: Kořen může mít pouze jeden datový prvek (nebo dokonce žádné datové prvky, pokud také nejsou žádné potomky); každý druhý uzel má alespoň MINIMÁLNÍ datové prvky.
Pravidlo 2: Maximální počet datových prvků uložených v uzlu je dvojnásobek hodnoty MINIMÁLNÍ .
Pravidlo 3: Datové prvky každého uzlu stromu B jsou uloženy v částečně vyplněném poli, seřazené od nejmenšího datového prvku (na indexu 0 ) na největší datový prvek (na konečné využité pozici pole).
Pravidlo 4: Celkový počet podstromů pod nelistovým uzlem je vždy o jeden větší než počet datových prvků v tomto uzlu.
- podstrom 0, podstrom 1,...
Pravidlo 5: S ohledem na jakýkoli nelistový uzel:
- Datový prvek na indexu je větší než všechny datové prvky v čísle podstromu i uzlu a
- Datový prvek na indexu je menší než počet všech datových prvků v podstromu i+1 uzlu.
Pravidlo 6: Každý list ve stromu B má stejnou hloubku. Zajišťuje tedy, že strom B zabrání problému nevyváženého stromu.
Operace na datové struktuře B Tree
Aby se zajistilo, že žádná z vlastností datové struktury stromu B nebude během operací narušena, může být strom B rozdělen nebo spojen. Níže jsou uvedeny některé operace, které můžeme provádět se stromem B:
- Hledání datového prvku ve stromu B
- Vložení datového prvku do B stromu
- Odstranění datového prvku ve stromu B
Vyhledávací operace na B stromu
Hledání prvku ve stromu B je podobné jako v binárním stromu vyhledávání. Ale místo dvoucestného rozhodování (vlevo nebo vpravo) jako binární vyhledávací strom, B strom dělá m-cestné rozhodnutí v každém uzlu, kde m je počet potomků uzlu.
Postup vyhledávání datového prvku ve stromu B:
hlavní metoda java
Krok 1: Vyhledávání začíná od kořenového uzlu. Porovnejte vyhledávací prvek k s kořenem.
Krok 1.1: Pokud se kořenový uzel skládá z prvku k, bude vyhledávání dokončeno.
Krok 1.2: Pokud je prvek k menší než první hodnota v kořenu, přesuneme se k potomkovi nejvíce vlevo a potomka vyhledáme rekurzivně.
Krok 1.3.1: Pokud má kořen pouze dva potomky, přesuneme se k potomkovi nejvíce vpravo a rekurzivně prohledáme dceřiné uzly.
Krok 1.3.2: Pokud má root více než dva klíče, prohledáme zbytek.
Krok 2: Pokud prvek k není nalezen po procházení celého stromu, pak prvek hledání není ve stromu B přítomen.
Pojďme si výše uvedené kroky představit pomocí příkladu. Předpokládejme, že jsme chtěli hledat klíč k=34 v následujícím B stromu:
Obrázek 3.1. Daný strom B
- Nejprve zkontrolujeme, zda je klíč k = 34 je v kořenovém uzlu. Protože klíč není v kořenu, přejdeme k jeho podřízeným uzlům. Můžeme také pozorovat, že kořenový uzel má dva potomky; proto porovnáme požadovanou hodnotu mezi dvěma klíči.
Obrázek 3.2. Klíč k není v kořenovém adresáři přítomen - Nyní, když si můžeme všimnout, že klíč k je větší než kořenový uzel, tj. 30, budeme pokračovat se správným potomkem kořene.
Obrázek 3.3. Klávesa k > 30, přesun na dítě vpravo - Nyní porovnáme klíč k s hodnotami přítomnými na uzlu, tj. 40 a 50, v tomto pořadí. Protože klíč k je menší než levý klíč, tj. 40, přesuneme se k levému potomkovi uzlu.
Obrázek 3.4. Klíč k<40, move to left child< li> - Protože hodnota v levém potomku 40 je 34, což je požadovaná hodnota, můžeme dojít k závěru, že klíč je nalezen a vyhledávací operace je dokončena.
Obrázek 3.4. Klíč k = 34, levé dítě 40
Porovnávali jsme klíč se čtyřmi různými hodnotami ve výše uvedeném příkladu, dokud jsme jej nenašli. Časová složitost požadovaná pro vyhledávací operaci ve stromu B je tedy O(log?n) .
Operace vkládání na B strom
Při vkládání datového prvku do B stromu musíme nejprve zkontrolovat, zda je tento prvek již ve stromu přítomen nebo ne. Pokud je datový prvek nalezen ve stromu B, operace vložení neproběhne. Pokud tomu tak není, pokračujeme ve vkládání dále. Při vkládání prvku do listového uzlu je třeba dbát na dva scénáře:
Kroky pro vložení datového prvku do B stromu:
Krok 1: Začneme výpočtem maximálního počtu klíčů v uzlu na základě pořadí B stromu.
Krok 2: Pokud je strom prázdný, je přidělen kořenový uzel a vložíme klíč, který funguje jako kořenový uzel.
Krok 3: Nyní prohledáme příslušný uzel pro vložení.
Krok 4: Pokud je uzel plný:
Krok 4.1: Datové prvky budeme vkládat vzestupně.
Krok 4.2: Pokud jsou datové prvky větší než maximální počet klíčů, rozdělíme celý uzel na mediánu.
Krok 4.3: Zatlačíme střední klávesu nahoru a rozdělíme levou a pravou klávesu jako levé a pravé dítě.
Krok 5: Pokud uzel není plný, vložíme uzel vzestupně.
Pojďme si výše uvedené kroky představit pomocí příkladu. Předpokládejme, že jsme povinni vytvořit B strom řádu 4. Datové prvky, které je třeba vložit do B stromu, jsou 5,3,21,11,1,16,8,13,4 a 9 .
- Protože m se rovná 3, maximální počet klíčů pro uzel = m-1 = 3-1 = 2 .
- Začneme vkládáním 5 v prázdném stromě.
Obrázek 4.1. Vkládání 5 - Nyní vložíme 3 do stromu. Protože 3 je menší než 5, vložíme 3 vlevo od 5 do stejného uzlu.
Obrázek 4.2. Vkládání 3 - Nyní do stromu vložíme 21, a protože 21 je větší než 5, vloží se napravo od 5 ve stejném uzlu. Protože však víme, že maximální počet klíčů v uzlu je 2, bude jeden z těchto klíčů přesunut do uzlu výše, aby byl rozdělen. Tedy 5, prostřední datový prvek, se posune nahoru a 3 a 21 se stanou jeho levým a pravým uzlem.
Obrázek 4.3. Vkládání 21 - Nyní je čas vložit další datový prvek, tj. 11, který je větší než 5, ale menší než 21. Proto bude 11 vložen jako klíč nalevo od uzlu sestávajícího z 21 jako klíče.
Obrázek 4.4. Vkládání 11 - Podobně vložíme do stromu další datový prvek 1 a jak můžeme pozorovat, 1 je menší než 3; proto bude vložen jako klíč nalevo od uzlu sestávajícího z 3 jako klíč.
Obrázek 4.5. Vkládání 1 - Nyní do stromu vložíme datový prvek 16, který je větší než 11, ale menší než 21. Počet klíčů v tomto uzlu však překračuje maximální počet klíčů. Proto se uzel rozdělí a přesune prostřední klíč do kořenového adresáře. Proto bude 16 vložena napravo od 5, čímž se 11 a 21 rozdělí na dva samostatné uzly.
Obrázek 4.6. Vkládání 16 - Datový prvek 8 bude vložen jako klíč vlevo od 11.
Obrázek 4.7. Vkládání 8 - Do stromu vložíme 13, což je menší než 16 a větší než 11. Datový prvek 13 by tedy měl být vložen napravo od uzlu skládajícího se z 8 a 11. Protože však maximální počet klíčů ve stromu může být pouze 2, dojde k rozdělení, přičemž se střední datový prvek 11 přesune do výše uvedeného uzlu a 8 a 13 do dvou samostatných uzlů. Nyní se výše uvedený uzel bude skládat z 5, 11 a 16, což opět překračuje maximální počet klíčů. Proto dojde k dalšímu rozdělení, čímž se datový prvek 11 stane kořenovým uzlem s 5 a 16 jako jeho potomky.
Obrázek 4.8. Vkládání 13 - Protože datový prvek 4 je menší než 5, ale větší než 3, bude vložen napravo od uzlu sestávajícího z 1 a 3, což opět překročí maximální počet klíčů v uzlu. Proto znovu dojde k úniku a přesune 3 do horního uzlu vedle 5.
Obrázek 4.9. Vkládání 4 - Nakonec bude datový prvek 9, který je větší než 8, ale menší než 11, vložen napravo od uzlu sestávajícího z 8 jako klíč.
Obrázek 4.10. Vkládání 9
Ve výše uvedeném příkladu jsme provedli různá srovnání. První hodnota byla přímo vložena do stromu; poté musela být každá hodnota porovnána s uzly dostupnými v tomto stromu. Časová složitost operace vkládání do stromu B závisí na počtu uzlů a .
Odstranění operace na B stromu
Odstranění datového prvku ve stromu B obsahuje tři primární události:
- Hledání uzlu, kde existuje klíč, který má být odstraněn,
- Smazání klíče a
- V případě potřeby vyvažování stromu.
Při odstraňování prvku ze stromu může nastat stav známý jako podtečení. Podtečení nastane, když uzel obsahuje méně než minimální počet klíčů; mělo by to držet.
Před vizualizací operace odstranění/odstranění je třeba porozumět následujícím pojmům:
Následují tři prominentní případy operace odstranění ve stromu B:
Případ 1: Odstranění/odstranění klíče leží v uzlu List - Tento případ se dále dělí na dva různé případy:
1. Smazání/odstranění klíče neporušuje vlastnost minimálního počtu klíčů, které by měl uzel držet.
Ukažme si tento případ na příkladu, kdy vymažeme klíč 32 z následujícího B stromu.
Obrázek 4.1: Odstranění klíče listového uzlu (32) ze stromu B
Jak můžeme pozorovat, odstranění 32 z tohoto stromu neporušuje výše uvedenou vlastnost.
2. Smazání/odstranění klíče porušuje vlastnost minimálního počtu klíčů, které by měl uzel držet. V tomto případě si musíme vypůjčit klíč od jeho nejbližšího sourozeneckého uzlu v pořadí zleva doprava.
Nejprve navštívíme blízkého sourozence Levého. Pokud má uzel Levý sourozenec více než minimální počet klíčů, vypůjčí si klíč z tohoto uzlu.
V opačném případě zkontrolujeme půjčení od nejbližšího uzlu Pravého sourozence.
Pojďme si nyní tento případ představit pomocí příkladu, kdy odstraníme 31 z výše uvedeného B stromu. Klíč si v tomto případě vypůjčíme od levého sourozeneckého uzlu.
Obrázek 4.2: Odstranění klíče listového uzlu (31) ze stromu B
Pokud oba blízké sourozenecké uzly již obsahují minimální počet klíčů, sloučíme uzel buď s levým sourozeneckým uzlem, nebo s pravým. Tento proces slučování se provádí prostřednictvím nadřazeného uzlu.
Pojďme znovu vizualizovat odstraněním klíče 30 z výše uvedeného B stromu.
Obrázek 4.3: Odstranění klíče listového uzlu (30) ze stromu B
Případ 2: Odstranění/odstranění klíče leží v uzlu mimo list - Tento případ se dále dělí na různé případy:
1. Nelistový/vnitřní uzel, který je odstraněn, je nahrazen předchůdcem v pořadí, pokud má levý podřízený uzel více než minimální počet klíčů.
Pojďme si tento případ představit na příkladu, kdy vymažeme klíč 33 ze stromu B.
Obrázek 4.4: Odstranění klíče listového uzlu (33) ze stromu B
2. Nelistový/vnitřní uzel, který je odstraněn, je nahrazen následníkem v pořadí, pokud má pravý podřízený uzel více než minimální počet klíčů.
Pokud má kterýkoli z potomků minimální počet klíčů, sloučíme Levý a Pravý dceřiný uzel.
Pojďme si tento případ představit odstraněním klíče 30 ze stromu B.
Obrázek 4.5: Odstranění klíče listového uzlu (30) ze stromu B
Pokud má nadřazený uzel po sloučení méně než minimální počet klíčů, lze hledat sourozence, jako v Případ 1 .
Případ 3: V následujícím případě se výška stromu zmenší. Pokud cílový klíč leží v interním uzlu a odstranění klíče vede k menšímu počtu klíčů v uzlu (což je méně, než je nutné minimum), hledejte předchůdce v pořadí a následníka v pořadí. Pokud mají obě děti minimální počet klíčů, k zapůjčení nemůže dojít. Tohle vede k Případ 2(3) , tj. sloučení podřízených uzlů.
Budeme opět hledat sourozence k zapůjčení klíče. Pokud však i sourozenec obsahuje minimální počet klíčů, pak sloučíme uzel se sourozencem spolu s nadřazeným uzlem a uspořádáme podřízené uzly podle požadavků (vzestupně).
města v Austrálii
Vizualizujme si tento případ pomocí příkladu, kdy vymažeme datový prvek 10 z daného B stromu.
Obrázek 4.6: Odstranění klíče listového uzlu (10) ze stromu B
Časová složitost ve výše uvedených příkladech se liší v závislosti na místě, odkud je potřeba klíč odstranit. Časová složitost operace mazání ve stromu B je tedy O(log?n) .
Závěr
V tomto tutoriálu jsme se dozvěděli o stromu B a vizualizovali jsme jeho různé operace na různých příkladech. Také jsme pochopili některé základní vlastnosti a pravidla B stromu.