Kiedy wybrać drzewo RB, B-Tree czy AVL?

Kiedy jako programista powinienem rozważyć użycie drzewa RB, B-drzewa lub drzewa AVL? Jakie są kluczowe punkty, które należy wziąć pod uwagę przed podjęciem decyzji o wyborze?

Czy ktoś mógłby wyjaśnić scenariuszem dla każdej struktury drzewa, dlaczego jest ona wybierana zamiast innych w odniesieniu do kluczowych punktów?

Weź to ze szczyptą soli:

B-tree, gdy zarządzasz więcej niż tysiącami elementów i stronicujesz je z dysku lub wolnego nośnika danych.

Drzewo RB, gdy robisz dość częste wstawianie, usuwanie i pobieranie w drzewie.

Drzewo AVL, gdy wstawianie i usuwanie jest rzadkie w stosunku do pobierania.

Myślę, że drzewa B + to dobra uporządkowana struktura danych kontenera ogólnego przeznaczenia, nawet w pamięci głównej. Nawet jeśli pamięć wirtualna nie stanowi problemu, często jest przyjazna pamięć podręczna, a drzewa B + są szczególnie dobre w przypadku dostępu sekwencyjnego - ta sama asymptotyczna wydajność jak w przypadku listy połączonej, ale przyjazność dla pamięci podręcznej jest bliska prostej tablicy. Wszystko to i O (log n) wyszukuj, wstawiaj i usuwaj.

Drzewa B + mają jednak problemy - na przykład elementy poruszające się w węzłach podczas wstawiania / usuwania, unieważnianie wskaźników do tych elementów. Mam bibliotekę kontenerów, która wykonuje „konserwację kursorów” - kursory dołączają się do węzła-liścia, do którego aktualnie się odwołują na połączonej liście, dzięki czemu można je naprawić lub unieważnić automatycznie. Ponieważ rzadko jest więcej niż jeden lub dwa kursory, działa dobrze - ale i tak wymaga dodatkowej pracy.

Inną rzeczą jest to, że drzewo B + jest po prostu tym. Myślę, że możesz usunąć lub odtworzyć węzły nie będące liśćmi, w zależności od tego, czy ich potrzebujesz, czy nie, ale dzięki węzłom drzew binarnych uzyskujesz znacznie większą elastyczność. Drzewo binarne można przekształcić w połączoną listę iz powrotem bez kopiowania węzłów - wystarczy zmienić wskaźniki, a następnie pamiętać, że traktujesz je teraz jako inną strukturę danych. Między innymi oznacza to, że uzyskujesz dość łatwe O (n) łączenie drzew - przekonwertuj oba drzewa na listy, połącz je, a następnie przekonwertuj z powrotem na drzewo.

Kolejną rzeczą jest przydzielanie i zwalnianie pamięci. W drzewie binarnym można to oddzielić od algorytmów - użytkownik może utworzyć węzeł, a następnie wywołać algorytm wstawiania, a usuwanie może wyodrębnić węzły (odłącz je od drzewa, ale nie zwalniaj pamięci). W drzewie B lub B + to oczywiście nie działa - dane będą żyć w węźle złożonym z wielu elementów. Pisanie metod wstawiania, które „planują” operację bez modyfikowania węzłów, dopóki nie dowiedzą się, ile nowych węzłów jest potrzebnych i czy można je przydzielić, jest wyzwaniem.

Czerwony czarny vs. AVL? Nie jestem pewien, czy ma to duże znaczenie. Moja własna biblioteka ma klasę „narzędzi” opartą na zasadach do manipulowania węzłami, z metodami dla podwójnie połączonych list, prostych drzew binarnych, drzew splay, czerwono-czarnych drzew i drzew, w tym różnych konwersji. Niektóre z tych metod zostały wdrożone tylko dlatego, że od czasu do czasu się nudziłem. Nie jestem pewien, czy nawet testowałem metody treap. Powodem, dla którego wybrałem czerwono-czarne drzewa zamiast AVL, jest to, że osobiście lepiej rozumiem algorytmy - co nie oznacza, że ​​są prostsze, to tylko przypadek historii, że lepiej je znam.

I ostatnia rzecz - pierwotnie opracowałem moje kontenery B + w ramach eksperymentu. To jeden z tych eksperymentów, które tak naprawdę nigdy się nie skończyły, ale nie jest to coś, co chciałbym zachęcić innych do powtórzenia. Jeśli potrzebujesz tylko uporządkowanego kontenera, najlepszą odpowiedzią jest użycie tego, który zapewnia Twoja istniejąca biblioteka - np. Std :: map itp. W C ++. Moja biblioteka ewoluowała przez lata, zajęło trochę czasu, zanim stała się stabilna, a stosunkowo niedawno odkryłem, że jest technicznie nieprzenośna (zależna od nieco niezdefiniowanego zachowania WRT offsetof).

W pamięci B-Tree ma tę zaletę, że liczba elementów przekracza 32000 ... Spójrz na speedtest.pdf ze stx-btree .

Wybierając struktury danych, kupujesz takie czynniki jak

• prędkość pobierania v prędkość aktualizacji
• jak dobrze struktura radzi sobie z operacjami w najgorszym przypadku, na przykład wstawianie rekordów przychodzących w posortowanej kolejności
• zmarnowana przestrzeń

Zacząłbym od przeczytania artykułów Wikipedii, do których odwołuje się Robert Harvey.

Pragmatycznie, pracując w językach takich jak Java, przeciętny programista zazwyczaj używa dostarczonych klas kolekcji. Jeśli podczas działania dostrajania wydajności odkryje się, że wydajność kolekcji jest problematyczna, można poszukać alternatywnych implementacji. Rzadko kiedy jest to pierwsza rzecz, którą trzeba wziąć pod uwagę przy projektowaniu biznesowym. Niezwykle rzadko zdarza się, że trzeba implementować takie struktury danych ręcznie, zwykle istnieją biblioteki, z których można skorzystać.