Węzły drzewa mają całkowitoliczbowe pola `klucz' i `wartosc'. Drzewo jest uporządkowane względem wartości pola `klucz'. Napisać funkcję która:
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.
Rozdzielić zadane drzewo binarne którego elementy mają całkowite pola `klucz' i `licznik' (uporządkowane względem wartości klucza) na dwa zależnie od tego czy licznik jest większy od zadanej wartości czy nie. Utworzone drzewa mają być uporządkowane względem wartości klucza.
Węzły drzewa mają całkowitoliczbowe pola `klucz' i `wartosc'. Podobnie węzły listy mają całkowitoliczbowe pola `klucz' i `wartosc'. Napisać funkcję, która mając dane drzewo utworzy listę której węzły mają te same wartości `klucz' i `wartosc'. 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 wartości `klucz' i `wartosc'. 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ę).
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. Drzewo porządkujemy "po składowych" (mamy cztery możliwe wyniki porównania!). Dokładniej, węzłowi drzewa opowiada punkt płaszczyzny, przy pomocy prostych równoległych do osi układu wspórzędnych i przechodzących przez nasz punkt dzielimy płaszczyznę na cztery ćwiartki. Z każdym wskaźnikiem do potomków jest związana jedna ćwiartka tzn. wszyscy potomkowie danego węzła których osiągamy przez dany wskaźnik należą do jednej ćwiartki. 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:
Niech `a[n]' będzie ilością elementów maksymalnie asymetrycznego drzewa zrównoważonego względem wysokości wysokości `n' (takie drzewa nazywamy drzewami Fibonacciego). Zachodzi równość `a[n+2] = a[n+1] + a[n] + 1'. Pokazać że dla `q1 = (1+sqrt(5))/2', `q1 = (1-sqrt(5))/2' (`q1' i `q2' sa pierwiastkami równania `x*x-x-1=0', mamy `a[n] = ((((5+3*sqrt(5))/2)*q1^5+((5-3*sqrt(5))/2)*p1^5)/5-1' gdzie we wzorze `^' oznacza potęgowanie. Uwaga: przyjmuję tu (zgodnie z zadaniem 1) że drzewo składające się z samego korzenia na wysokość 1.