Dátová štruktúra stromu B a stromu B + v C ++

b tree b tree data structure c

Tento výukový program v C ++ vysvetľuje datové štruktúry stromu B a stromu B +. Používajú sa na ukladanie údajov na disky, keď nie je možné uložiť všetky údaje do hlavnej pamäte:

B-strom je samostatne vyvážený strom ako aj špecializovaný strom m-way, ktorý sa používa na prístup na disk.

Keď je množstvo údajov, ktoré sa majú uložiť, veľmi vysoké, nemôžeme uložiť všetky údaje do hlavnej pamäte. Preto ukladáme údaje na disk. Prístup k údajom z disku trvá dlhšie v porovnaní s prístupom k hlavnej pamäti.

Ak je počet kľúčov údajov uložených na diskoch veľmi vysoký, k údajom sa zvyčajne pristupuje vo forme blokov. Čas prístupu do týchto blokov je priamo úmerný výške stromu.

=> Kliknutím sem zobrazíte sériu školení Absolute C ++.

Čo sa dozviete:

• B-strom v C ++
  • Základné operácie s B-stromom
    • # 1) Vyhľadávanie
    • # 2) Vkladanie
    • # 3) Vymazanie
  • Aplikácie stromov B.
• Strom B + v C ++
  • Výhody stromov B +
• Rozdiel medzi stromom B a stromom B +
• Záver
  • Odporúčané čítanie

B-strom v C ++

B-strom je plochý strom, tj. Výška stromu B je minimálna. Namiesto toho je do každého uzla B-stromu vložených toľko kľúčov. Udržiavaním výšky B-stromu na minime je prístup rýchlejší v porovnaní s inými vyváženými stromami, ako sú AVL stromy.

Typický strom B je uvedený nižšie:

softvér, ktorý je nainštalovaný v počítači a slúži na správu virtuálnych strojov

Spravidla je veľkosť uzla v B-strome zachovaná rovnaká ako veľkosť bloku.

Ďalej sú uvedené niektoré z vlastností B-Tree.

• Všetky listy B-stromu sú na rovnakej úrovni.
• B-strom rádu m môže mať najviac m-1 kľúčov a m detí.
• Každý uzol v B-strome má najviac m detí.
• Koreňový uzol musí mať najmenej dva uzly.
• Každý uzol okrem koreňového uzla a listového uzla obsahuje m / 2 potomkov.

Ďalej diskutujeme o základných operáciách B-stromu.

Základné operácie s B-stromom

Ďalej sú uvedené niektoré základné operácie B-stromu.

# 1) Vyhľadávanie

Vyhľadávanie v strome B je podobné ako v BST. Ak chceme vo vyššie uvedenom strome vyhľadať položku 3, budeme postupovať nasledovne:

• Porovnajte 3 s koreňovými prvkami. Tu, 3<6 and 3 <15. So we proceed to the left subtree.
• Porovnajte 3 a 4 v ľavom podstrome. Ako 3<4, we proceed to the left subtree of node 4.
• Nasledujúci uzol má dva kľúče, 2 a 3. 3> 2, zatiaľ čo 3 = 3. Takže sme našli kľúč v tomto uzle. Vráťte sa na nájdené miesto.

Vyhľadávanie v strome B závisí od výšky stromu. Vyhľadanie danej položky zvyčajne trvá O (log n).

# 2) Vkladanie

Vloženie novej položky do stromu B sa vykonáva na úrovni uzlov listu.

Nasleduje postupnosť krokov (algoritmus) na vloženie novej položky do stromu B.

• Prejdite stromom B a nájdite miesto v listových uzloch na vloženie položky.
• Ak listový uzol obsahuje kľúče
• Inak ak sú kľúče uzla listu = m-1, potom:
  • Vložte novú položku do rastúceho počtu položiek.
  • Vezmite strednú hodnotu uzlov a uzol rozdeľte na dva uzly.
  • Zatlačte medián na jeho nadradený uzol.
  • Ak kľúč nadradeného uzla = m-1, zopakujte vyššie uvedené kroky aj pre nadradený uzol. To sa deje, kým nenájdeme vhodný listový uzol.
• Nakoniec vložte prvok.

Vloženie do stromu B sme demonštrovali nasledovne.

Vložme položku 70 do stromu zobrazeného nižšie.

predvolená brána systému Windows 10 nie je k dispozícii

Daný strom má minimálny stupeň ‘m’ = 3. Preto sa do každého uzla zmestí 2 × m -1 = 5 klávesov.

Teraz vložíme položku 70. Pretože v uzle môžeme mať 5 kľúčov, porovnáme prvok 70 s koreňovým prvkom 30. Od 70> 30 vložíme položku 70 do pravého podstromu.

V pravom podstrome máme uzol s kľúčmi 40, 50, 60. Pretože každý uzol môže mať v sebe 5 kľúčov, vložíme do tohto samotného uzla položku 70.

Po vložení vyzerá strom B nasledujúcim spôsobom.

# 3) Vymazanie

Rovnako ako vkladanie, aj mazanie kľúča sa vykonáva na úrovni uzlov listov. Ale na rozdiel od vloženia je vymazanie komplikovanejšie. Kľúč, ktorý sa má vymazať, môže byť buď listový uzol alebo vnútorný uzol.

Pri mazaní kľúča postupujeme podľa nižšie uvedenej postupnosti krokov (algoritmu).

1. Vyhľadajte listový uzol.

dva. V prípade, že počet kľúčov v uzle> m / 2, potom daný kľúč z uzla vymažte.

3. V prípade, že listový uzol nemá kľúče m / 2, musíme kľúče dokončiť odobratím kľúčov z pravého alebo ľavého podstromu, aby sme udržali strom B.

Postupujeme podľa týchto krokov:

• Ak ľavý podstrom obsahuje prvky m / 2, jeho najväčší prvok zatlačíme do nadradeného uzla a potom presunieme intervenujúci prvok na miesto, kde bol kľúč vymazaný.
• Ak pravý podstrom obsahuje prvky m / 2, jeho najmenší prvok zatlačíme do nadradeného uzla a potom presunieme intervenujúci prvok na miesto, kde bol kľúč vymazaný.

Štyri. Ak žiadny uzol nemá m / 2 uzly, vyššie uvedené kroky nemožno vykonať, preto vytvoríme nový listový uzol spojením dvoch listových uzlov a zasahujúceho prvku nadradeného uzla.

5. Ak je rodič bez uzlov m / 2, opakujeme vyššie uvedené kroky pre príslušný nadradený uzol. Tieto kroky sa opakujú, až kým nedostaneme vyvážený strom B.

Nižšie je uvedená ilustrácia na odstránenie uzla zo stromu B.

Zvážte ešte raz nasledujúci strom B.

Predpokladajme, že chceme odstrániť kľúč 60 zo stromu B. Ak skontrolujeme strom B, zistíme, že kľúč, ktorý sa má vymazať, sa nachádza v uzle listu. Vymažeme kľúč 60 z tohto listového uzla.

Teraz bude strom vyzerať nasledovne:

Môžeme si všimnúť, že po odstránení kľúča 60 uzol listu B stromu spĺňa požadované vlastnosti a nemusíme robiť ďalšie úpravy stromu B.

Keby sme však mali kľúč 20 vymazať, potom by v uzle ľavého listu zostal iba kľúč 10. V takom prípade by sme museli presunúť koreň 30 do listového uzla a presunúť kláves 40 do koreňa.

Pri mazaní kľúča zo stromu B by ste preto mali byť opatrní a nemali by sa porušovať vlastnosti stromu B.

Traverz v strome B.

Traverz v strome B je tiež podobný inorderovému traverzu v BST. Začíname rekurzívne zľava, potom prídeme ku koreňu a pokračujeme smerom k ľavému podstromu.

Aplikácie stromov B.

• Stromy B sa používajú na indexovanie údajov, najmä vo veľkých databázach, pretože prístup k údajom uloženým vo veľkých databázach na diskoch je veľmi časovo náročný.
• Hľadanie údajov vo väčších netriedených súboroch údajov trvá veľa času, ale dá sa to výrazne vylepšiť indexovaním pomocou stromu B.

Strom B + v C ++

Strom B + je rozšírením stromu B. Rozdiel v B + strome a B strome je v tom, že v B strome môžu byť kľúče a záznamy uložené ako interné aj ako listové uzly, zatiaľ čo v B + stromoch sú záznamy uložené ako listové uzly a kľúče sú uložené iba vo interných uzloch.

Záznamy sú navzájom spojené spôsobom prepojeného zoznamu. Toto usporiadanie umožňuje rýchlejšie a efektívnejšie vyhľadávanie stromov B +. Vnútorné uzly stromu B + sa nazývajú indexové uzly.

kde nájdem kľúč zabezpečenia siete na mojom smerovači

Stromy B + majú dva rády, t. J. Jeden pre vnútorné uzly a druhý pre listové alebo vonkajšie uzly.

Nižšie je uvedený príklad stromu B +.

Pretože B + strom je rozšírením B-stromu, základné operácie, o ktorých sme hovorili v rámci témy B-strom, stále platia.

Pri vkladaní aj odstraňovaní by sme mali zachovať základné vlastnosti stromov B + neporušené. Operácia vymazania v strome B + je však porovnateľne ľahšia, pretože údaje sa ukladajú iba v listových uzloch a z listových uzlov sa odstránia vždy.

Výhody stromov B +

• Môžeme načítať záznamy v rovnakom počte prístupov na disk.
• V porovnaní so stromom B je výška stromu B + menšia a zostáva vyrovnaná.
• Na indexovanie používame kľúče.
• K údajom v strome B + je možné pristupovať postupne alebo priamo, pretože uzly listov sú usporiadané do prepojeného zoznamu.
• Vyhľadávanie je rýchlejšie, pretože údaje sa ukladajú iba v listových uzloch a ako prepojený zoznam.

Rozdiel medzi stromom B a stromom B +

Záver

V tomto tutoriáli sme podrobne diskutovali o B-stromoch a B + stromoch. Tieto dve dátové štruktúry sa používajú, keď existuje veľmi veľké množstvo údajov a keď nie je možné uložiť všetky údaje do hlavnej pamäte. Na ukladanie údajov na disky teda používame strom B a strom B +.

Vyhľadávanie stromov B je o niečo pomalšie, pretože údaje sa ukladajú do vnútorných uzlov aj do listových uzlov. B + strom je rozšírením B-stromu a údaje sa tu ukladajú iba v listových uzloch. Vďaka tomuto faktoru je vyhľadávanie v strome B + rýchlejšie a efektívnejšie.

=> Úplný zoznam výukových programov C ++ nájdete tu.

Odporúčané čítanie

• Dátová štruktúra stromu a haldy AVL v C ++
• Prepojená dátová štruktúra zoznamu v C ++ s ilustráciou
• Dátová štruktúra frontu v C ++ s ilustráciou
• Skladať dátovú štruktúru v C ++ s ilustráciou
• Dátová štruktúra kruhového prepojeného zoznamu v C ++ s ilustráciou
• Úvod do dátových štruktúr v C ++
• Štruktúra dát prioritného frontu v C ++ s ilustráciou
• Štruktúra dát dvojnásobne prepojeného zoznamu v C ++ s ilustráciou