2. Klasówka 1998/99#
Zadanie 1#
Udowodnij, że dla każdej liczby naturalnej \(k\) istnieje drzewo czerwono-czarne, w którym różnica w wysokościach poddrzew korzenia jest większa od \(k\).
Zadanie 2#
Zaprojektuj strukturę danych umożliwiającą efektywne wykonywanie na dynamicznym, skończonym zbiorze \(S\) trójek liczb naturalnych \((k, l, m)\) następujących operacji:
\(Utworz(S)\):: utwórz początkowy zbiór;
\(Dodaj(S, (k, l, m))\):: \(S := S \cup \{(k, l, m)\}\);
\(Usun(S, (k, l, m))\):: \(S := S \setminus \{(k, l, m)\}\);
\(Znajdz(S, (k, l, m))\):: sprawdź czy \((k, l, m)\) jest w \(S\), a jeśli tak, to zwróć wskaźnik do miejsca wystąpienia \((k, l, m)\) w strukturze;
\(Licz(S, (k, l, m))\):: zwraca liczbę \(|(m : (k, l, m) \in S|\).
Zadanie 3#
Niech \(S\) będzie dynamicznym zbiorem domkniętych przedziałów o końcach całkowitych ze zbioru \(\{1, 2, \cdots, n\}\). Zaprojektuj strukturę danych umożliwiającą wykonywanie na zbiorze \(S\) następujących operacji:
\(Utworz(S)\):: utwórz początkowy zbiór i zainicjuj strukturę;
\(Dodaj(S, (l, p))\):: \(S := S \cup \{(l, p)\}\);
\(Miara(S)\):: zwróć miarę teoriomnogościowej sumy wszystkich odcinków ze zbioru \(S\).
Uwaga: W kosztach operacji nie uwzględniamy kosztów przydzielania i zwalniania pamięci.
Zadanie 4#
Do początkowo pustego drzewa BST wstawiono kolejno liczby \(1, 10, 2, 9, 3, 8, 4, 7, 5, 6\). Jak wyglądają końcowe drzewa, gdy drzewo BST jest:
AVL-drzewem,
drzewem czerwono-czarnym,
2-3-4 drzewem.