Vydělávej až 160.000 Kč měsíčně! Akreditované rekvalifikační kurzy s garancí práce od 0 Kč. Více informací.
Hledáme nové posily do ITnetwork týmu. Podívej se na volné pozice a přidej se do nejagilnější firmy na trhu - Více informací.

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ého r), p=(r-1)/2 (v případě lichého r)
  • 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).
B-strom datová struktura - Vyhledávací algoritmy

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:

  1. x byl v u`` nalezen - vyhledávání úspěšně končí
  2. x nebyl nalezen v u a u je list - vyhledávání neúspěšně končí
  3. x nebyl v u nalezen a u 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í uzel u na onoho následníka a vrátíme se na krok 1.
Vyhledávání v B-stromu - Vyhledávací algoritmy

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:

  1. prvek x byl nalezen. Přidávání končí (nepředpokládá se více stejných prvků ve stromu)
  2. 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 uzel u není zaplněn (počet prvků v u není větší než r), přidávání končí. Pokud však r 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:

Vkládání prvku do B-stromu – 1 - Vyhledávací algoritmy

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:

Vkládání prvku do B-stromu – 2 - Vyhledávací algoritmy

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

Vkládání prvku do B-stromu – 3 - Vyhledávací algoritmy

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:

  1. x nebylo ve stromu nalezeno - operace končí, není co odebrat.
  2. 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.
  3. 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)

Mazání prvku z B-stromu – 1 - Vyhledávací algoritmy
  1. List u má alespoň jednoho sourozence, který obsahuje více než p prvků. Přesuneme do uzlu u 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 od u) či nejmenší (v případě, že soused je vpravo od u) prvek ze souseda.

Odstraňujeme 15.

Mazání prvku z B-stromu – 2 - Vyhledávací algoritmy
  1. List u nemá sourozence, kteří mají více než p prvků. Vytvoříme tedy nový list s r prvky z uzlu u + prvek z předchůdce + prvky ze sourozence u.

Odstraňujeme 12.

Mazání prvku z B-stromu – 3 - Vyhledávací algoritmy

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.

Mazání prvku z B-stromu – 4 - Vyhledávací algoritmy

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ý.

Mazání prvku z B-stromu – 5 - Vyhledávací algoritmy

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.


 

Předchozí článek
AVL strom
Všechny články v sekci
Vyhledávací algoritmy
Přeskočit článek
(nedoporučujeme)
Srovnání jednoduchých vyhledávacích struktur
Článek pro vás napsal Petr Valigura
Avatar
Uživatelské hodnocení:
12 hlasů
Autor se věnuje programování v různých (i funkcionálních) jazycích, nejčastěji však používá webové technologie, hlavně pak JavaScript. Baví ho zajímavé algoritmy a věci kolem softwaru obecně.
Aktivity