Drzewa czerwono-czarne

Zadanie AL8.1 Narysuj drzewo czerwono-czarne, które powstaje w wyniku wstawienia kolejno elementów 38, 31, 22, 8, 20, 5, 10, 9, 21, 27, 29, 25, 28 do początkowo pustego drzewa czerwono-czarnego. Przedstaw poszczególne etapy wstawiania i drzewa powstałe po wstawieniu każdego z elementów.

Zadanie AL8.2 Z powstałego drzewa w zadaniu AL8.1 usuń kolejno elementy 5, 38, 8, 10, 22, 20, 29, 31. Przedstaw poszczególne etapy usuwania i drzewa powstałe po usunięciu każdego z elementów.

Zadanie AL8.3 (4+1 pkt)

  1. Napisz program (czyli struktury danych i funkcje), który umożliwia wstawianie elementów do drzewa czerwono-czarnego. Testowanie (na małych danych, z jakąś wizualizacją drzewa) powinno obejmować wszystkie przypadki naprawiania drzewa. (4 pkt)

  2. Napisz i przetestuj funkcje, które wyznaczają maksymalną i minimalną głębokość liści w drzewie czerwono-czarnym oraz liczbę czerwonych węzłów. Testowanie: najpierw na małych danych, dla sprawdzenia, z wizualizacją drzewa, a potem na dużych danych (np. 1000 kluczy: 1, 2, 3, ... , 1000) (1 pkt)

Zadanie AL8.4 (nieobowiązkowe, dodatkowy 1 punkt) Do poprzedniego zadania dołącz funkcje, które umożliwią usuwanie elementu z drzewa czerwono-czarnego. Testowanie (na małych danych, z jakąś wizualizacją drzewa) powinno obejmować wszystkie przypadki naprawiania drzewa.

UWAGI