ASD Ćwiczenia 8

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

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