#1 03. 01. 2009 19:49
B+ strom
Mějme následující B+ strom:
Jak bude strom vypadat po vložení prvku 'YZ'?
- z posledního listu vytvořím 2 listy- v prvním z nich budou hodnoty 'UV' a 'VW', v posledním 'XY' a 'YZ'. Takto ale není splněna podmínka pro naplněnost vnitřích uzlů- můžu si proto rozštěpit libovolné 2 listové uzly na 3 nebo je nějaý algoritmus pro to, ktetý z nich vybrat?
Offline
#2 18. 01. 2009 03:39
- Kondr
- Veterán
- Místo: Linz, Österreich
- Příspěvky: 4247
- Škola: FI MU 2013
- Pozice: Vývojář, JKU
- Reputace: 38
Re: B+ strom
- z posledního listu vytvořím 2 listy- v prvním z nich budou hodnoty 'UV' a 'VW', v posledním 'XY' a 'YZ'
- potřebujme vložit XY o úroveň výš, tam se to nevleze, proto rozštěpíme kořen na dva vnitřní uzly -- jeden s hodnotami DE,MN, druhý s UV,XY.
- vyrobíme kořen a do něj dáme UV
Algoritmus obecně funguje tak, že se pokusíme hodnotu vložit do příslušného listu.
- když je místo, vložíme hodnotu
- když místo není, rozštěpíme uzel na poloviny a do vhodné půlky přidáme hodnotu. První klíč z druhé půlky pak vložíme o úroveň výš -- tam se opět buď vleze, nebo uzel rozštěpíme a první klíč druhé půlky pošleme zase o úroveň výš... takto vkládání "probublává" nahoru, pokud hodnota vybublá nad kořen, stane se novým kořenem.
BRKOS - matematický korespondenční seminář pro střední školy
Offline