B-drzewa

Zadanie AL11.1 Zilustruj wyniki wstawiania do początkowego pustego B-drzewa stopnia 3 kolejno kluczy F, S, Q, K, C, L, H, T, V, W, M, R, N, P, A, B, X, Y, D, Z, E, G, J.

Zadanie AL11.2 Narysuj kolejne B-drzewa powstające w wyniku usuwania z poniższego B-drzewa kolejno kluczy P, C, V, S oraz O.

Zadanie AL11.4 ((2+3)+1* pkt.)

• (a) Zaimplementuj i przetestuj funkcję szukającą elementu w B-drzewie. (2 pkt.)

• (b) Zaimplementuj i przetestuj funkcję wstawiającą element do B-drzewa. (3 pkt.)

• (*c nieobowiązkowe) Zaimplementuj i przetestuj funkcję usuwającą element z B-drzewa. (1 pkt.)

UWAGI

• Dla uproszczenia przyjmujemy, że klucze są liczbami całkowitymi i ignorujemy ewentualne inne informacje przechowywane z kluczami.

• Węzły drzewa powinny być przechowywane w pliku dyskowym i odczytywane/zapisywane pojedynczo, w miarę potrzeby, jak to zwykle się dzieje w B-drzewach. W pliku budujB.c znajduje się przykładowy program zawierający funkcję, która buduje B-drzewo, oraz funkcję, która wyświetla drzewo w następującym stylu.

  B-drzewo

       
     D G 
    / | \
  AB EF HIJ 
    
  

  będzie wyświetlone jako

    
   HIJ
  G 
   EF
  D
   AB
  
  

  Można też zobaczyć tam (i skorzystać) przykład zapisu i odczytu węzłów drzewa do pliku.

• Ważnym elementem zadania jest testowanie poprawności zaimplementowanych procedur. Zatem działanie programu, zwłaszcza usuwanie, należy zademonstrować na kilku przykładach odpowiadających różnym przypadkom algorytmu.