Algorytmy i struktury danych - klasówka 2
16.01.2009

1. [10 punktów]
a) [6 punktów] Drzewo AVL nazywamy wysmukłym jeśli zawiera minimalną liczbę wierzchołków wśród drzew AVL o wysokościach równych wysokości tego drzewa. Udowodnij, że wierzchołki każdego wysmukłego AVL-drzewa można pokolorować w taki sposób, żeby otrzymać drzewo czerwono-czarne.
b) [2 punkty] Podaj ciąg różnych liczb całkowitych, które po wstawieniu do początkowo pustego drzewa dadzą wysmukłe AVL-drzewo o wysokości 4. Kolejność liczb powinna być taka, żeby podczas całego procesu wstawiania wystąpiła dokładnie jedna pojedyncza rotacja.
b) [2 punkty] Podaj przykład 9-wierzchołkowego drzewa czerwono-czarnego, które nie jest AVL-drzewem.

2. [10 punktów] Niech G będzie grafem dwuspójnym wierzchołkowo o co najmniej 3 wierzchołkach i niech T będzie DFS-drzewem rozpinającym grafu G. Przez HG,T oznaczamy graf zorientowany otrzymany z G przez zorientowanie wszystkich krawędzi drzewowych w kierunku od ojca do syna, a krawędzi niedrzewowych w kierunku od potomka do przodka. Dla każdego wierzchołka v w grafie G definiujemy liczbę powrotną p(v) jako minimalną liczbę krawędzi niedrzewowych na ścieżce zorientowanej w HG,T, prowadzącej z v do korzenia drzewa T. Załóżmy, że graf G jest reprezentowany przez listy sąsiedztwa. Zaproponuj algorytm, który w czasie liniowym wyznacza pewne DFS-drzewo T w grafie G i oblicza dla każdego wierzchołka jego liczbę powrotną w HG,T. Uzasadnij poprawność swojego rozwiązania.