Drzewa lewicowe to ciekawa implementacja złączalnych kolejek priorytetowych.
Kolejki priorytetowe to struktury przechowujące dane obdarzone priorytetami, umożliwiające łatwy dostęp do elementu o najwyższym priorytecie.
(Tradycyjnie, im mniejsza liczba reprezentująca priorytet, tym wyższy priorytet. ;-)
Struktury te dostarczają następujących operacji:
Oczywiście po usunięciu elementu o najwyższym priorytecie, drugi w kolejności staje się tym najwyższym itd.
Kolejki złączalne umożliwiają dodatkowo łączenie dwóch kolejek w jedną.
Kolejki priorytetowe implementuje się zwykle za pomocą tzw. kopców, czyli struktur drzewiastych, które
spełniają tzw. warunek kopca, mówiący, że priorytet elementu zawartego w korzeniu każdego poddrzewa
jest mniejszy lub równy niż każdego innego elementu w tym poddrzewie.
Drzewa lewicowe to kopce binarne (czyli każdy węzeł może mieć 0, 1 lub dwóch potomków)
spełniające, oprócz warunku kopca, tzw. warunek lewicowości.
Warunek lewicowości mówi, że dla każdego węzła skrajnie prawa ścieżka zaczynająca się w danym
węźle jest najkrótszą ścieżką od tego węzła do liścia.
Dzięki temu w każdym drzewie lewicowym, tzw. prawa wysokość, czyli długość skrajnej prawej
ścieżki od korzenia do liścia, jest co najwyżej logarytmicznej wielkości, w porównaniu z liczbą elementów drzewa.
Dodatkowo, aby umożliwić efektywne wykonywanie operacji na drzewie, w każdym węźle przechowywana
jest prawa wysokość poddrzewa zaczepionego w tym węźle.
Najważniejszą operacją na drzewach lewicowych jest ich łączenie.
Pozostałe operacje wykonuje się bardzo prosto:
Łączenie drzew lewicowych też nie jest trudne.
Aby połączyć dwa niepuste drzewa lewicowe, ustawiamy jako pierwsze (\(d_1\)) to, które ma mniejszy
element w korzeniu, a jako drugie (\(d_2\)) to, które ma większy.
W korzeniu wynikowego drzewa na pewno będzie więc korzeń \(d_1\).
Teraz rekurencyjnie łączymy prawe poddrzewo \(d_1\) oraz całe drzewo \(d_2\), w wyniku dostając drzewo \(d_3\).
Jako wynik całej operacji łączenia \(d_1\) i \(d_2\) zwracamy drzewo \(d_4\), które wygląda następująco:
Korzeń \(d_4\) jest taki sam, jak korzeń \(d_1\).
Jedno z poddrzew \(d_4\) to lewe poddrzewo \(d_1\), a drugie to drzewo \(d_3\).
Przy tym prawym poddrzewem \(d_4\) zostaje to z nich, które ma mniejszą prawą wysokość.
Dzięki temu \(d_4\) pozostaje drzewem lewicowym.
Oczywiście przy konstrukcji drzewa \(d_4\) należy pamiętać o odpowiednim ustawieniu prawej wysokości.
Rysunkową wersję łączenia drzew lewicowych można zobaczyć np. tu:
http://www.cise.ufl.edu/~sahni/cop5536/sliddes/lec114.pdf.
W naszym zadaniu dla uproszczenia zakładamy, że dane składają się z samych priorytetów.
Używając drzew lewicowych zaimplementuj złączalną kolejkę priorytetową z następującymi operacjami:
type 'a queue
(** Typ złączalnej kolejki priorytetowej *)
val empty : 'a queue
(** Pusta kolejka priorytetowa *)
val add : 'a -> 'a queue -> 'a queue
(** [add e q] zwraca kolejkę powstałą z dołączenia elementu [e] do kolejki [q] *)
exception Empty
(** Wyjątek podnoszony przez [delete_min] gdy kolejka jest pusta *)
val delete_min : 'a queue -> 'a * 'a queue
(** Dla niepustej kolejki [q], [delete_min q] zwraca parę [(e,q')] gdzie [e]
jest elementem minimalnym kolejki [q] a [q'] to [q] bez elementu [e].
Jeśli [q] jest puste podnosi wyjątek [Empty]. *)
val join : 'a queue -> 'a queue -> 'a queue
(** [join q1 q2] zwraca złączenie kolejek [q1] i [q2] *)
val is_empty : 'a queue -> bool
(** Zwraca [true] jeśli dana kolejka jest pusta. W przeciwnym razie [false] *)
(specyfikacja ta znajduje się również w pliku leftist.mli)
Termin oddania zadania ustala prowadzący — 2 tygodnie od ogłoszenia.
| Załącznik | Wielkość |
|---|---|
| wpf-1-leftist.mli | 801 bajtów |