Cvičení 5
B+ stromy - animace
Vlastislav Dohnal

4.12.2012
V. Dohnal: Cvičení 5
Animace štěpení uzlů: list
nPředpokládejte n=3. Vkládáme hodnotu 6.
5
6
7
7
5
7
5
6
7
5
7
5
1
3
6
Dělíme napůl podle klíčů. Pokud nelze přesně napůl, pak levá polovina je větší.
Vyhledání
správného listu
Vložení nové
hodnoty do listu
Vytvoření nového listu
pro pravou polovinu
Levá polovina do
starého uzlu
Připojení listu
do rodiče – vkládáme
dvojici <první klíč nového uzlu;
ukazatel na nový uzel>
5
7
5
1
3
Původní strom
Strom po vložení 6

4.12.2012
V. Dohnal: Cvičení 5
Animace štěpení uzlů: nelistový uzel
nPředpokládejte n=3. Vkládáme hodnotu 4.
5
7
1
3
5
6
7
4
4
4
5
6
7
5
7
4
Dělíme napůl podle ukazatelů. Pokud nelze přesně, pak levá polovina je větší.
Levá polovina jde do původního uzlu. Pravá polovina (jeho první klíč přeskočíme) jde do nového
uzlu.
Vyhledání
správného listu
Připojení listu
do rodiče – vkládáme
dvojici <první klíč nového uzlu;
ukazatel na nový uzel>
Vložení do listu a
jeho rozštěpení
Rozštěpení vnitřního uzlu (zde kořene)
a vytvoření nového kořene
4
7
Do rodiče přidáme přeskočený
klíč a ukazatel na nový uzel
5
5
Původní strom
Strom po vložení 4
5
6
7
5
7
1
3