Jakie drzewo binarne samobalansujące poleciłbyś?

18

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ę.

dan_waterworth
źródło
Jeśli chodzi o wydajność i łatwość wdrożenia, ogólne wydajności są dobrze określone, ale dla twojej implementacji, uważam, że najlepszą rzeczą byłoby wdrożyć tyle, ile można znaleźć, a następnie dać nam znać, który działa najlepiej ...
glenatron

Odpowiedzi:

15

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.

Szybki Joe Smith
źródło
1
Osobiście uważam, że czerwono-czarna wkładka jest łatwiejsza niż wkładka AVL. Powodem jest (niedoskonała) analogia do B-drzew. Wstawki są skrzypiące, ale skreślenia są złe (tyle przypadków do rozważenia). W rzeczywistości nie mam już własnej czerwono-czarnej implementacji usuwania C ++ - usunąłem ją, kiedy zdałem sobie sprawę (1), że nigdy jej nie używałem - za każdym razem, gdy chciałem usunąć, usuwałem wiele elementów, więc przekonwertowałem z drzewa na listy, usuń z listy, a następnie przekonwertuj z powrotem na drzewo i (2) i tak został uszkodzony.
Steve314
2
@ Steve314, czerwono-czarne drzewa są łatwiejsze, ale nie udało ci się dokonać implementacji, która działa? Jakie są wtedy drzewa AVL?
dan_waterworth
@dan_waterworth - Nie wdrożyłem jeszcze metody, która działa, ale mam notatki, rozumiem podstawową zasadę, ale nigdy nie uzyskałem właściwej kombinacji motywacji, czasu i pewności siebie. Jeśli tylko chciałem, aby wersje działały, to po prostu kopiuj pseudokod z podręcznika i tłumacz (i nie zapominaj, że C ++ ma standardowe kontenery z bibliotekami), ale gdzie w tym jest zabawa?
Steve314,
BTW - Wierzę (ale nie mogę podać odniesienia), że dość popularny podręcznik zawiera błędną implementację jednego ze zrównoważonych algorytmów drzewa binarnego - nie jestem pewien, ale może to być czerwono-czarne usunięcie. Więc to nie tylko ja ;-)
Steve314
1
@ Steve314, wiem, drzewa mogą być piekielnie skomplikowane w imperatywnym języku, ale, co zaskakujące, ich wdrożenie w Haskell było dziecinnie proste. Napisałem zwykłe drzewo AVL, a także wariant przestrzenny 1D w weekend i oba mają tylko około 60 linii.
dan_waterworth
10

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ść)

Matthieu M.
źródło
Naprawdę lubię listy pominięć i zaimplementowałem je wcześniej, choć nie w funkcjonalnym języku. Myślę, że spróbuję po nich, ale teraz jestem na drzewach równoważących się.
dan_waterworth
Ponadto ludzie często używają list narciarskich do współbieżnych struktur danych. Może być lepiej, zamiast wymuszać niezmienność, używać prymitywów współbieżności haskell (takich jak MVar lub TVar). Chociaż nie nauczy mnie to wiele o pisaniu kodu funkcjonalnego.
dan_waterworth
2
@ Fanatic23, lista pominięć nie jest ADT. ADT jest zestawem lub tablicą asocjacyjną.
dan_waterworth
@dan_waterworth my bad, masz rację.
Fanatic23
5

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).

Steve314
źródło
1
+1. Treaps to mój osobisty wybór, napisałem nawet post na blogu o tym, jak są wdrażane.
P Shved
5

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.

S.Lott
źródło
3

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.

Steve314
źródło
Splays są nieco denerwujące, ponieważ modyfikują drzewo, nawet gdy znajdują. Byłoby to dość bolesne w środowiskach wielowątkowych, co jest jedną z głównych motywacji do używania funkcjonalnego języka, takiego jak Haskell. Z drugiej strony nigdy wcześniej nie używałem języków funkcjonalnych, więc może to nie jest czynnik.
Szybki Joe Smith
@ Szybki - zależy od tego, jak zamierzasz korzystać z drzewa. Jeśli użyjesz go w kodzie w stylu funkcjonalnym, albo porzucisz mutację przy każdym znalezieniu (co czyni drzewo Splay nieco głupim), albo skończy się powielaniem znacznej części drzewa binarnego przy każdym wyszukiwaniu, i śledź stan drzewa, z którym pracujesz w miarę postępu pracy (powód prawdopodobnie używania stylu monadycznego). Kopiowanie może zostać zoptymalizowane przez kompilator, jeśli nie będziesz już odwoływał się do stanu starego drzewa po utworzeniu nowego (podobne założenia są powszechne w programowaniu funkcjonalnym), ale może nie.
Steve314,
Żadne podejście nie wydaje się warte wysiłku. Z drugiej strony, w przeważającej części nie używaj również czysto funkcjonalnych języków.
Szybki Joe Smith
1
@ Szybki - Powielanie drzewa jest tym, co zrobisz dla dowolnej struktury danych drzewa w czysto funkcjonalnym języku do mutowania algorytmów, takich jak wstawki. Pod względem źródłowym kod nie będzie się różnił od kodu imperatywnego, który wykonuje aktualizacje w miejscu. Różnice zostały już prawdopodobnie rozwiązane w przypadku niezrównoważonych drzew binarnych. Tak długo, jak nie będziesz próbował dodawać łączy nadrzędnych do węzłów, duplikaty będą miały wspólne wspólne poddrzewa co najmniej, a głęboka optymalizacja w Haskell jest dość hardkorowa, jeśli nie idealna. Zasadniczo sam jestem anty-Haskellem, ale to niekoniecznie problem.
Steve314,
2

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.

Petr Pudlák
źródło