Metody Programowania - Lista 6

Zadanie 1

Napisać funkcję, która mając daną posortowaną tablicę liczb całkowitych zbuduje maksymalnie zrównoważone drzewo, którego kluczami są liczby z tej tablicy.

Zadanie 2

Zmodyfikować funkcję szukania elementu w drzewie uporządkowanym, tak by zwracała albo węzeł z równym kluczem (jeśli istnieje) albo, gdy klucza nie ma w drzewie to węzeł z najmniejszym kluczem większym od szukanego klucza. Jeśli szukany klucz jest większy od wszystkich kluczy w drzewie zwrócić listę pustą. Uwaga: funkcja ma wykonywać co najwyżej `O(w)' operacji gdzie `w' jest wysokością drzewa.

Zadanie 3

Węzły drzewa mają całkowitoliczbowe pola klucza i pole z wartością. Napisać funkcję, która mając dane drzewo utworzy listę par klucz, wartość. Zakładamy że drzewo jest uporządkowane względem wartości klucza, chcemy żeby klucze na liście wynikowej były uporządkowane. Podobnie, napisać funkcję, która mając mając daną listę utworzy drzewo którego węzły mają te same klucze i wartości. Nic nie zakładamy o porządku elementów listy, wynikowe drzewo ma być uporządkowane względem wartości klucza (łącznie te dwie funkcje mogą posortować listę).

Zadanie 4

Węzły drzewa dwuwymiarowego reprezentują kwadraty. Dany węzeł może być węzłem końcowym (liściem), albo dany kwadrat jest podzielony na cztery równe części i wtedy ten węzeł ma do czterech potomków. Początkowy kwadrat to kwadrat jednostkowy -- o wierzchołkach (0,0), (1,0), (0,1), (1,1). Mamy daną listę punktów. Chcemy żeby w kwadratch odpowiadających węzłom końcowym znajdował się co najwyżej jeden z zadanych punktów. Napisać funkcję (a właściwie trzy oddzielne funkcje) która:

mając dany punkt kwadratu początkowego i drzewo znajdzie węzeł końcowy taki że ten punkt należy do kwadratu związanego z tym węzłem
"wstawi" punkt do drzewa, tzn. znajdzie odpowiadający punktowi węzeł końcowy i jeśli trzeba podzieli ten węzeł
mając dany kwadrat początkowy i listę punktów zbuduje z niego drzewo

Naiwne rozwiązanie w każdym węźle przechowywałoby wierzchołki związanego z nim kwadratu -- jest to niepotrzebne

Zadanie 5

Zapoznać się z przykładem o drzewach AVL.

co trzeba w nim zmienić żeby węzły drzewa były reprezentowane przez wektory?
dodać do węzłów dodatkowe pole z danymi
zastąpić porównanie liczb przez dodatkową funkcję porównującą podawaną przez użytkownika w momencie tworzenia drzewa (tzn. inne funkcje mają ją odczytać z drzewa).