ASD Ćwiczenia 8: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
m
m
 
Linia 43: Linia 43:
  
 
<div class="mw-collapsible-content" style="display:none">
 
<div class="mw-collapsible-content" style="display:none">
W każdym węźle przechowujemy atrybut 'rozmiar poddrzewa'. Taki atrybut można łatwo uaktualniac podczas rotacji i pozwala on na zlokalizowanie k-tego elementu przy pomocy jednego zejścia od korzenia w dół drzewa.
+
W każdym węźle przechowujemy atrybut 'rozmiar poddrzewa'. Taki atrybut można łatwo uaktualniać podczas rotacji i pozwala on na zlokalizowanie k-tego elementu przy pomocy jednego zejścia od korzenia w dół drzewa.
 
</div>
 
</div>
 
</div>
 
</div>
Linia 112: Linia 112:
 
W celu wykonania Split schodzimy do węzła z kluczem $x$, po czym wracamy do korzenia, wykonując Join osobno dla drzew po lewej i po prawej stronie ścieżki. Koszt Join jest w zasadzie proporcjonalny do ''różnicy wysokości'' łączonych drzew, więc łączny koszt wyjdzie proporcjonalny do wysokości $S$.
 
W celu wykonania Split schodzimy do węzła z kluczem $x$, po czym wracamy do korzenia, wykonując Join osobno dla drzew po lewej i po prawej stronie ścieżki. Koszt Join jest w zasadzie proporcjonalny do ''różnicy wysokości'' łączonych drzew, więc łączny koszt wyjdzie proporcjonalny do wysokości $S$.
  
(b) W przypadku AVL idea jest podobna jak poprzednio, ale pojawia się trochę problemów technicznych; szczegółowe rozwiązanie można znaleźć na przykład w książce D.Knutha "Sztuka programowania", WNT 2002, podrozdz. 6.2.3, str. 509.
+
(b) W przypadku AVL idea jest podobna jak poprzednio, ale pojawia się trochę problemów technicznych; szczegółowe rozwiązanie można znaleźć na przykład w książce D. Knutha "Sztuka programowania", WNT 2002, podrozdz. 6.2.3, str. 509.
 
</div>
 
</div>
 
</div>
 
</div>

Aktualna wersja na dzień 21:18, 3 gru 2006

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