Mam podstawową wiedzę na temat tego, jak 2-3-4 trees utrzymywać działanie właściwości bilansu wysokości po operacji, aby upewnić się, że nawet najgorsze operacje to O (n logn).Dlaczego nie używamy 2-3 lub 2-3-4-5 drzew?
Ale nie rozumiem tego wystarczająco dobrze, aby wiedzieć, dlaczego tylko 2-3-4?
Dlaczego nie 2-3 lub 2-3-4-5 itp?
Szczerze mówiąc, nie wiedziałem o 2-3-4 drzewach. W mojej klasie Data Structures uczono nas 2-3 drzewek i, szczerze mówiąc, większość z nas zaimplementowała drzewa AVL do mokrej części ćwiczenia.
Ale najwyraźniej istnieje uogólnienie tego typu drzewa: (a,b) tree.
Wdrażanie 2-3-4 drzew wymaga zwykle wielu klas (2NODE, 3NODE, 4NODE) lub masz właśnie NODE z tablicą elementów. W przypadku wielu klas tracisz dużo czasu na konstruowanie i niszczenie instancji węzła, a ich ponowne tworzenie jest uciążliwe. Jeśli używasz pojedynczej klasy z tablicami do przechowywania elementów i dzieci, to albo ciągle zmieniasz rozmiar tablic, co jest podobnie nieekonomiczne, albo kończysz marnując ponad połowę swojej pamięci na nieużywane elementy tablicy. To po prostu nie jest zbyt wydajne w porównaniu z czerwono-czarnymi drzewami.
Drzewa czerwono-czarne mają tylko jeden typ struktury węzła. Ponieważ czerwono-czarne drzewa mają dwoistość z 2-3-4 drzewami, drzewa RB mogą używać dokładnie tych samych algorytmów co 2-3-4 drzewa (nie ma potrzeby stosowania głupich mylących/złożonych implementacji opisanych w Cormen, Leiserson i Rivest, które prowadziły do drzewek AA, które nie są mniej złożone niż algorytm 2-3-4.)
Tak więc, czerwono-czarne drzewa dla łatwości implementacji oraz wydajności pamięci/procesora. (Drzewa AVL są również ładne, produkują lepiej zbalansowane drzewa i są głupie po prostu do kodowania, ale wydają się być mniej wydajne, ponieważ pracują zbyt często, aby utrzymać tylko nieco bardziej zwarte drzewo.)
Och, i 2 3-4-5-6 ... itp. Nie są zrobione, ponieważ nic się nie zyskuje. 2-3-4 ma przyrost netto ponad 2-3 drzew, ponieważ można je łatwo wykonać bez rekursji (rekursja wydaje się być mniej wydajna, zwłaszcza gdy nie można jej zakodować w rekursywnie). Jednak B-drzewa i drzewa Bplus to prawie 2-3-4-5-6-7-8-9-etc drzewa, w których maksymalny rozmiar węzłów, n, jest wybrany tak, że n rekordów może być przechowywanych w jeden sektor dyskowy. (każdy sektor dysku jest węzłem drzewa, a rozmiar sektora jest równy liczbie elementów przechowywanych w węźle). Dzieje się tak, ponieważ czas na przeszukiwanie 512 rekordów liniowo w pamięci jest nadal DUŻO szybszy niż przechodzenie w dół poziom w drzewie, który wymaga innego wyszukiwania/pobierania dysku. i O (512) nadal jest O (1), a zatem utrzymuje O (lg n) dla drzewa.
Jeśli kiedykolwiek zaimplementowałeś 2-3-4 lub czerwono-czarne drzewo, będziesz wiedział, że nie jest bardzo banalnie robić dobrze, a następnie testować. Jest nawet uproszczona wersja czerwono-czarnego drzewa, drzewa [AA-tree] (http://en.wikipedia.org/wiki/AA_tree), które jest mniej symetryczne niż czerwono-czarne drzewo, ale wydaje się być dobra alternatywa, która ma mniejszą złożoność wdrażania. Kiedy potrzebujesz więcej podwęzłów lub bardziej płaskich drzew, wybierasz b-drzewa i jawnie obsługujesz wiele podwęzłów w jednolity sposób. –
Ponadto zawsze pojawiają się obawy co do lokalizacji danych i narzutów na węzeł (z powodu kosztów alokacji). Tego rodzaju problemy zwykle zachęcają do rozwiązań opartych na tablicach (np. Tablicach hashowych) w praktyce. –