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

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