Matematické Fórum
Nevíte-li si rady s jakýmkoliv matematickým problémem, toto místo je pro vás jako dělané.
Nástěnka
❗22. 8. 2021 (L) Přecházíme zpět na doménu forum.matweb.cz!
❗04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
❗23.10.2013 (Jel.) Zkuste před zadáním dotazu použít některý z online-nástrojů, konzultovat použití můžete v sekci CAS.
Nejste přihlášen(a). Přihlásit
#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: 4246
- Š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