Napisać funkcję która mając dane drzewo uporządkowane `d' i wartość `k' znajdzie element drzewa z minimalnym kluczem większym lub równym `k'. Funkcja ma zwracać wskaźnik zerowy jeśli takiego elementu nie ma. Uwaga: funkcja ma wykonywać co najwyżej `O(w)' operacji gdzie `w' jest wysokością drzewa.
Zakładamy że elementy drzewa i listy mają deklaracje jak niżej:
struct drzewo {
struct drzewo * lewe;
struct drzewo * prawe;
int klucz;
int wartosc;
};
struct lista {
struct lista * nastepny;
int klucz;
int wartosc;
};
Napisać funkcję która mając dane drzewo uporządkowane `d' i wartości `k1' i `k2' wyprodukuje listę tych kluczy (i odpowiadająch im wartości) które są większe lub równe `k1' i mniejsze lub równe `k2'. Innmi słowy ma to być lista kluczy (i odpowiadająch im wartości) z odcinka domkniętego od `k1' do `k2'. Uwaga: funkcja ma wykonywać co nawyżej `O(w+m)' operacji gdzie `w' jest wysokością drzewa zaś `m' jest ilością elementów wynikowej listy.
Kluczami w drzewie dwuwymiarowym są punkty (pary liczb całkowitych), zaś każdy węzeł ma cztery wskaźniki do potomków. Napisać funkcję która wstawi wierzchołek do drzewa uporządkowanego, zachowując porządek oraz drugą, która mając dane drzewo i prostokąt wyprodukuje listę punktów (kluczy) z tego drzewa zawartych w prostokącie. Uwaga: zakładamy że punkty są różne, ale powyższy opis nie mówi co zrobić jeśli mamy dwa punkty których jedna współrzędna jest równa zaś różnią się drugą współrzędną. Jakie wybory są tu rozsądne i jak to wpływa na oba algorytmy?
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 czterech potomków. Mamy dany kwadrat początkowy i 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: