Jakie drzewo binarne samobalansujące poleciłbyś?

Uczę się Haskell i jako ćwiczenie tworzę drzewa binarne. Po utworzeniu zwykłego drzewa binarnego chcę go dostosować, aby sam się balansował. Więc:

• Który jest najbardziej wydajny?
• Który jest najłatwiejszy do wdrożenia?
• Który jest najczęściej używany?

Ale co najważniejsze, co polecacie?

Zakładam, że należy to tutaj, ponieważ jest otwarte na debatę.

Polecam zacząć od drzewa czerwono-czarnego lub drzewa AVL .

Czerwono-czarne drzewo jest szybsze do wstawiania, ale drzewo AVL ma niewielką krawędź do wyszukiwania. Drzewo AVL jest prawdopodobnie nieco łatwiejsze do zaimplementowania, ale wcale nie w oparciu o moje własne doświadczenia.

Drzewo AVL zapewnia, że ​​drzewo jest zrównoważone po każdym wstawieniu lub usunięciu (żadne sub-drzewo nie ma współczynnika równowagi większego niż 1 / -1, podczas gdy czerwono-czarne drzewo zapewnia, że ​​drzewo jest odpowiednio zrównoważone w dowolnym momencie.

Rozważałbym alternatywę, jeśli nie masz nic przeciwko losowym strukturom danych: Listy pomijania .

Z wysokiego poziomu jest to struktura drzewa, z tym wyjątkiem, że nie jest implementowana jako drzewo, ale jako lista z wieloma warstwami łączy.

Dostaniesz wstawianie / przeszukiwanie / usuwanie O (log N) i nie będziesz musiał radzić sobie z tymi wszystkimi trudnymi przypadkami przywracania równowagi.

Nigdy nie zastanawiałem się nad wdrożeniem ich w języku funkcjonalnym, a strona wikipedia nie pokazuje żadnych, więc może nie być to łatwe (wrt na niezmienność)

Jeśli chcesz zacząć od stosunkowo łatwej struktury (zarówno drzewa AVL, jak i drzewa czerwono-czarne są skrzypiące), jedną z opcji jest pułapka - nazwana jako kombinacja „drzewa” i „sterty”.

Każdy węzeł otrzymuje wartość „priorytetu”, często losowo przypisywaną podczas tworzenia węzła. Węzły są umieszczane w drzewie, tak aby przestrzegano kolejności kluczy, a także przestrzegano porządkowania wartości priorytetów w kształcie sterty. Rozmieszczanie na stosie oznacza, że ​​oboje dzieci rodzica mają niższe priorytety niż rodzic.

EDYCJA usunęła „w obrębie kluczowych wartości” powyżej - priorytet i kolejność kluczy obowiązują razem, więc priorytet jest istotny nawet dla unikatowych kluczy.

To ciekawa kombinacja. Jeśli klucze są unikalne, a priorytety unikalne, istnieje unikalna struktura drzewa dla dowolnego zestawu węzłów. Mimo to wstawianie i usuwanie jest wydajne. Ściśle mówiąc, drzewo może być niezrównoważone do tego stopnia, że ​​jest to faktycznie lista połączona, ale jest to bardzo mało prawdopodobne (jak w przypadku standardowych drzew binarnych), w tym w normalnych przypadkach, takich jak klucze wstawiane po kolei (w przeciwieństwie do standardowych drzew binarnych).

Który jest najbardziej wydajny?

Niejasne i trudne do odpowiedzi. Złożoności obliczeniowe są dobrze zdefiniowane. Jeśli to rozumiesz przez efektywność, nie ma prawdziwej debaty. Rzeczywiście, wszystkie dobre algorytmy pochodzą z dowodów i czynników złożoności.

Jeśli masz na myśli „czas działania” lub „wykorzystanie pamięci”, musisz porównać rzeczywiste implementacje. Następnie w grę wchodzą język, czas działania, system operacyjny i inne czynniki, które utrudniają odpowiedź na pytanie.

Który jest najłatwiejszy do wdrożenia?

Niejasne i trudne do odpowiedzi. Niektóre algorytmy mogą wydawać się skomplikowane, ale dla mnie banalne.

Który jest najczęściej używany?

Niejasne i trudne do odpowiedzi. Najpierw jest „przez kogo?” część tego? Tylko Haskell? Co z C lub C ++? Po drugie, istnieje zastrzeżony problem z oprogramowaniem, w którym nie mamy dostępu do źródła w celu przeprowadzenia ankiety.

Ale co najważniejsze, co polecacie?

Zakładam, że należy to tutaj, ponieważ jest otwarte na debatę.

Poprawny. Ponieważ twoje pozostałe kryteria nie są zbyt pomocne, to wszystko, co dostaniesz.

Możesz uzyskać źródło dużej liczby algorytmów drzewa. Jeśli chcesz się czegoś nauczyć, możesz po prostu zaimplementować każdy, kogo znajdziesz. Zamiast prosić o „rekomendację”, po prostu zbierz każdy algorytm, jaki możesz znaleźć.

Oto lista:

http://en.wikipedia.org/wiki/Self-balancing_binary_search_tree

Zdefiniowano sześć popularnych. Zacznij od nich.

Jeśli interesują Cię drzewa Splay, istnieje prostsza wersja tych, które, jak sądzę, zostały po raz pierwszy opisane w artykule Allena i Munroe. Nie ma takich samych gwarancji wydajności, ale pozwala uniknąć komplikacji związanych z ponownym równoważeniem „zig-zig” vs. „zig-zag”.

Zasadniczo podczas wyszukiwania (w tym wyszukiwania punktu wstawiania lub węzła do usunięcia) znaleziony węzeł jest obracany bezpośrednio w kierunku korzenia, od dołu do góry (np. Po wyjściu z funkcji wyszukiwania rekurencyjnego). Na każdym kroku wybierasz pojedynczy obrót w lewo lub w prawo w zależności od tego, czy dziecko, które chcesz wyciągnąć kolejny krok w kierunku korzenia, było prawym dzieckiem, czy lewym dzieckiem (jeśli odpowiednio pamiętam moje kierunki obrotu, to odpowiednio).

Podobnie jak drzewa Splay, chodzi o to, że ostatnio otwierane przedmioty są zawsze w pobliżu korzenia drzewa, więc dostęp do nich jest szybki. Upraszczając, te drzewa Allen-Munroe obracają się do korzeni (jak je nazywam - nie znam oficjalnej nazwy) mogą być szybsze, ale nie mają takiej samej gwarancji zamortyzowanej wydajności.

Jedna rzecz - ponieważ ta struktura danych z definicji mutuje nawet w przypadku operacji wyszukiwania, prawdopodobnie musiałaby zostać zaimplementowana monadycznie. IOW to może nie jest dobre dopasowanie do programowania funkcjonalnego.

Bardzo proste zrównoważone drzewo to drzewo AA . Niezmiennik jest prostszy, a zatem łatwiejszy w implementacji. Ze względu na swoją prostotę jego wydajność jest nadal dobra.

Jako ćwiczenie zaawansowane możesz spróbować użyć GADT do wdrożenia jednego z wariantów zrównoważonych drzew, których niezmiennik jest wymuszony przez typ systemu typów.