Zadanie 1 (rotacje)
Danych jest \(n\) par liczb całkowitych, które się parami różnią na każdej pozycji. Pierwsze elementy para to klucze, drugie to priorytety.
- Wykaż, że istnieje dokładnie jedno drzewo binarne, które jest drzewem wyszukiwań binarnych ze względu na klucze i jednocześnie kopcem typu MAX ze względu na priorytety.
- Niech \( T \) będzie wyszukiwań drzewem binarnych ze względu na klucze. Opisz konstrukcję ciągu rotacji o długości \(O(n)\), które należy wykonać, żeby przekształcić drzewo \(T\) w drzewo BST, które będzie jednocześnie kopcem binarnym typu MAX ze względu na priorytety.
- Zaproponuj algorytm, który w czasie liniowym znajdzie ciąg rotacji, o którym mowa w poprzednim punkcie
.
Zadanie 2 (AVL-drzewa)
- Opisz sposób wykonywania operacji Delete dla AVL-drzew
- Do początkowo pustego AVL-drzewa wstawiamy kolejno elementy pewnej permutacji liczb \(1, 2, \ldots, n\). Dla \( n = 12 \) podaj permutacje dla których uzyskamy odpowiednio najniższe i najwyższe AVL-drzewo.
- Podaj przykład AVL-drzewa, w którym usunięcie klucza wymaga \(\Omega (\log n)\) rotacji.
Zadanie 3 (selekcja)
Zaproponuj wzbogacenie drzewa wyszukiwań binarnych o możliwość wyszukiwania \(k\)-tek klucza co do wielkości w drzewie. Czy wzbogacenie można przeprowadzić na AVL-drzewach.
Zadanie 4 (drzewa typu "splay")
Wykaż, że jeżeli budujemy drzewo typu "splay" poprzez wstawienie \(n\) kluczy do początkowo pustego drzewa, to możemy otrzymać drzewo binarne o wysokości liniowej.