Zadanie 5 b

• Zaimplementować słownik oparty na samoorganizującym się drzewie BST. Implementacja dynamiczna (nie tablicowa), każdy węzeł drzewa posiada referencje do lewego i prawego potomka oraz węzła rodzicielskiego.

• Drzewo powinno wykorzystywać strategię modyfikacji struktury drzewa po wyszukaniu węzła o określonej wartości klucza ST (Sleatora, Tarjana - odwiedzony lub wstawiony węzeł przemieszcza się o jeden lub dwa poziomy w kierunku korzenia).

• Słownik ma umożliwić przechowywanie danych w postaci element = {klucz}. Dostęp do słownika za pomocą funkcji:

• add( element)

• element del( klucz)

• element search( klucz)

• inorder() f-cja pomocnicza przechodząca drzewo w porządku inorder

• W głównej pętli programu nr 1 inicjalizujemy słownik, następnie dodajemy do niego minimalnie 100 tys. losowych elementów (po każdym wstawieniu dokonując modyfikacji struktury zgodnie ze wskazaną strategią), po czym wyprowadzamy na konsolę informację o strukturze drzewa, następnie przechodzimy je w porządku inorder wyprowadzając na konsolę wartości kluczy odwiedzanych kolejno węzłów.

• W programie nr 2 należy po wprowadzeniu z konsoli wartości klucza poszukiwanego węzła należy wyszukać ten węzeł i, o ile istnieje, usunąć z drzewa, po czym wyprowadzić na konsolę informacje o strukturze drzewa.