ASD Ćwiczenia 9

Ćwiczenie [Dowód lematu 1]

Udowodnij lemat 1

Rozwiązanie

Indukcja po $k$.

Ćwiczenie [Kolejka dwumianowa 1]

Do początkowo pustej kolejki dwumianowej wstawiamy klucze 1, 2, ..., 1000. Czy teraz w jej skład wchodzi drzewo $B_5$?

Rozwiązanie

Tak, bo $1000=2^9+2^8+2^7+2^6+{\mathbf{𝟐}}^{\mathbf{𝟓}}+2^3$.

Ćwiczenie [Przykładowy ciąg operacji]

Narysuj
(a) kolejkę dwumianową
(b) kopiec Fibonacciego
otrzymane w wyniku wstawienia do początkowo pustej struktury kolejno kluczy 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, wykonaniu Delmin, zmniejszeniu klucza 7 do wartości 1 i usunięciu klucza 8.

Rozwiązanie

(a) (b)

Ćwiczenie [Reprezentacja]

Zaproponuj reprezentację komputerową kolejki dwumianowej i kopca Fibonacciego, która umożliwia realizację wszystkich operacji z podanymi kosztami.

Rozwiązanie

Kolejka dwumianowa: W każdym węźle pola: klucz, ojciec, lewy syn, prawy brat; wskaźniki do brata w korzeniach wykorzystywane do utrzymywania listy drzew; listy braci (i korzeni) cykliczne.

Kopiec Fibonacciego: Podobnie, ale listy braci dwukierunkowe oraz dodatkowe pole z flagą logiczną, mówiącą czy węzeł stracił syna od czasu ostatniego odcięcia. Dostęp do listy drzew przez wskaźnik do korzenia z najmniejszym kluczem.

Ćwiczenie [Meld i DelMin]

Napisz pseudokod operacji Meld i DelMin na kolejkach dwumianowych.

Rozwiązanie

Zobacz [CLRS], podrozdz. 19.2 (konieczne są drobne modyfikacje).

Ćwiczenie [Koszty operacji]

Jakie są pesymistyczne (nie zamortyzowane) koszty poszczególnych operacji na kopcach Fibonacciego?

Rozwiązanie

MakePQ: 1

Insert: 1

FindMin: 1

DelMin n

DecreaseKey n

Delete n

Meld 1

Ćwiczenie [Pseudokod]

Napisz pseudokod operacji DelMin i DecreaseKey na kopcach Fibonacciego.

Rozwiązanie

Zobacz [CLRS], podrozdz. 20.2 i 20.3.

Ćwiczenie [Zaznaczanie węzłów]

Węzeł 7 nie został zaznaczony w ostatniej fazie operacji DecreaseKey w animacji z wykładu, pomimo że właśnie stracił jednego syna. Powodem jest to, że podczas wykonywania DecreaseKey nie ma potrzeby zaznaczać korzeni (zastanów się, dlaczego!). Jednak jego sąsiad 18 jest zaznaczony. Jak mogło do tego dojść?

Rozwiązanie

Węzeł 18 został zaznaczony, kiedy jeszcze nie był korzeniem, podczas wcześniejszej operacji DecreaseKey lub Delete, a potem stał sie korzeniem w wyniku operacji DelMin.

Ćwiczenie [Wysokość drzewa]

Czy wysokość drzewa w $n$-wierzchołkowym kopcu Fibonacciego jest $O(\lg n)$?

Rozwiązanie

Nie. Nietrudno podać przykład ciągu operacji, który prowadzi do powstania drzewa-linii.

Ćwiczenie [Modyfikacja kopca Fibonacciego]

Czy możliwa jest taka modyfikacja kopca Fibonacciego, żeby zarówno operacja Insert, jak i DelMin miały koszt zamortyzowany $o(\log n)$?

Rozwiązanie

Nie, bo wtedy można by użyć takiej struktury danych do posortowania $n$ elementów w czasie $o(n\log n)$.