B-strom: Porovnání verzí

 

== Princip uložení dat ==

Data jsou ve stromu uložena jako setříděné hodnoty, které rozdělují strom na jednotlivé [[Strom (datová struktura)#Podstrom|podstromy]]. Například pokud nějaký uzel má tři potomky, musí být v tomto uzlu uloženy dva klíče ''k''₁ a ''k''₂, které budou uzel rozdělovat. Všechny hodnoty které jsou menší než ''k''₁ musí být uloženy v levém podstromu, hodnoty které jsou větší než ''k''₁ a menší než ''k''₂ musí být uloženy v prostředním podstromu, a konečně všechny hodnoty větší než ''k''₂ musí být v pravém podstromu. Na tyto podstromy jsou samozřejmě v uzlu uloženy ukazatele.

 

 

== Operace se stromem ==

 

=== Operace vyhledávání ===

## Pokud je hodnota tohoto klíče větší a '''aktuální uzel není listem''', zapamatujeme si ukazatel vlevo od tohoto klíče. Pokud je aktuální uzel zároveň listem, skočíme na krok číslo 5 (není již kde vyhledávat).

# V případě, že máme z minulého kroku ukazatel, následujeme ho a pokračujeme krokem jedna. V případě, že ukazatel není k dispozici, znamená to, že musíme následovat ukazatel, který je nejvíce vpravo (hledaná hodnota je větší než klíč s největší hodnotou v tomto uzlu).

# Nenalezli jsme požadovanou hodnotu, končíme.

 

 

Samozřejmě, že pokud přidáváme klíč do rodiče, musíme zkontrolovat, jestli se do něj vejde a pokud ne, musíme ho rozdělit stejným způsobem. Pokud se takovýmto postupem dostaneme až do kořene, musíme vytvořit nový kořen s pouze jednou položkou, která nám původní kořen rozdělí na dvě části.

 

Příklad: Máme B-strom stupně 5 tak, jako je na obrázku. Každý uzel může mít maximálně 4 klíče. Pokud do dítěte chceme uložit další hodnotu, nejde to a uzel se rozpadne. Vkládaný klíč (nemusí to být nutně klíč ''k''₃, tento klíč je zeleně zvýrazněn protože je ''prostřední'') se virtuálně vloží a poté se vybere prostřední klíč (zeleně). Tento prostřední klíč se poté vloží do rodiče (označen jako ''k''₃') a původní uzel se rozpadne na dva, tak jak bylo napsáno výše.

 

==== Operace spojení uzlů ====

Pokud chceme spojit dva uzly, musíme v zásadě provést 2 kroky:

# Přesuneme všechny klíče z pravého sourozence do levého, tento pravý podstrom následně zrušíme.

 

==== Operace přesunutí klíče ====

Přesunutí klíče z jednoho sourozence do druhého – uvažujme přesunutí klíče z pravého podstromu do levého, tak jak je to znázorněno na obrázku.

 

 

{{Stromy Inf}}

 

[[Kategorie:Stromy (datové struktury)]]