Zadanie 5 a

• 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 AMB (Allena, Munro, Bitnera - węzeł o wartości klucza będącej argumentem operacji wstawienia lub wyszukania jest na drodze kolejnych rotacji promowany do poziomu korzenia - operacja splay).

• 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.