Ćwiczenia 8: drzewa wyszukiwań binarnych

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.