© Květuše Sýkorová
• definice (
tree)
• autoři: Rudolf Bayer, Ed McCreight
– vyvážený strom řádu m ( • každý uzel nejméně
2∙
1)
a nejvýše m potomků
– s výjimkou kořene
© Květuše Sýkorová
• každý vnitřní uzel obsahuje o 1 méně klíčů než je počet potomků (ukazatelů) – od (
1) do (
1)
• všechny vnější uzly (listy) mají stejnou hloubku
• datová realizace – ADS (abstraktní datové struktury) Datová struktura není vhodná pro malý počet záznamů!
1
• použití: – celá nebo část struktury stromu je uložena v nějaké externí (vnější) sekundární paměti • např. pevný disk, magnetický disk (databáze) – velmi časté
– pro tento případ je struktura optimalizována • přístup do externí paměti je časově náročný © Květuše Sýkorová
– minimalizace počtu přístupů do této paměti
– uzel = stránka o m‐1 záznamech • viz: B tree animation
• příklad: – vyvážený B strom řádu 4 • každý uzel má nejméně 2 a nejvýše 4 potomky (ukazatele) • každý vnitřní uzel obsahuje nejméně 1 a nejvýše 3 záznamy
© Květuše Sýkorová
4
0
9
17
2
19 6
7
11
14
21
15
2
• vkládání: – nový klíč se vždy vkládá do listové stránky • ve stránce se klíče řadí podle velikosti
– přeplnění listové stránky • stránka se rozdělí na dvě nové stránky • prostřední klíč se přesune do rodičovské stránky – pokud rodičovská stránka neexistuje, tak se vytvoří © Květuše Sýkorová
– přeplnění rodičovské stránky • opakujeme předchozí postup dokud nedojde k zařazení nebo k vytvoření nového kořene
• Pole klíčů: 10, 4, 1, 5, 8, 7, 0, 2, 3 –
strom řádu 3 • každý uzel bude mít 2‐3 potomky (podstromy) – s výjimkou kořene
• každý vnitřní uzel bude mít nejméně 1 a nejvýše 2 záznamy
k2
© Květuše Sýkorová
k1
3
• Pole klíčů: 10, 4, 1, 5, 8, 7, 0, 2, 3
© Květuše Sýkorová
10
© Květuše Sýkorová
• Pole klíčů: 10, 4, 1, 5, 8, 7, 0, 2, 3
10
4
• Pole klíčů: 10, 4, 1, 5, 8, 7, 0, 2, 3
© Květuše Sýkorová
4
10 4
10
© Květuše Sýkorová
• Pole klíčů: 10, 4, 1, 5, 8, 7, 0, 2, 3
4
10
5
• Pole klíčů: 10, 4, 1, 5, 8, 7, 0, 2, 3
© Květuše Sýkorová
1
4
10 1
4
• Pole klíčů: 10, 4, 1, 5, 8, 7, 0, 2, 3
© Květuše Sýkorová
1
1
4
10
6
• Pole klíčů: 10, 4, 1, 5, 8, 7, 0, 2, 3
© Květuše Sýkorová
1
1
4
10
• Pole klíčů: 10, 4, 1, 5, 8, 7, 0, 2, 3 1
© Květuše Sýkorová
4
1
10
7
• Pole klíčů: 10, 4, 1, 5, 8, 7, 0, 2, 3 5
© Květuše Sýkorová
4
1
10 4
5
• Pole klíčů: 10, 4, 1, 5, 8, 7, 0, 2, 3 5
© Květuše Sýkorová
4
1
10 5
10
8
• Pole klíčů: 10, 4, 1, 5, 8, 7, 0, 2, 3 5
© Květuše Sýkorová
4
1
5
10
• Pole klíčů: 10, 4, 1, 5, 8, 7, 0, 2, 3 8
© Květuše Sýkorová
4
1
5
10 4
8
9
• Pole klíčů: 10, 4, 1, 5, 8, 7, 0, 2, 3 8
© Květuše Sýkorová
4
1
5 5
10 8
10
• Pole klíčů: 10, 4, 1, 5, 8, 7, 0, 2, 3 8
© Květuše Sýkorová
4
1
5
10
10
• Pole klíčů: 10, 4, 1, 5, 8, 7, 0, 2, 3 8
© Květuše Sýkorová
4
1
8
5
10
• Pole klíčů: 10, 4, 1, 5, 8, 7, 0, 2, 3 7
© Květuše Sýkorová
4
1
8
5 4
10 7
8
11
• Pole klíčů: 10, 4, 1, 5, 8, 7, 0, 2, 3 7
© Květuše Sýkorová
4
1
8
5
10 5
7
• Pole klíčů: 10, 4, 1, 5, 8, 7, 0, 2, 3
© Květuše Sýkorová
7
1
4
8
5
7
10
12
• Pole klíčů: 10, 4, 1, 5, 8, 7, 0, 2, 3
© Květuše Sýkorová
0
1
4
8
5
7
0
4
10
8
• Pole klíčů: 10, 4, 1, 5, 8, 7, 0, 2, 3
© Květuše Sýkorová
0
1
4
8
5
7 0
10
1
13
• Pole klíčů: 10, 4, 1, 5, 8, 7, 0, 2, 3
© Květuše Sýkorová
0
0
1
4
8
5
7
10
• Pole klíčů: 10, 4, 1, 5, 8, 7, 0, 2, 3
© Květuše Sýkorová
2
0
1
4
8
5
7
2
4
10
8
14
• Pole klíčů: 10, 4, 1, 5, 8, 7, 0, 2, 3
© Květuše Sýkorová
2
0
1
4
8
5
7
0
1
10
2
• Pole klíčů: 10, 4, 1, 5, 8, 7, 0, 2, 3
© Květuše Sýkorová
2
0
1
2
4
8
5
7
10
15
• Pole klíčů: 10, 4, 1, 5, 8, 7, 0, 2, 3 2
© Květuše Sýkorová
1
0
2
4
8
5
7
10
• Pole klíčů: 10, 4, 1, 5, 8, 7, 0, 2, 3 2
© Květuše Sýkorová
1
0
4
2
5
7
8
10
16
• Pole klíčů: 10, 4, 1, 5, 8, 7, 0, 2, 3 2 4
© Květuše Sýkorová
1
0
8
2
5
7
10
• Pole klíčů: 10, 4, 1, 5, 8, 7, 0, 2, 3 2 4
© Květuše Sýkorová
1
0
8
2
5
7
10
17
• Pole klíčů: 10, 4, 1, 5, 8, 7, 0, 2, 3 3 4
© Květuše Sýkorová
1
0
8
2
5 3
7
10
4
• Pole klíčů: 10, 4, 1, 5, 8, 7, 0, 2, 3 3 4
© Květuše Sýkorová
1
0
8
2
5 1
7
10
3
18
• Pole klíčů: 10, 4, 1, 5, 8, 7, 0, 2, 3 3 4
© Květuše Sýkorová
1
0
8
2
5 2
7
10
3
• Pole klíčů: 10, 4, 1, 5, 8, 7, 0, 2, 3 3 4
© Květuše Sýkorová
1
0
8
2
3
5
7
10
19
• Pole klíčů: 10, 4, 1, 5, 8, 7, 0, 2, 3 4
© Květuše Sýkorová
1
0
8
2
3
5
7
10
• rušení v listové stránce: – máme více jak
záznamů
• zrušíme záznam pouze v této listové stránce + posun
– máme právě
záznamů
© Květuše Sýkorová
• v sousední listové stránce je dostatek klíčů (více jak
)
– přesuneme záznam z rodičovské stránky do listové – přesuneme záznam ze sousední stránky do rodičovské
• v žádné sousední stránce není dostatek klíčů – spojíme dohromady záznamy v obou sousedních stránkách spolu s příslušným záznamem v rodičovské stránce
20
• rušení v rodičovské stránce: – máme více jak
záznamů
• ve stránce potomka je dostatek klíčů (více jak
)
– přesuneme záznam ze stránky potomka do rodičovské stránky
• ve stránce potomka není dostatek klíčů
© Květuše Sýkorová
– přesuneme záznamy ze stránky potomka do sousední stránky potomka
– máme pouze
záznamů
• ve stránce potomka je dostatek klíčů (více jak
)
– přesuneme záznam ze stránky potomka do rodičovské stránky
• ve stránce potomka není dostatek klíčů – přesuneme záznamy ze stránky potomka do sousední stránky potomka a řešíme problém o hladinu výše
• Pole klíčů: 10, 4, 1, 5, 8, 7, 0, 2, 3 – najdeme 2 4
© Květuše Sýkorová
1
0
8
2
3
5
v listové stránce je více jak
7
10
záznamů
21
• Pole klíčů: 10, 4, 1, 5, 8, 7, 0, 2, 3 – odstraníme 2 4
© Květuše Sýkorová
1
8
0
3
5
7
10
zrušíme záznam pouze v listové stránce
• Pole klíčů: 10, 4, 1, 5, 8, 7, 0, 2, 3 – odstraníme 2 4
© Květuše Sýkorová
1
0
8
3
5
7
10
posuneme ostatní záznamy v listové stránce
22
• Pole klíčů: 10, 4, 1, 5, 8, 7, 0, 2, 3 – najdeme 8 4
© Květuše Sýkorová
1
8
0
3
5
7
10
rušíme záznam v rodičovské stránce
• Pole klíčů: 10, 4, 1, 5, 8, 7, 0, 2, 3 – odstraníme 8 4
© Květuše Sýkorová
1
0
3
5
7
ve stránce potomka je dostatek klíčů (více jak
10 )
23
• Pole klíčů: 10, 4, 1, 5, 8, 7, 0, 2, 3 – odstraníme 8 4
© Květuše Sýkorová
1
0
7
3
5
10
přesuneme záznam ze stránky potomka do rodičovské stránky
• Pole klíčů: 10, 4, 1, 5, 8, 7, 0, 2, 3 – najdeme 1 4
© Květuše Sýkorová
1
0
7
3
5
10
rušíme záznam v rodičovské stránce
24
• Pole klíčů: 10, 4, 1, 5, 8, 7, 0, 2, 3 – odstraníme 1 4
© Květuše Sýkorová
7
0
3
5
10
přesuneme záznamy ze stránky potomka do sousední stránky potomka řešíme problém o hladinu výše
• Pole klíčů: 10, 4, 1, 5, 8, 7, 0, 2, 3 – odstraníme 1 4
© Květuše Sýkorová
7
0
3
5
10
přesuneme záznamy ze stránky potomka do sousední stránky potomka řešíme problém o hladinu výše
25
• Pole klíčů: 10, 4, 1, 5, 8, 7, 0, 2, 3 – odstraníme 1 4
© Květuše Sýkorová
7
0
3
5
10
přesuneme záznamy ze stránky potomka do sousední stránky potomka řešíme problém o hladinu výše
• Pole klíčů: 10, 4, 1, 5, 8, 7, 0, 2, 3 – odstraníme 1
© Květuše Sýkorová
4
0
3
5
7
10
přesuneme záznamy ze stránky potomka do sousední stránky potomka řešíme problém o hladinu výše
26
• Pole klíčů: 10, 4, 1, 5, 8, 7, 0, 2, 3 – odstraníme 1
© Květuše Sýkorová
4
0
5
10
)‐(m) strom řádu m:
• B(
– log
log 1
–1 –1 –1 – © Květuše Sýkorová
3
7
2 2
–1
počet uzlů
hloubka
počet záznamů
1
0
m‐1
m
1
m.(m‐1)
m2
2
m2.(m‐1)
:
:
:
mh
h
mh.(m‐1)
2 1
– •
⋯
1
⋯
∙ ∙
1
∙
1
1
27
