Tabele skrótów a drzewa binarne

Podczas implementacji słownika („Chcę wyszukiwać dane klientów według ich identyfikatorów klienta”), typowymi stosowanymi strukturami danych są tabele skrótów i drzewa wyszukiwania binarnego. Wiem na przykład, że biblioteka STL C ++ implementuje słowniki (nazywają je mapami) przy użyciu (zrównoważonych) drzew wyszukiwania binarnego, a platforma .NET używa tabel mieszania pod maską.

Jakie są zalety i wady tych struktur danych? Czy jest jakaś inna opcja, która jest uzasadniona w niektórych sytuacjach?

Zauważ, że nie jestem szczególnie zainteresowany przypadkami, w których klucze mają silną strukturę podstawową, powiedzmy, że wszystkie są liczbami całkowitymi od 1 do n lub coś.

— Alex ten Brink
źródło

Zirytuję cię, ale nie możesz po prostu powiedzieć „liczby całkowite od 1 do n”, ponieważ w takim przypadku tablica wyprzedzi wszystkie inne struktury danych :-). „Ciągi znaków” wydają się sprawiedliwe i obejmują większość sytuacji.

— jmad

@jmad powiedział, że nie jest zainteresowany tą sprawą.

— Joe

@ Joe Myślałem, że to jasne, że wziąłem to pod uwagę. W każdym razie nie jest to powód do podania najgorszego możliwego przykładu klucza.

— jmad

W rzeczywistości .NET ma zarówno słowniki zaimplementowane przy użyciu drzew, jak i słowniki zaimplementowane przy użyciu tabel mieszających (podobnie jak C ++ od standardu 2011).

— sepp2k

Możliwe to samo na SO: stackoverflow.com/questions/371136/...

— Ciro Santilli 20 改造中心法轮功六四事件

$n$

Krótka odpowiedź jest taka, że tabele skrótów są w większości przypadków szybsze , ale w najgorszym przypadku mogą być bardzo złe. Drzewa wyszukiwania mają wiele zalet, w tym oswajanie najgorszych zachowań , ale są nieco wolniejsze w typowych przypadkach.

$O(\mathrm{lg}(n))$ $\mathrm{log}_2(n)$

$2n$ $O(1)$

$O(1)$

$O(n)$
$O(1)$

Gdy wrzucisz lokalność danych do miksu, tabele skrótów działają źle. Działają dokładnie, ponieważ przechowują pokrewne elementy daleko od siebie, co oznacza, że jeśli aplikacja wyszukuje elementy współdzielące prefiks w sekwencji, nie skorzysta z efektów pamięci podręcznej. Nie ma to znaczenia, jeśli aplikacja wykonuje zasadniczo losowe wyszukiwania.

Kolejnym czynnikiem przemawiającym na korzyść drzew wyszukiwania jest to, że są one niezmienną strukturą danych: jeśli musisz wziąć kopię drzewa i zmienić w nim kilka elementów, możesz współdzielić większość struktury danych. Jeśli weźmiesz kopię tabeli skrótów, musisz skopiować całą tablicę wskaźników. Ponadto, jeśli pracujesz w czysto funkcjonalnych językach, tabele skrótów często nie są opcją.

$k_1 \equiv k_2 \implies h(k_1) = h(k_2)$

W szczególności, jeśli będziesz potrzebować kolejności klawiszy, na przykład jeśli chcesz mieć możliwość wyświetlania kluczy w kolejności alfabetycznej, to tabele skrótów nie pomogą (musisz je posortować), podczas gdy potrafi w prosty sposób przejść przez drzewo wyszukiwania.

Możesz łączyć drzewa wyszukiwania binarnego i tabele skrótów w postaci drzew skrótów . Drzewo skrótów przechowuje klucze w drzewie wyszukiwania zgodnie z ich skrótem. Jest to przydatne na przykład w czysto funkcjonalnym języku programowania, w którym chcesz pracować na danych, które nie mają łatwej do obliczenia relacji kolejności.

Gdy klucze są ciągami (lub liczbami całkowitymi), próbka może być inną opcją. Trie jest drzewem, ale indeksowanym inaczej niż drzewo wyszukiwania: piszesz klucz w trybie binarnym i idziesz w lewo dla 0, a w prawo dla 1. Koszt dostępu jest zatem proporcjonalny do długości klucza. Próby można skompresować w celu usunięcia węzłów pośrednich; jest to znane jako Patricia Trie lub Radix Tree . Drzewa Radix mogą przewyższać drzewa zrównoważone, szczególnie gdy wiele kluczy ma wspólny przedrostek.

— Gilles „SO- przestań być zły”
źródło

Czy BST również nie mają złej lokalizacji danych?

— sick

@svick Mogą, ale nie muszą, w zależności od sposobu przydzielania węzłów. Zwiększenie jałowości drzewa może pomóc bez pogorszenia czasu działania (koszt jest większy i bardziej złożony kod).

— Gilles „SO- przestań być zły”

Na BST łatwo jest uzyskać elementy „w porządku”, w przypadku tabeli skrótów nie ma mowy.

— vonbrand

Dlaczego nie ma to znaczenia innego niż ze względów bezpieczeństwa, jeśli tabele skrótów mają zły czas najgorszego przypadku, jeśli ich średnia wielkość jest lepsza niż w przypadku drzew binarnych? Wyobrażam sobie, że wygoda narzędzia / użytkownika ma w przybliżeniu liniowy związek z czasem, w którym drzewo kończy, więc więc oczekiwana (średnia) wartość powinna mieć znaczenie.

— Kelmikra

@ Kyth'Py1k Co rozumiesz przez „drzewo do końca”? Celem tablic skrótów jest dostęp do jednej wartości na raz, a nie do całego drzewa, w przeciwnym razie lista lub tablica działałyby lepiej. Nawet w situtations, w których liczy się średnia wartość (co nie zawsze ma miejsce, np. Gdy masz ograniczenia w czasie rzeczywistym), jest to średnia z żądań złożonych w danej sytuacji, które często nie są wcale jednolite w tabeli - np. Tendencyjny do określonego przedrostka.

— Gilles „SO- przestań być zły”