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): 23.04.2018
Termin dostarczenia sprawozdania (mailem pdf): 30.04.2018

Projekt

Wygeneruj n-elementowe ciągi nieparzystych 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,
• malejący,
• losowy,
• metodą połowienia binarnego.

Zaimplementuj dwie struktury danych:

• rosnąco posortowaną listę jednokierunkową,
• 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 parzystych 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,
• dla drzewa BST, zależności wysokości drzewa od liczby elementów.