Zadanie 2
Zaimplementować słownik oparty na liście z przeskokami (ang. skip list). Implementacja dynamiczna, wykorzystująca strażników (stałe elementy: najmniejszy i największy). Maksymalna liczba poziomów kolejki wynosi 10 (poziom 0 kompletny, poziom 9 najrzadszy). Prawdopodobieństwo pojawienia się nowo dodanego elementu na kolejnym poziomie pod warunkiem występowania na poziomie aktualnym wynosi 0,25.
Słownik ma umożliwić przechowywanie danych w postaci element = {klucz}. Jako typ danych dla klucza przyjąć integer. Dostęp do słownika za pomocą funkcji:
add(klucz)
element del(klucz)
element search(klucz)
show(level) f-cja pomocnicza - wyświetlenie elementów na wybranym poziomie
count() f-cja pomocnicza - wyświetlenie liczby elementów na wszystkich poziomach od 0 do 9
Zwrócić uwagę na poprawne i efektywne wyszukiwanie miejsca na nowo wstawiany element w funkcji add.
W głównej pętli programu inicjalizujemy słownik, następnie dodajemy do niego minimalnie 10 tys losowych elementów, po czym wyświetlamy zawartość poziomu 8 i 9. Jaka powinna być teoretycznie liczba wyświetlonych elementów na tych poziomach?