Algorytmy i Struktury Danych

Lista 8

B-DRZEWA

Zadanie 1.

Z własności B-drzew wiemy, że:

• każdy węzeł różny od korzenia musi mieć co najmniej t-1 kluczy, stąd minimalna ilość synów takiego

węzła jest równa t;

• każdy węzeł może zawierać co najwyżej 2t-1 kluczy, stąd maksymalna ilość synów takiego węzła

jest równa 2t.

Dopuszczając sytuacje, gdy t=1 mamy w każdym węźle [0,1] kluczy oraz [1,2] synów. Powstałe drzewo
byłoby podobne do drzew binarnych, które nie są optymalne dla obsługi urządzeń dyskowych.

Zadanie 3.

W każdym węźle mamy dla minimalnego stopnia t, maksymalnie 2t-1 kluczy. Stąd:

h

X

i=0

(2t − 1) · (2t)

i

Rozwijając tę sumę otrzymujemy:

h

X

i=0

(2t − 1) · (2t)

i

= (2t − 1) + (2t − 1)(2t) + ... + (2t − 1)(2t)

h−1

+ (2t − 1)(2t)

h

=

= 2t − 1 + 4t

2

− 2t + ... + 2

h

t

h

− 2

h−1

t

h−1

+ 2

h+1

t

h+1

− 2

h

t

h

= (2t)

h+1

− 1

Łatwo widać stąd, że wszystkie środkowe wyrazy się skracają.

Zadanie 4.

Drzewo czerwono-czarne jest zrównoważonym drzewem binarnym o wysokości O(lg n). Po

wchłonięciu przez czarne węzły ich czerwonych dzieci powstanie B-drzewo o minimalnym stopniu t=2
tzw. 2-3-4 drzewo. Przy założeniu, że drzewo czerwono-czarne jest pełnym drzewem binarnym oraz jest
pokolorowane poziomami na przemian otrzymamy pełne B-drzewo o minimalnym stopniu t=2.

Zadanie 7.

Wywołujemy poniższą procedure z parametrem root[T], który domyślnie jest już wczytany.

1

B−Tree−Min ( x )

2

r=x

3

i f

l e a f [ r ]

4

t h e n

r e t u r n key_1 [ r ]

5

e l s e

6

Disk−Read [ c_1 [ r ] ]

7

r e t u r n B−Tree−Min ( c_1 [ r ] )

Zadanie 8.

W tym zadaniu użyjemy gotowego rozwiązania B-Tree-Search.

1

B−Tree−P r e d e c e s s o r (T ,

x )

2

( r ,

i ) = B−Tree−S e a r c h ( r o o t [ T ] ,

x )

3

i f

i >= 2

4

t h e n

r e t u r n

( r ,

i −1)

5

e l s e

6

( p ,

j ) = AN−P r e d e c e s s o r ( r o o t [ T ] ,

x )

7

i f

l e a f [ r ]

and

j =1

8

t h e n

r e t u r n NIL

9

e l s e

10

r e t u r n

( p ,

j −1)

1

AN−P r e d e c e s s o r ( k ,

x )

2

r = k

3

i f

key_1 [ r ] = x

4

t h e n Disk−Read ( c_1 [ r ] )

5

r e t u r n

( c_1 [ r ] ,

n [ c_1 [ r ] ] + 1 )

6

e l s e

7

w h i l e

i <= n [ r ]+1

8

Disk−Read ( c_i [ r ] )

9

i f

key_1 [ c_i [ r ] ] = x

10

t h e n

r e t u r n

( r ,

i )

11

e l s e

12

w h i l e

i <= n [ r ]

and x > key_i [ r ]

13

i=i +1

14

r e t u r n AN−P r e d e c e s s o r ( c_i [ r ] ,

x )

1