2. Klasówka 2011/12#
Zadanie 1#
Liściem w drzewie z korzeniem nazywamy każdy węzeł bez następników (synów). Niech \(T\) będzie drzewem wyszukiwań binarnych powstającym przez wstawienie, do początkowo pustego drzewa, kolejno \(n\) parami różnych kluczy \(k_1, k_2, \cdots, k_n\). W dalszym ciągu klucze utożsamiamy z zawierającymi je węzłami.
Zaproponuj liniowy algorytm, który dla danych: \(n\), ciągu kluczy \(k_1, k_2, \cdots, k_n\) i indeksu \(j\), \(1 \le j \le n\), sprawdzi, czy węzeł \(k_j\) jest liściem w \(T\).
Załóżmy, że ciąg \(k_1, k_2, \cdots, k_n\) jest permutacją liczb \(1, 2, \cdots, n\). Zaproponuj algorytm, który w czasie \(O(n)\) wyznaczy wszystkie liście w drzewie \(T\).
Udowodnij, że jeżeli AVL-drzewa usuniemy wszystkie liście, to otrzymane drzewo będzie nadal AVL-drzewem.
Ile wynosi minimalna liczba liści w AVL-drzewie o wysokości \(2012\)?
Załóżmy, że ciąg \(k_1, k_2, \cdots, k_n\) jest permutacją liczb \(1, 2, \cdots, n\) i wiemy, że po wstawieniu do początkowo pustego drzewa wyszukiwań binarnych kolejno kluczy \(k_i\), \(i = 1, 2, \cdots, n\), otrzymane drzewo \(T\) będzie AVL-drzewem (nie wykonujemy żadnych operacji równoważenia). Zaproponuj algorytm, który w czasie liniowym zbuduje drzewo \(T\), tzn. dla każdego węzła (klucza) określi jego lewego i prawego syna.
Zadanie 2#
Zaproponuj efektywną strukturę danych dla skończonego ciągu liczbowego \(\alpha\) o długości \(n\), umożliwiającą efektywne wykonywanie on-line następujących operacji:
Rosnący:: ile wynosi długość najdłuższego podciągu rosnącego złożonego z kolejnych elementów ciągu \(\alpha\).
Zmień\((i, \Delta)\):: do \(i\)-tego elementu ciągu dodaj \(\Delta\) (to może być liczba ujemna).
Pokaż w jaki sposób efektywnie zainicjować zaproponowaną strukturę danych dla początkowego ciągu \(\alpha\).
Zadanie 3 (bonus za 7 pkt)#
Uwaga! zadanie wycofane z kolokwium - nie da się go rozwiązać w oczekiwanym czasie, korzystając tylko z materiału AiSD
Dane jest \(n\)-wierzchołkowe drzewo z korzeniem \(T\), z wagami na krawędziach (liczby całkowite). Dla każdego wierzchołka \(v\) różnego od korzenia dane są ojciec \(p[v]\) w drzewie i waga \(w[v]\) krawędzi \(v-p[v]\). Przyjmujemy też, że wierzchołki są ponumerowane w porządku „preorder” i utożsamiamy je z tymi numerami - \(v\) oznacza zarówno wierzchołek, jak i jego numer. Zaproponuj algorytm, który w czasie \(O(n+k)\) udzieli odpowiedzi na \(k\) z góry zadanych zapytań postaci:
\(Max(u,v)\):: ile wynosi waga najcięższej krawędzi na ścieżce z \(u\) do \(v\)?
przy czym wiemy, że w każdym zapytaniu \(v\) jest przodkiem u w drzewie.