Drzewa dynamiczne odgrywają ważną rolę w rozwiązywaniu problemów, takich jak przepływy sieciowe, wykresy dynamiczne, problemy kombinatoryczne („Drzewa dynamiczne w praktyce” Tarjana i Wernecka) oraz ostatnio łączone słowniki („Prosty słownik łączący” Adama Karczmarza),
Przez drzewa dynamiczne odwołuję się do definicji podanej w dokumencie Sleator & Tarjan zatytułowanym „Struktura danych dla drzew dynamicznych” z 1983 r. Od tego czasu opublikowano niewiele wysiłków w dziedzinie badań nad programowaniem funkcjonalnym.
- Edward Kmett zaimplementował wersję drzewek ST głównie jako tłumaczenie odpowiednika C ++, patrz Drzewa cięte linkami .
- Chris Okasaki napisał ograniczoną implementację drzew Splay w swojej znanej książce „Czysto funkcjonalne struktury danych”.
- Ralf Hinze i Ross Paterson wprowadzili funkcjonalną strukturę danych zwaną 2-3 palcami, ale z nieco innym celem niż pierwotna definicja dynamicznych drzew.
Implementacja (i być może wydajność) dynamicznych drzew jest podzielona według trzech podejść:
- Linearyzacja, w której drzewa ET (Euler tour) odgrywają wielką rolę. Nie znaleziono czysto funkcjonalnego badania.
- Rozkład ścieżek, w którym drzewa ST są flagowym produktem, właśnie znalazł wersję Kmetta.
- Skurcz drzewa, w którym gracze zajmują drzewa najlepsze, drzewa topologiczne i drzewa RC. Nie znaleziono czysto funkcjonalnego badania.
Czysto funkcjonalną analizę i implementację można znaleźć na Splay, AVL, czerwono-czarnym drzewie, ale NIE są to drzewa dynamiczne. Te pierwsze są uważane za cień (zwaną także wirtualną lub pomocniczą) strukturą danych tego drugiego.
Moje pytanie brzmi:
Jakie są przyczyny (wady, wady) społeczności badawczej ds. Programowania funkcjonalnego, która nie bierze udziału w strukturze danych dynamicznych drzew?