Jako programista, kiedy należy rozważyć użycie drzewa RB, drzewa B lub drzewa AVL? Jakie są kluczowe kwestie, które należy wziąć pod uwagę przed podjęciem decyzji o wyborze?Kiedy wybrać drzewo RB, drzewo B lub drzewo AVL?
Czy ktoś może wyjaśnić scenariusz dla każdej struktury drzewa, dlaczego jest wybrany przez innych w odniesieniu do kluczowych punktów?
Weź to z przymrużeniem oka:
B-drzewo kiedy zarządzający więcej niż tysiące przedmiotów i jesteś przywoływania ich z dysku lub jakimś powolnym nośniku.
Drzewo RB, gdy robisz dość częste wstawianie, usuwanie i wyszukiwanie w drzewie.
Drzewo AVL, gdy twoje wstawki i usunięcia są rzadkie w stosunku do twoich poszukiwań.
Wystarczy dodać trochę więcej szczegółów: B-drzewa mogą mieć zmienną liczbę dzieci, które pozwalają na przechowywanie wielu rekordów, ale nadal utrzymują drzewo o małej wysokości. Drzewo RB zawiera mniej restrykcyjne reguły dotyczące ponownego równoważenia, które powodują, że wstawianie/usuwanie jest szybsze niż drzewo AVL. I odwrotnie, drzewo AVL jest bardziej zrównoważone, więc wyszukiwania są szybsze niż drzewo RB. – pschang
Drzewa RB mają również lepszą wydajność O (1) na równoważeniu, co czyni je bardziej odpowiednimi dla trwałych struktur danych z przewijaniem i przewijaniem do przodu. –
Przy wyborze struktur danych handlujesz od czynników takich jak
Chciałbym zacząć od czytania artykułów Wikipedii odwołuje Robert Harvey.
Pragmatycznie, podczas pracy w językach takich jak Java, przeciętny programista zazwyczaj korzysta z podanych klas kolekcji. Jeśli w procesie dostrajania wydajności odkryjesz, że wydajność kolekcji jest problematyczna, możesz szukać alternatywnych implementacji. Rzadko jest to pierwsza rzecz, którą musi rozważyć rozwój biznesowy. Niezwykle rzadko trzeba ręcznie wprowadzać takie struktury danych, zazwyczaj można korzystać z bibliotek.
Aby być uczciwym, OP zapytał "kiedy powinienem rozważyć użycie", a nie "kiedy powinienem rozważyć wdrożenie". Chociaż ostatni paragraf jest prawdziwy, nie zapewnia on dużej wartości w kontekście tego pytania. Nawet w przypadku bibliotek, musisz zrozumieć algorytmy, aby efektywnie wybrać, która struktura najlepiej odpowiada Twoim potrzebom biznesowym. – Dan
Myślę, że drzewa B + to dobra uporządkowana struktura danych ogólnego przeznaczenia, nawet w pamięci głównej. Nawet jeśli pamięć wirtualna nie jest problemem, często jest ona przyjazna dla pamięci podręcznej, a drzewa B + są szczególnie dobre dla dostępu sekwencyjnego - ta sama asymptotyczna wydajność, jak połączona lista, ale z przyjaznością dla pamięci podręcznej zbliżoną do prostej tablicy. Wszystko to i O (log n) szukaj, wstaw i usuń.
B + drzewa mają jednak problemy - takie jak elementy poruszające się w obrębie węzłów podczas wstawiania/usuwania, unieważniające wskaźniki do tych elementów. Mam bibliotekę kontenerów, która wykonuje "obsługę kursora" - kursory dołączają się do węzła z listkami, do którego aktualnie odwołują się na liście połączonej, aby można je było naprawić lub unieważnić automatycznie. Ponieważ rzadko jest więcej niż jeden lub dwa kursory, działa dobrze - ale to jeszcze trochę więcej pracy.
Inną rzeczą jest to, że drzewo B + jest w zasadzie tym właśnie. Sądzę, że możesz odciąć lub odtworzyć węzły inne niż liście w zależności od tego, czy ich potrzebujesz, czy nie, ale w przypadku węzłów drzewa binarnego zyskujesz większą elastyczność. Drzewo binarne można przekonwertować na listę połączoną iz powrotem bez kopiowania węzłów - wystarczy zmienić wskaźniki, a następnie pamiętać, że traktuje się je teraz jako inną strukturę danych. Między innymi oznacza to, że masz dość łatwe O (n) łączenie drzew - konwertuj oba drzewa na listy, scalaj je, a następnie konwertuj z powrotem do drzewa.
Kolejną rzeczą jest przydzielanie i uwalnianie 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łączyć je od drzewa, ale nie zwalniać pamięci). W drzewie B lub w drzewie B + to oczywiście nie działa - dane będą żyły w węźle z wieloma elementami. Pisanie metod wstawiania, które "planują" operację bez modyfikowania węzłów, dopóki nie będą wiedzieć, ile nowych węzłów jest potrzebnych i które mogą być przydzielone, jest wyzwaniem.
Czerwony czarny kontra AVL? Nie jestem pewien, czy robi to wielką różnicę. Moja własna biblioteka ma oparte na regułach "narzędzie" klasy do manipulowania węzłami, z metodami podwójnie połączonych list, prostych drzew binarnych, drzewek rozrzuconych, drzewek czerwono-czarnych i zawrotów, w tym różnych konwersji. Niektóre z tych metod zostały wdrożone tylko dlatego, że nudziłem się w tym samym czasie. Nie jestem pewien, czy testowałem nawet metody treap. Powodem, dla którego wybrałem czerwono-czarne drzewa, a nie AVL, jest to, że ja osobiście lepiej rozumiem algorytmy - co nie znaczy, że są prostsze, to tylko fiołek historii, że lepiej się z nimi zapoznałem.
Ostatnia rzecz - Pierwotnie opracowałem moje kontenery drzewa B + jako eksperyment. To jeden z tych eksperymentów, który nigdy się nie zakończył, ale nie jest to coś, co zachęciłbym innych do powtórzenia. Jeśli wszystko czego potrzebujesz to uporządkowany kontener, najlepszą odpowiedzią jest użycie tej, którą zapewnia twoja istniejąca biblioteka - np. std :: map etc w C++. Moja biblioteka ewoluowała przez lata, zajęło to sporo czasu, zanim stała się stabilna, a stosunkowo niedawno odkryłem, że jest technicznie nieprzenośna (w zależności od nieokreślonego zachowania WRT).
W pamięci B-drzewo ma tę zaletę, że liczba przedmiotów jest większa niż 32000 ... Popatrz na speedtest.pdf z stx-btree.
Cóż, ja na przykład doceniam to pytanie - obecnie prezentowane z wyborem fastutil IntAVLTreeSet vs. IntRBTreeSet. – Yang