Zagadnienia

• Struktura listy jedno- i dwukierunkowej
• Struktura drzewa poszukiwań binarnych (Binary Search Tree – BST)
• Tworzenie i usuwanie w/w struktur
• Wyszukiwanie elementu na liście/ w drzewie
• Usuwanie pojedynczych elementów listy/ drzewa
• Przeglądanie drzewa w porządku wzdłużnym (preorder), poprzecznym (inorder) i wstecznym (postorder)
• Definicja drzewa wyważonego i dokładnie wyważonego

Termin oddawania programów i wyników eksperymentów (+ wykresy): 11.04.2017
Termin dostarczenia sprawozdania (mailem pdf): 25.04.2017

Projekt

Wygeneruj n-elementowe ciągi parzystych liczb naturalnych bez powtórzeń (20 różnych wartości n, które mają być tak dobrane, żeby można było dokonać pomiaru czasu):

• rosnący,
• losowy,
• metodą połowienia binarnego.

Zaimplementuj dwie struktury danych:

• malejąco posortowaną listę dwukierunkową,
• drzewo BST.

Dla każdego ciągu wejściowego i strktury danych przerowadź następujące eksperymenty:

• tworzenie struktury przez wstawianie kolejnych elementów,
• usuwania x losowych wartości,
• dodawania x losowych wartości.

x jest losowym ciągiem nieparzystych liczb naturalnych bez powtórzeń. Wartość x, zależną od n, należy dobrać tak, aby można było dokonać pomiaru czasu np. x=n/100.

Dla przeprowadzonych eksperymentów wykonaj wykresy:

• zależności czasu od liczby elementów (3 wykresy z 3 ciągami * 2 strukturami danych),
• dla drzewa BST, zależności wysokości drzewa od liczby elementów (1 wykres z 3 ciągami).