Algorytmy i struktury danych · Laboratorium 4

Drzewa

Celem laboratorium jest implementacja drzewa binarnego oraz drzewa wyszukiwań binarnych z jawnymi niezmiennikami, analizą kosztu operacji i testami przypadków brzegowych.

1. Model drzewa binarnego

Węzeł przechowuje wartość oraz odwołania do lewego i prawego poddrzewa. Puste poddrzewo reprezentuj wartością None. Oddziel strukturę węzła od operacji udostępnianych przez drzewo.

Zadanie 1. Zaimplementuj obliczanie liczby węzłów, wysokości drzewa oraz trzy przejścia w głąb: preorder, inorder i postorder. Sprawdź drzewo puste, pojedynczy węzeł oraz drzewo silnie niezrównoważone.

2. Drzewo wyszukiwań binarnych

Przyjmij niezmiennik: wszystkie klucze w lewym poddrzewie są mniejsze od klucza węzła, a w prawym większe. Jawnie określ politykę dla duplikatów.

search(key)
insert(key)
minimum()
maximum()
Zadanie 2. Zaimplementuj wyszukiwanie i wstawianie. Po każdej serii operacji zweryfikuj, że przejście inorder zwraca klucze w porządku rosnącym.

3. Usuwanie węzłów

Usuwanie wymaga rozpatrzenia trzech przypadków: liścia, węzła z jednym dzieckiem oraz węzła z dwojgiem dzieci. W trzecim przypadku można użyć następnika inorder, czyli najmniejszego elementu prawego poddrzewa.

Zadanie 3. Zaimplementuj usuwanie dla wszystkich trzech przypadków. Przygotuj osobny test dla usuwania korzenia w każdym z nich.

4. Złożoność a wysokość

Operacja BSTDrzewo zrównoważonePrzypadek skrajny
wyszukiwanieΘ(log n)Θ(n)
wstawianieΘ(log n)Θ(n)
usuwanieΘ(log n)Θ(n)
Zadanie 4. Wstaw kolejno liczby 1..n oraz tę samą liczbę elementów w losowej kolejności. Porównaj wysokość obu drzew i liczbę porównań podczas wyszukiwania.

5. Walidacja niezmiennika

Zadanie 5. Napisz funkcję walidującą BST bez sortowania wszystkich elementów. Przekazuj dopuszczalny przedział kluczy do kolejnych poddrzew i wykryj celowo wprowadzony błąd struktury.

6. Sprawozdanie

  1. Przyjęta reprezentacja i polityka duplikatów.
  2. Implementacja przejść, wyszukiwania, wstawiania i usuwania.
  3. Testy trzech przypadków usuwania oraz przypadków brzegowych.
  4. Porównanie wysokości i kosztu operacji dla różnych kolejności danych.
  5. Opis walidacji niezmiennika BST.
  6. Opis użycia AI albo informacja, że AI nie użyto.

Przykład opisu AI: „Użyłem modelu językowego do wygenerowania propozycji przypadków testowych dla usuwania w BST. Implementację i oczekiwane wyniki przygotowałem samodzielnie, a przypadki zweryfikowałem przez kontrolę inorder i walidację przedziałów.”

Źródła

  1. T. H. Cormen, C. E. Leiserson, R. L. Rivest i C. Stein, Introduction to Algorithms, wyd. 4, MIT Press, 2022.
  2. A. Levitin, Introduction to the Design and Analysis of Algorithms, wyd. 3, Pearson, 2022.