Lekce 8 - B-stromy
V minulé lekci, AVL strom, jsme si udělali popis AVL stromu, samovyvažovací vyhledávací struktury a základních operací vkládání, vymazání a vyhledávání prvků.
B-stromy jsou jedním z typů datových struktur, konkrétně z vyhledávacích stromů. Od většiny ostatních se však liší v tom, že v jeho uzlech lze uložit více než jeden prvek. Co to s sebou přináší? Pojďme se na to podívat!
Nejdříve si definujeme B-stromy, konkrétně jejich vlastnosti. Pomůže
nám to k jednoduššímu pochopení algoritmu
Vlastnosti
- 1. Maximální počet prvků v uzlu je u všech uzlů stejný a volíme ho
na začátku (od této chvíle budu tuto vlastnost nazývat kapacita a značit
ji budu písmenem r (r >= 2)). Pojďme si zde rovnou říci, že důležitá
je většinou polovina z kapacity. Polovinu (budeme značit p) z r vypočítáme
snadno:
p=r/2
(v případě sudéhor
),p=(r-1)/2
(v případě lichéhor
) - 2. Jednotlivé uzly (kořene) musí být aspoň z poloviny zaplněné, nesmí však překročit r.
- 3. Prvky uložené v uzlu jsou seřazeny vzestupně.
- 4. Uzel je buďto list anebo má o jednoho následníka více, než je počet prvků v něm uložený. Následník pak v sobě obsahuje prvky větší než jeho levá hodnota v předkovi a menší než pravá hodnota předkovi.
- 5. Listy jsou v B-stromu jen v jeho poslední (nejspodnější) úrovni. Jinými slovy vzdálenost všech listů od kořene je rovna (a je rovná i s výškou stromu).

Na obrázku vidíme B-strom o výšce 1 a s kapacitou 3. Jelikož je v jeho kořenu (uzel nahoře) jeden prvek, podle vlastnosti výše musí mít přesně 2 následníky, pokud to tedy není listový uzel. Na druhou stranu, jeho potomci jsou listové uzly, takže musí být na stejné úrovni. Můžete také zkontrolovat, že prvky jsou seřazené, takže všechny vlastnosti platí.
Někdy můžete v souvislosti s B-stromy zaslechnout pojem
"řád". B-strom s kapacitou uzlu r
má řád r + 1
,
jelikož nelistový uzel může mít až r + 1
následníků.
Vyhledávání
Nyní k samotnému algoritmu. Kvůli odlišnosti implementace, velikosti a složitosti, zde nebudu uvádět pseudokód nebo kód v nějakém konkrétním jazyce. Ale napíši detailní popis slovy pro vyhledávání, vkládání a odstraňování.
Značení
- Aktuální uzel budeme označovat
u
(na začátku jím bude kořen uzlu - nejvyšší uzel, který nemá žádného předka) - Hledanou hodnotu poté budeme označovat
x
.
Algoritmus
1. Vyhledání x
v uzlu u
(můžeme použít
například sekvenční
nebo binární
vyhledávání), tento krok může skončit 3 způsoby:
x
byl v u`` nalezen - vyhledávání úspěšně končíx
nebyl nalezen vu
au
je list - vyhledávání neúspěšně končíx
nebyl vu
nalezen au
je nelistový. V tom případě skončilo v místě, kde je odkaz na jeho následníka, který by měl prvek obsahovat. Pokračujeme tedy v něm, změníme aktuální uzelu
na onoho následníka a vrátíme se na krok 1.

A to je vše Velice
snadné, že?
Vkládání prvku
Značení
- Aktuální uzel -
u
- Přidávaný prvek -
x
Algoritmus
1. Provedeme vyhledání ve stromu, může to skončit 2 způsoby:
- prvek
x
byl nalezen. Přidávání končí (nepředpokládá se více stejných prvků ve stromu) - vyhledávání skončilo v listovém uzlu
u
, kde by měl prvek nalézat (vzhledem k velikosti),x
na toto místo vložíme. Pokud uzelu
není zaplněn (počet prvků vu
není větší nežr
), přidávání končí. Pokud všakr
přesáhneme, dojde k rozdělení uzlů.
2. Rozdělujeme uzly. Jestliže má u
po přidání
r+1
prvků, rozdělíme uzel na tři části. Využijeme známého
p
a rozdělíme ho tedy:
P
prvků na začátku uzlu + prvek uprostřed +
p
prvků na konci uzlu.
První a druhá část budou nové uzly (můžete si všimnout, podmínka minimálního počtu p bude platit) a prvek uprostřed přesuneme do předchůdce, na místo, kde byl odkaz na uzel u. Jakmile přesuneme prvek, vytvoříme nalevo a napravo od něho odkazy na nově vzniklé listy.
Možná vás napadlo, že jsme tím problém nemuseli vyřešit. Ano,
skutečně, v případě umístění prvku výše může dojít k přeplnění
uzlu, do kterého jsme prvek vložili. To vyřešíme stejným způsobem. Krok 2
opakujeme, dokud se nedostaneme ke kořenu nebo dokud nedojdeme k uzlu, který
nebude přeplněn. Když dojde k přeplnění i v kořenu, rozdělí se znovu na
tři části a prostřední bude umístěna do samostatného uzlu a tento uzel
se stane novým kořenem. Části s p
prvky budou znovu jeho
odkazy. V této chvíli dochází ke zvětšení stromu.
Zkusme si to na příkladu. Vezměme si například tento strom kapacity 4:

Přidáme prvek 15
. To by neměl být problém. Problémem však
je, že jsme překročili kapacitu uzlu:

Naštěstí víme jak to vyřešit - rozdělíme si přeplněný uzel a prvek přesuneme nahoru:

Odebírání prvku
Značení
- Aktuální uzel -
u
- Odebíraný prvek -
x
Algoritmus
1. Provedeme vyhledání ve stromu prvku x
, může to skončit 3
způsoby:
x
nebylo ve stromu nalezeno - operace končí, není co odebrat.x
bylo nalezeno v listovém uzlu (uzel v nejspodnější úrovni).X
z uzlu odstraníme. Když je uzel aspoň z poloviny (p
) zaplněn, operace končí. Jinak přejdeme ke 2. kroku.x
bylo nalezeno v nelistovém uzlu.X
z uzlu odstraníme a na volné místo umístíme buď největší (tedy nejpravější) prvek z levého podstromu (nejpravější list). Anebo nejmenší (tedy nejlevější) prvek v pravém podstromu (nejlevější list). Pokud je ve všech listových uzlech aspoň polovina prvků, operace odebrání končí. Jinak přejdeme ke 2. kroku.
2. Může se stát, že narušíme podmínku - každý uzel musí být aspoň
z poloviny (p
) zaplněn, má tedy p-1
prvků. Tento
stav lze, samozřejmě, řešit. V podstatě máme řešení 2:
Prakticky to budu předvádět na tomto stromu (r = 4
)

- List
u
má alespoň jednoho sourozence, který obsahuje více nežp
prvků. Přesuneme do uzluu
prvek z předchůdce a na nově vzniklé místo v předchůdci přesuneme největší (v případě, že soused je vlevo odu
) či nejmenší (v případě, že soused je vpravo odu
) prvek ze souseda.
Odstraňujeme 15
.

- List u nemá sourozence, kteří mají více než
p
prvků. Vytvoříme tedy nový list sr
prvky z uzluu
+ prvek z předchůdce + prvky ze sourozenceu
.
Odstraňujeme 12
.

Zde může nastat situace, že v předchůdci znova dojde k tomu, že počet
prvků bude p-1
. Řeší se to stejně, záleží na sourozencích.
Můžeme se tak dostat až ke kořenu, pokud sloučíme uzel s kořenem, ve
kterém byl jen jeden prvek, nově vzniklý uzel se stává kořenem.
A nyní ukáži příklad se změnou kořene. Vezmeme si tento strom, který
bude mít kapacitu 4
a odstraníme prvek v kořenu -
60
.

Odstraníme prvek 60
a přesuneme prvek 59
(největší prvek v levém podstromu) na místo v kořeně, mohli bychom
přesunout i 62
, ale zbytečně by se nám rozbila podmínka,
která určuje, že musí být aspoň z poloviny zaplněný.

Vidíme, že všechny vlastnosti B
stromu platí.
A to je vše
Na závěr pro zájemce uvedu časovou složitost. U
vyhledávání složitost závisí, jak velké máme r
a jakou
metodu vyhledávání použijeme v jednotlivých uzlech. Když zvolíme
binární vyhledávání, má logaritmickou složitost. Dále musíme
započítat procházení uzlů od kořene k listu, zde výška stromu závisí
logaritmicky na počtu prvků. Vyhledávání má tedy logaritmickou složitost.
Základem přidání a odebrání prvku je vyhledávání a dále (možný)
průchod nahoru. Zde je průchod nahoru zas závislý na výšce stromu. Tedy
všechny operace mají logaritmickou složitost, která je již docela
příjemná
V další lekci, Srovnání jednoduchých vyhledávacích struktur, si srovnáme jednoduché vyhledávací struktury - algoritmy BST, binární vyhledávací strom, setříděné pole a nesetříděné pole.