| « poprzedni punkt | następny punkt » |
Zaproponuj algorytm wyliczania wag dla danego drzewa
binarnego. Jaki jest koszt Tego algorytmu?
(Wygodnie jest przyjąć, że h(null) = -1 i zastosować jakiś algorytm
rekurencyjnego przeglądania drzewa.)
Dany jest ciąg uporządkowany rosnąco. Jaki jest koszt
budowy wyważonego drzewa binarnych poszukiwań następującą metodą?
(a) umieszczamy element środkowy ciągu w korzeniu budowanego drzewa, (b) lewe
poddrzewo budujemy z elementów mniejszych od środkowego, a prawe poddrzewo z
elementów większych od środkowego, stosując tę samą metodę.
Dana są podzbiory A i B zbioru liczb rzeczywistych
R, reprezentowane przez drzewa AVL, |A| = n i |B|=m. Napisać program
znajdujący przecięcie zbiorów A i B w postaci drzewa AVL. Przeanalizuj koszt
czasowy i pamięciowy zaproponowanego algorytmu.
Podaj przykład drzewa AVL, dla którego usunięcie jednego elementu spowoduje wykonanie rzędu lg n rotacji.
Napisz algorytm wyznaczania wysokości drzewa,
którego każdy wierzchołek ma co najwyżej n synów. Oszacuj koszt tego algorytmu
i uzasadnij jego poprawność.
Zaproponuj algorytm rozwiązywania (a) problemu min-max oraz (b) problemu wyszukiwania elementu k-tego co do wielkości z użyciem drzew AVL. Porównaj koszt znalezionych algorytmów z algorytmami poznanymi w wykładzie trzecim.
Dane są dwa ciągi uporządkowane. Oszacuj koszt scalania tych ciągów, jeśli zastosowano następującą metodę: (a) dla dłuższego z ciągów zbudowano drzewo AVL (metodą z zdania 2), (b) kolejno włożono do tego drzewa elementy drugiego ciągu, a następnie (c) odczytano wierzchołki otrzymanego drzewa w porządku inorder.
| « poprzedni punkt | następny punkt » |