V nasledujúcom návode sa dozvieme o dátovej štruktúre B Tree a zvážime jej vizualizáciu.
Takže, začnime.
Čo je to strom B?
The B strom je a špeciálny typ viacsmerného vyhľadávacieho stromu , všeobecne známy ako M-cesta strom, ktorý sa sám vyrovnáva. Vďaka svojej vyváženej štruktúre sa tieto stromy bežne používajú na prevádzku a správu obrovských databáz a na zjednodušenie vyhľadávania. V strome B môže mať každý uzol najviac n podriadených uzlov. B Tree je príkladom viacúrovňového indexovania v systéme správy databáz (DBMS). Listové aj vnútorné uzly budú mať referencie na záznamy. Strom B je známy ako Balanced Stored Tree, pretože všetky uzly listov sú na rovnakej úrovni.
Nasledujúci diagram je príkladom B stromu:
Postava 1. A B Strom s poradím 3
Pochopenie pravidiel stromu B
Nasledujúce sú dôležité vlastnosti stromu B:
- Všetky uzly listov sú na rovnakej úrovni.
- Štruktúra údajov stromu B je definovaná pojmom minimálny stupeň „d“. Hodnota 'd' závisí od veľkosti bloku disku.
- Každý uzol, okrem koreňa, musí pozostávať z aspoň d-1 kľúčov. Koreňový uzol môže pozostávať minimálne z 1 kľúča.
- Všetky uzly (vrátane koreňového uzla) môžu pozostávať najviac z (2d-1) kľúče.
- Počet detí uzla sa rovná pridanie počtu kľúčov v ňom prítomných a .
- Všetky kľúče uzla sú zoradené vo vzostupnom poradí. Dieťa medzi dvoma kľúčmi, k1 a k2, pozostáva zo všetkých kľúčov v rozsahu medzi k1 a k2.
- Na rozdiel od stromu binárneho vyhľadávania, štruktúra údajov stromu B rastie a zmenšuje sa od koreňa. Zatiaľ čo binárny vyhľadávací strom rastie smerom nadol a zmenšuje sa smerom nadol.
- Podobne ako pri iných samovyvážených binárnych vyhľadávacích stromoch je časová zložitosť dátovej štruktúry B stromu pre operácie ako vyhľadávanie, vkladanie a mazanie O(log?n) .
- Vloženie uzla do stromu B prebieha iba v listovom uzle.
Uvažujme o nasledujúcom príklade stromu B minimálneho rádu 5.
Obrázok 2 A B Strom poriadku 5
Poznámka: Hodnota minimálnej objednávky je oveľa vyššia ako 5 v praktickom strome B.
Vo vyššie uvedenom diagrame môžeme pozorovať, že všetky listové uzly sú na rovnakej úrovni a všetky nelistové uzly nemajú prázdny podstrom a pozostávajú z kľúčov o jeden menší, než je počet ich potomkov.
objekt java
Stanovená formulácia pravidiel stromu B:
Každý B strom závisí od kladného konštantného celého čísla známeho ako MINIMÁLNE , ktorý sa používa na určenie počtu dátových prvkov, ktoré môžu byť uložené v jednom uzle.
Pravidlo 1: Koreň môže mať len jeden dátový element (alebo dokonca žiadne dátové elementy, ak nie sú ani potomkami); každý druhý uzol má aspoň MINIMÁLNE dátové prvky.
Pravidlo 2: Maximálny počet dátových prvkov uložených v uzle je dvojnásobok hodnoty MINIMÁLNE .
Pravidlo 3: Dátové prvky každého uzla B stromu sú uložené v čiastočne vyplnenom poli, zoradené od najmenšieho dátového prvku (v indexe 0 ) na najväčší dátový prvok (na konečnej použitej pozícii poľa).
Pravidlo 4: Celkový počet podstromov pod nelistovým uzlom je vždy o jeden väčší ako počet dátových prvkov v tomto uzle.
- podstrom 0, podstrom 1,...
Pravidlo 5: Pokiaľ ide o akýkoľvek nelistový uzol:
- Údajový prvok na indexe je väčší ako všetky dátové prvky v čísle podstromu i uzla a
- Údajový prvok v indexe je menší ako počet všetkých údajových prvkov v podstrome i+1 uzla.
Pravidlo 6: Každý list v strome B má rovnakú hĺbku. Zabezpečuje teda, že strom B zabráni problémom s nevyváženým stromom.
Operácie na dátovej štruktúre B stromu
Aby sa zabezpečilo, že počas operácií nebude narušená žiadna z vlastností dátovej štruktúry stromu B, môže byť strom B rozdelený alebo spojený. Nasledujú niektoré operácie, ktoré môžeme vykonať na strome B:
- Vyhľadávanie dátového prvku v strome B
- Vloženie dátového prvku do B stromu
- Vymazanie dátového prvku v B strome
Operácia vyhľadávania na strome B
Vyhľadávanie prvku v strome B je podobné ako v strome binárneho vyhľadávania. Ale namiesto obojsmerného rozhodnutia (doľava alebo doprava), ako je to v prípade binárneho vyhľadávacieho stromu, strom B urobí m-cestné rozhodnutie v každom uzle, kde m je počet potomkov uzla.
Kroky na vyhľadávanie dátového prvku v strome B:
Krok 1: Vyhľadávanie začína od koreňového uzla. Porovnajte vyhľadávací prvok k s koreňom.
Krok 1.1: Ak koreňový uzol pozostáva z prvku k, vyhľadávanie bude dokončené.
inurl:.git/head
Krok 1.2: Ak je prvok k menší ako prvá hodnota v koreni, presunieme sa k potomkovi úplne vľavo a potom ho vyhľadáme rekurzívne.
Krok 1.3.1: Ak má koreň iba dve deti, presunieme sa k potomkovi úplne vpravo a rekurzívne prehľadáme detské uzly.
Krok 1.3.2: Ak má root viac ako dva kľúče, zvyšok prehľadáme.
Krok 2: Ak sa prvok k nenájde ani po prejdení celého stromu, potom sa prvok vyhľadávania v strome B nenachádza.
Poďme si predstaviť vyššie uvedené kroky pomocou príkladu. Predpokladajme, že sme chceli hľadať kľúč k=34 v nasledujúcom strome B:
Obrázok 3.1. Daný strom B
- Najprv skontrolujeme, či je kľúč k = 34 je v koreňovom uzle. Keďže kľúč nie je v koreni, prejdeme k jeho podriadeným uzlom. Môžeme tiež pozorovať, že koreňový uzol má dve deti; preto porovnáme požadovanú hodnotu medzi dvoma kľúčmi.
Obrázok 3.2. Kľúč k nie je prítomný v koreňovom adresári - Teraz, keď si môžeme všimnúť, že kľúč k je väčší ako koreňový uzol, t.j. 30, budeme pokračovať so správnym potomkom koreňa.
Obrázok 3.3. Tlačidlo k > 30, posuňte dieťa doprava - Teraz porovnáme kľúč k s hodnotami prítomnými v uzle, t.j. 40 a 50, v tomto poradí. Keďže kľúč k je menší ako ľavý kľúč, teda 40, presunieme sa do ľavého potomka uzla.
Obrázok 3.4. Kľúč k<40, move to left child< li> - Keďže hodnota v ľavom potomkovi 40 je 34, čo je požadovaná hodnota, môžeme konštatovať, že kľúč sa našiel a operácia vyhľadávania je dokončená.
Obrázok 3.4. Kľúč k = 34, ľavé dieťa 40
Porovnávali sme kľúč so štyrmi rôznymi hodnotami vo vyššie uvedenom príklade, kým sme ho nenašli. Časová zložitosť potrebná na operáciu vyhľadávania v strome B je teda O(log?n) .
Operácia vloženia na strom B
Pri vkladaní dátového prvku do B stromu musíme najprv skontrolovať, či sa daný prvok už v strome nachádza alebo nie. Ak sa dátový prvok nájde v strome B, operácia vloženia sa neuskutoční. Ak to tak však nie je, pokračujeme vo vkladaní ďalej. Pri vkladaní prvku do listového uzla je potrebné venovať pozornosť dvom scenárom:
Kroky na vloženie dátového prvku do B stromu:
Krok 1: Začneme výpočtom maximálneho počtu kľúčov v uzle na základe poradia B stromu.
Krok 2: Ak je strom prázdny, pridelí sa koreňový uzol a vložíme kľúč, ktorý funguje ako koreňový uzol.
Krok 3: Teraz vyhľadáme príslušný uzol na vloženie.
Krok 4: Ak je uzol plný:
Krok 4.1: Dátové prvky vložíme vzostupne.
Krok 4.2: Ak sú dátové prvky väčšie ako maximálny počet kľúčov, rozdelíme celý uzol na mediáne.
Krok 4.3: Zatlačíme stredný kľúč nahor a rozdelíme ľavý a pravý kľúč ako ľavé a pravé dieťa.
Krok 5: Ak uzol nie je plný, vložíme uzol vzostupne.
Poďme si predstaviť vyššie uvedené kroky pomocou príkladu. Predpokladajme, že sme povinní vytvoriť B strom poriadku 4. Dátové prvky, ktoré je potrebné vložiť do B stromu, sú 5,3,21,11,1,16,8,13,4 a 9 .
- Keďže m sa rovná 3, maximálny počet kľúčov pre uzol = m-1 = 3-1 = 2 .
- Začneme vkladaním 5 v prázdnom strome.
Obrázok 4.1. Vkladanie 5 - Teraz vložíme 3 do stromu. Keďže 3 je menšie ako 5, vložíme 3 naľavo od 5 do toho istého uzla.
Obrázok 4.2. Vkladanie 3 - Teraz do stromu vložíme 21 a keďže 21 je väčšie ako 5, vloží sa napravo od 5 v tom istom uzle. Keďže však vieme, že maximálny počet kľúčov v uzle je 2, jeden z týchto kľúčov sa presunie do vyššie uvedeného uzla, aby sa rozdelil. Teda 5, stredný dátový prvok, sa posunie nahor a 3 a 21 sa stanú jeho ľavým a pravým uzlom.
Obrázok 4.3. Vkladanie 21 - Teraz je čas vložiť ďalší dátový prvok, t.j. 11, ktorý je väčší ako 5, ale menší ako 21. Preto sa 11 vloží ako kľúč naľavo od uzla pozostávajúceho z 21 ako kľúča.
Obrázok 4.4. Vkladanie 11 - Podobne do stromu vložíme ďalší dátový prvok 1 a ako môžeme pozorovať, 1 je menej ako 3; preto bude vložený ako kľúč naľavo od uzla pozostávajúceho z 3 ako kľúča.
Obrázok 4.5. Vkladanie 1 - Teraz do stromu vložíme dátový prvok 16, ktorý je väčší ako 11, ale menší ako 21. Počet kľúčov v tomto uzle však presahuje maximálny počet kľúčov. Preto sa uzol rozdelí a presunie stredný kľúč do koreňového adresára. Preto sa 16 vloží napravo od 5, čím sa 11 a 21 rozdelia na dva samostatné uzly.
Obrázok 4.6. Vkladanie 16 - Dátový prvok 8 bude vložený ako kľúč naľavo od 11.
Obrázok 4.7. Vkladanie 8 - Do stromu vložíme 13, čo je menej ako 16 a väčšie ako 11. Preto by sa mal dátový prvok 13 vložiť napravo od uzla pozostávajúceho z 8 a 11. Keďže však maximálny počet kľúčov v strome môže len 2, dôjde k rozdeleniu, pričom sa stredný dátový prvok 11 presunie do vyššie uvedeného uzla a 8 a 13 do dvoch samostatných uzlov. Teraz bude vyššie uvedený uzol pozostávať z 5, 11 a 16, čo opäť presahuje maximálny počet kľúčov. Preto dôjde k ďalšiemu rozdeleniu, čím sa dátový prvok 11 stane koreňovým uzlom s 5 a 16 ako jeho potomkami.
Obrázok 4.8. Vkladanie 13 - Keďže dátový prvok 4 je menší ako 5, ale väčší ako 3, bude vložený napravo od uzla pozostávajúceho z 1 a 3, čo opäť prekročí maximálny počet kľúčov v uzle. Preto opäť dôjde k úniku a presunie 3 do horného uzla vedľa 5.
Obrázok 4.9. Vkladanie 4 - Nakoniec sa dátový prvok 9, ktorý je väčší ako 8, ale menší ako 11, vloží napravo od uzla pozostávajúceho z 8 ako kľúč.
Obrázok 4.10. Vkladanie 9
Vo vyššie uvedenom príklade sme vykonali rôzne porovnania. Prvá hodnota bola priamo vložená do stromu; potom sa každá hodnota musela porovnať s uzlami dostupnými v tomto strome. Časová zložitosť operácie vloženia do stromu B závisí od počtu uzlov a .
Odstránenie operácie na strome B
Odstránenie dátového prvku na strome B obsahuje tri primárne udalosti:
- Vyhľadaním uzla, kde existuje kľúč, ktorý sa má odstrániť,
- Vymazanie kľúča a
- V prípade potreby vyvážte strom.
Pri odstraňovaní prvku zo stromu môže nastať stav známy ako podtečenie. Podtečenie nastane, keď uzol pozostáva z menšieho ako minimálneho počtu kľúčov; malo by to držať.
Pred vizualizáciou operácie odstránenia/odstránenia je potrebné porozumieť nasledujúcim výrazom:
Nasledujú tri výrazné prípady operácie vymazania v strome B:
Prípad 1: Vymazanie/odstránenie kľúča leží v uzle listu - Tento prípad sa ďalej delí na dva rôzne prípady:
1. Vymazanie/odstránenie kľúča neporušuje vlastnosť minimálneho počtu kľúčov, ktoré by mal uzol držať.
Poďme si tento prípad predstaviť pomocou príkladu, kde vymažeme kľúč 32 z nasledujúceho B stromu.
Obrázok 4.1: Vymazanie kľúča listového uzla (32) zo stromu B
Ako môžeme pozorovať, vymazanie 32 z tohto stromu neporušuje vyššie uvedenú vlastnosť.
2. Vymazanie/odstránenie kľúča porušuje vlastnosť minimálneho počtu kľúčov, ktoré by mal uzol držať. V tomto prípade si musíme požičať kľúč od jeho blízkeho súrodeneckého uzla v poradí zľava doprava.
Najprv navštívime najbližšieho súrodenca Leva. Ak má ľavý súrodenecký uzol viac ako minimálny počet kľúčov, požičia si kľúč z tohto uzla.
slučka for v skripte shellu
V opačnom prípade skontrolujeme požičanie od najbližšieho pravého súrodeneckého uzla.
Poďme si teraz predstaviť tento prípad pomocou príkladu, kde vymažeme 31 z vyššie uvedeného B stromu. Kľúč si v tomto prípade požičiame od ľavého súrodeneckého uzla.
Obrázok 4.2: Vymazanie kľúča listového uzla (31) zo stromu B
Ak oba blízke súrodenecké uzly už pozostávajú z minimálneho počtu kľúčov, potom uzol zlúčime buď s ľavým súrodeneckým uzlom, alebo s pravým. Tento proces zlučovania sa vykonáva cez nadradený uzol.
Poďme znova vizualizovať odstránením kľúča 30 z vyššie uvedeného B stromu.
Obrázok 4.3: Odstránenie kľúča listového uzla (30) zo stromu B
Prípad 2: Vymazanie/odstránenie kľúča spočíva v uzle mimo listu - Tento prípad sa ďalej delí na rôzne prípady:
1. Nelistový/vnútorný uzol, ktorý je odstránený, je nahradený predchodcom v poradí, ak má ľavý podriadený uzol viac ako minimálny počet kľúčov.
Ukážme si tento prípad na príklade, kde vymažeme kľúč 33 zo stromu B.
Obrázok 4.4: Odstránenie kľúča listového uzla (33) zo stromu B
2. Nelistový/vnútorný uzol, ktorý je odstránený, je nahradený následníkom v poradí, ak má pravý dcérsky uzol viac ako minimálny počet kľúčov.
Ak má ktorýkoľvek z potomkov minimálny počet kľúčov, potom zlúčime ľavý a pravý podriadený uzol.
Poďme si tento prípad predstaviť odstránením kľúča 30 zo stromu B.
Obrázok 4.5: Odstránenie kľúča listového uzla (30) zo stromu B
Po zlúčení, ak má nadradený uzol menší než minimálny počet kľúčov, je možné hľadať súrodencov, ako napr. Prípad 1 .
Prípad 3: V nasledujúcom prípade sa výška stromu zmenšuje. Ak cieľový kľúč leží v internom uzle a odstránenie kľúča vedie k menšiemu počtu kľúčov v uzle (čo je menej, než je nevyhnutné minimum), potom hľadajte predchodcu v poradí a následníka v poradí. Ak obe deti majú minimálny počet kľúčov, požičanie nemôže nastať. To vedie k Prípad 2(3) t.j. zlúčenie podradených uzlov.
rovná sa metóda java
Opäť budeme hľadať súrodenca, aby sme si požičali kľúč. Ak však aj súrodenec pozostáva z minimálneho počtu kľúčov, potom uzol zlúčime so súrodencom spolu s nadradeným uzlom a podriadené uzly usporiadame podľa požiadaviek (vzostupne).
Vizualizujme si tento prípad pomocou príkladu, kde vymažeme dátový prvok 10 z daného B stromu.
Obrázok 4.6: Odstránenie kľúča listového uzla (10) zo stromu B
Časová zložitosť vo vyššie uvedených príkladoch sa líši v závislosti od miesta, odkiaľ je potrebné kľúč odstrániť. Časová zložitosť operácie vymazania v strome B je teda O(log?n) .
Záver
V tomto návode sme sa dozvedeli o strome B a vizualizovali sme jeho rôzne operácie na rôznych príkladoch. Tiež sme pochopili niektoré základné vlastnosti a pravidlá B stromu.