ASD Ćwiczenia 8
Zadanie 1
Udowodnij, że wysokość drzewa AVL jest logarytmiczna względem jego rozmiaru.
Rozwiązanie
Zadanie 2
Oblicz, ile jest różnych drzew Fibonacciego o wysokości
.Rozwiązanie
Zadanie 3
Napisz pseudokod operacji Insert i Delete w drzewach AVL.
Zadanie 4
Chcemy, żeby nasz słownik udostępniał dodatkową operację Select(S,k), zwracającą k-ty najmniejszy element w S. Jak zmodyfikować drzewa AVL, żeby pozwalały wykonywac operację Select w czasie logarytmicznym?
Rozwiązanie
Zadanie 5
Udowodnij Lemat 1.
Rozwiązanie
Zadanie 6
Opisane tu operacje Insert i Delete dla B-drzew są dwuprzebiegowe: najpierw schodzimy od korzenia do liścia, a następnie wracamy w górę drzewa przywracając warunki równowagi. Zaprojektuj wymagające z grubsza o połowę odwołań do dysku mniej jednoprzebiegowe algorytmy wstawiania i usuwania kluczy z B-drzewa, w których przywracanie równowagi odbywa się od razu podczas marszu w dół drzewa.
Rozwiązanie
Zadanie 7
Chcemy rozszerzyć nasz zestaw operacji słownikowych o dwie dodatkowe:
Join(S1,S2) łączy dwa słowniki w jeden, przy założeniu, że wszystkie klucze w S1 są mniejsze niż wszystkie klucze w S2;
Split(S,x) dzieli słownik S na dwa słowniki: pierwszy złożony z elementów mniejszych bądź równych x i drugi zlożony z elementów większych od x.
Jak zrealizować te operacje
(a) dla B-drzew;
(b) dla drzew AVL
z kosztem proporcjonalnym do wysokości przetwarzanych drzew?
Rozwiązanie