Datová struktura stromu B a stromu B + v C ++

b tree b tree data structure c

Tento výukový program C ++ vysvětluje datové struktury stromu B a stromu B +. Používají se k ukládání dat na disky, když celá data nelze uložit do hlavní paměti:

B-strom je samostatně vyvážený strom a také speciální m-way strom, který se používá pro přístup na disk.

Když je množství dat, která mají být uložena, velmi vysoké, nemůžeme uložit všechna data do hlavní paměti. Proto ukládáme data na disk. Přístup k datům z disku trvá déle ve srovnání s přístupem k hlavní paměti.

Když je počet klíčů dat uložených na discích velmi vysoký, k datům se obvykle přistupuje ve formě bloků. Čas přístupu k těmto blokům je přímo úměrný výšce stromu.

=> Klikněte sem a získejte Absolute C ++ Training Series.

Co se naučíte:

• B-strom v C ++
  • Základní operace s B-stromem
    • # 1) Hledání
    • # 2) Vložení
    • # 3) Smazání
  • Aplikace stromů B.
• Strom B + v C ++
  • Výhody stromů B +
• Rozdíl mezi B-stromem a B + stromem
• Závěr
  • Doporučené čtení

B-strom v C ++

Strom B je plochý strom, tj. Výška stromu B je omezena na minimum. Místo toho je do každého uzlu B-stromu vloženo tolik klíčů. Udržováním výšky B-stromu na minimu je přístup rychlejší ve srovnání s jinými vyváženými stromy, jako jsou stromy AVL.

Typický strom B je uveden níže:

aplikace pro převod videí z YouTube na mp3

Obecně je velikost uzlu v B-stromu stejná jako velikost bloku.

Níže jsou uvedeny některé vlastnosti B-Tree.

• Všechny listy B-stromu jsou na stejné úrovni.
• B-strom řádu m může mít nanejvýš m-1 klíčů a m dětí.
• Každý uzel v B-stromu má maximálně m dětí.
• Kořenový uzel musí mít alespoň dva uzly.
• Každý uzel kromě kořenového uzlu a listového uzlu obsahuje m / 2 podřízených.

Dále probereme některé základní operace B-stromu.

Základní operace s B-stromem

Níže jsou uvedeny některé základní operace B-Tree.

# 1) Hledání

Hledání ve stromu B je podobné jako v BST. Pokud ve výše uvedeném stromu chceme hledat položku 3, budeme postupovat následovně:

• Porovnejte 3 s kořenovými prvky. Tady, 3<6 and 3 <15. So we proceed to the left subtree.
• Porovnejte 3 se 4 v levém podstromu. Jako 3<4, we proceed to the left subtree of node 4.
• Další uzel má dva klíče, 2 a 3. 3> 2, zatímco 3 = 3. Na tomto uzlu jsme tedy našli klíč. Vraťte se na nalezené místo.

Hledání ve stromu B závisí na výšce stromu. Hledání dané položky obvykle trvá O (log n).

# 2) Vložení

Vložení nové položky do stromu B se provádí na úrovni uzlů listu.

Následuje posloupnost kroků (algoritmus) k vložení nové položky do stromu B.

• Procházejte stromem B a vyhledejte místo v uzlech listů, kam chcete položku vložit.
• Pokud listový uzel obsahuje klíče
• Jinak pokud klíče listového uzlu = m-1, pak:
  • Vložte novou položku do rostoucího počtu položek.
  • Vezměte medián uzlů a rozdělte uzel na dva uzly.
  • Zatlačte medián na jeho nadřazený uzel.
  • Pokud klíč nadřazeného uzlu = m-1, opakujte výše uvedené kroky také pro nadřazený uzel. To se děje, dokud nenajdeme příslušný listový uzel.
• Nakonec vložte prvek.

Ukázali jsme vložení do stromu B následujícím způsobem.

Vložíme položku 70 do níže zobrazeného stromu.

výchozí brána Windows 10 není k dispozici

Daný strom je s minimálním stupněm „m“ = 3. Proto se může každý uzel ubytovat, 2 * m -1 = 5 kláves uvnitř.

Nyní vložíme položku 70. Protože v uzlu můžeme mít 5 klíčů, porovnáme prvek 70 s kořenovým prvkem 30. Od 70> 30 vložíme položku 70 do pravého podstromu.

V pravém podstromu máme uzel s klíči 40, 50, 60. Protože každý uzel může mít 5 klíčů, vložíme do tohoto uzlu samotnou položku 70.

Po vložení vypadá strom B následovně.

# 3) Smazání

Stejně jako vkládání se i mazání klíče provádí na úrovni uzlů listu. Ale na rozdíl od vložení je odstranění komplikovanější. Klíč, který má být odstraněn, může být buď listový uzel, nebo interní uzel.

Chcete-li odstranit klíč, postupujte podle níže uvedené sekvence kroků (algoritmus).

1. Vyhledejte uzel listu.

2. V případě, že počet klíčů v uzlu> m / 2, pak odstraňte daný klíč z uzlu.

3. V případě, že uzel listu nemá klíče m / 2, musíme klíče dokončit převzetím klíčů z pravého nebo levého podstromu, abychom udrželi strom B.

Postupujeme podle těchto kroků:

• Pokud levý podstrom obsahuje prvky m / 2, posuneme jeho největší prvek do nadřazeného uzlu a poté přesuneme intervenující prvek na místo, kde byl klíč odstraněn.
• Pokud pravý podstrom obsahuje prvky m / 2, zatlačíme jeho nejmenší prvek do nadřazeného uzlu a poté přesuneme intervenující prvek na místo, kde byl klíč odstraněn.

Čtyři. Pokud žádný uzel nemá m / 2 uzly, nelze výše uvedené kroky provést, proto vytvoříme nový listový uzel spojením dvou listových uzlů a intervenujícího prvku nadřazeného uzlu.

5. Pokud je nadřazený uzel bez m / 2 uzlů, opakujeme výše uvedené kroky pro dotyčný nadřazený uzel. Tyto kroky se opakují, dokud nedostaneme vyvážený strom B.

Níže je uveden příklad odstranění uzlu ze stromu B.

Zvažte ještě jednou následující strom B.

Předpokládejme, že chceme odstranit klíč 60 ze stromu B. Pokud zkontrolujeme strom B, zjistíme, že klíč, který má být odstraněn, je přítomen v uzlu listu. Odstranili jsme klíč 60 z tohoto listového uzlu.

jak otevřít xml soubor ve Wordu

Nyní bude strom vypadat takto:

Můžeme si všimnout, že po odstranění klíče 60 uzel listu stromu B splňuje požadované vlastnosti a nemusíme dělat žádné další úpravy stromu B.

Pokud bychom však museli odstranit klíč 20, pak by v uzlu levého listu zůstal pouze klíč 10. V tomto případě bychom museli přesunout kořen 30 do uzlu listu a přesunout klíč 40 do kořene.

Při mazání klíče ze stromu B je tedy třeba postupovat opatrně a neměly by být porušeny vlastnosti stromu B.

Traverz ve stromu B.

Traversal in B tree is also similar to inorder traversal in BST. Začneme rekurzivně zleva, pak přijdeme ke kořenu a pokračujeme směrem k levému podstromu.

Aplikace stromů B.

• Stromy B se používají k indexování dat, zejména ve velkých databázích, protože přístup k datům uloženým ve velkých databázích na discích je velmi časově náročný.
• Hledání dat ve větších netříděných souborech dat zabere hodně času, ale toto lze výrazně zlepšit indexováním pomocí stromu B.

Strom B + v C ++

Strom B + je rozšířením stromu B. Rozdíl ve stromu B + a stromu B je v tom, že ve stromu B mohou být klíče a záznamy uloženy jako interní i listové uzly, zatímco ve stromech B + jsou záznamy uloženy jako listové uzly a klíče jsou uloženy pouze v interních uzlech.

Záznamy jsou navzájem propojeny způsobem propojeného seznamu. Díky tomuto uspořádání je vyhledávání stromů B + rychlejší a efektivnější. Vnitřní uzly stromu B + se nazývají indexové uzly.

Stromy B + mají dva řády, tj. Jeden pro vnitřní uzly a druhý pro listové nebo vnější uzly.

Níže je uveden příklad stromu B +.

Protože B + strom je rozšířením B-stromu, základní operace, které jsme probrali pod tématem B-strom, stále platí.

Při vkládání i mazání bychom měli zachovat základní vlastnosti stromů B + beze změny. Operace odstranění ve stromu B + je však poměrně jednodušší, protože data jsou uložena pouze v listových uzlech a budou vždy odstraněna z listových uzlů.

Výhody stromů B +

• Můžeme načíst záznamy ve stejném počtu přístupů na disk.
• Ve srovnání se stromem B je výška stromu B + menší a zůstává vyrovnaná.
• K indexování používáme klíče.
• K datům ve stromu B + lze přistupovat postupně nebo přímo, protože uzly listů jsou uspořádány v propojeném seznamu.
• Hledání je rychlejší, protože data jsou uložena pouze v listových uzlech a jako propojený seznam.

Rozdíl mezi B-stromem a B + stromem

Závěr

V tomto tutoriálu jsme podrobně diskutovali o B-stromech a B + stromech. Tyto dvě datové struktury se používají, když existuje velmi velké množství dat a když celá data nelze uložit do hlavní paměti. K ukládání dat na disky tedy používáme B-strom a B + strom.

Hledání stromů B je o něco pomalejší, protože data jsou uložena v interních uzlech i v listových uzlech. B + strom je rozšířením B-stromu a data zde jsou uložena pouze v listových uzlech. Díky tomuto faktoru je hledání ve stromu B + rychlejší a efektivnější.

=> Úplný seznam výukových programů C ++ naleznete zde.

Doporučené čtení

• Datová struktura stromu AVL a haldy v C ++
• Propojená datová struktura seznamu v C ++ s ilustrací
• Struktura dat fronty v C ++ s ilustrací
• Skládejte datovou strukturu v C ++ s ilustrací
• Datová struktura kruhového propojeného seznamu v C ++ s ilustrací
• Úvod do datových struktur v C ++
• Struktura dat prioritní fronty v C ++ s ilustrací
• Dvojnásobně propojená datová struktura seznamu v C ++ s ilustrací