Informatyka MIMUW

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.