Zalety binarnych drzew wyszukiwania nad tabelami skrótów

Jakie są zalety drzew wyszukiwania binarnego w porównaniu z tabelami skrótów?

Tabele haszujące mogą wyszukiwać dowolny element w czasie Theta (1) i równie łatwo jest dodać element ... ale nie jestem pewien, jakie korzyści wynikają z odwrotnej sytuacji.

Pamiętaj, że binarne drzewa wyszukiwania (oparte na referencjach) są wydajne w pamięci. Nie rezerwują więcej pamięci, niż potrzebują.

Na przykład, jeśli funkcja skrótu ma zakres R(h) = 0...100, musisz przydzielić tablicę 100 elementów (wskaźników do), nawet jeśli haszujesz tylko 20 elementów. Gdybyś miał użyć drzewa wyszukiwania binarnego do przechowywania tych samych informacji, przydzieliłbyś tylko tyle miejsca, ile potrzebujesz, a także niektóre metadane dotyczące linków.

Jedną z zalet, na którą nikt inny nie zwrócił uwagi, jest to, że drzewo wyszukiwania binarnego umożliwia wydajne przeszukiwanie zakresów.

Aby zilustrować mój pomysł, chcę przedstawić skrajny przypadek. Załóżmy, że chcesz uzyskać wszystkie elementy, których klucze mieszczą się w przedziale od 0 do 5000. W rzeczywistości jest tylko jeden taki element i 10000 innych elementów, których klucze nie należą do zakresu. BST może całkiem efektywnie przeszukiwać zakresy, ponieważ nie przeszukuje poddrzewa, na które nie można znaleźć odpowiedzi.

W jaki sposób możesz wyszukiwać zakresy w tabeli skrótów? Musisz albo iterować każdą przestrzeń kubełkową, która wynosi O (n), albo musisz sprawdzić, czy istnieje każda z 1, 2, 3, 4 ... do 5000. (co z kluczami od 0 do 5000 to nieskończony zestaw? na przykład klucze mogą być liczbami dziesiętnymi)

Jedną z „zalet” drzewa binarnego jest to, że można po nim przejść, aby wyświetlić wszystkie elementy w kolejności. Nie jest to niemożliwe w przypadku tablicy Hash, ale nie jest to normalna operacja polegająca na projektowaniu struktury haszowanej.

Oprócz wszystkich innych dobrych komentarzy:

Tabele skrótów ogólnie mają lepsze zachowanie pamięci podręcznej, wymagając mniejszych odczytów pamięci w porównaniu z drzewem binarnym. W przypadku tablicy skrótów zwykle ponosisz tylko jeden odczyt, zanim uzyskasz dostęp do odniesienia przechowującego dane. Drzewo binarne, jeśli jest wariantem zrównoważonym, wymaga czegoś w kolejności odczytów pamięci k * lg (n) dla jakiejś stałej k.

Z drugiej strony, jeśli wróg zna twoją funkcję skrótu, może wymusić na twojej tablicy mieszania kolizje, znacznie utrudniając jej działanie. Sposób obejścia problemu polega na losowym wybraniu funkcji skrótu z rodziny, ale BST nie ma tej wady. Ponadto, gdy ciśnienie w tabeli mieszania rośnie zbyt mocno, często masz tendencję do powiększania i ponownego przydzielania tabeli mieszania, co może być kosztowną operacją. BST ma tutaj prostsze zachowanie i nie ma tendencji do nagle przydzielania dużej ilości danych i wykonywania operacji ponownego haszowania.

Drzewa wydają się być ostateczną średnią strukturą danych. Mogą działać jako listy, można je łatwo podzielić do pracy równoległej, mają szybkie usuwanie, wstawianie i wyszukiwanie w kolejności O (lg n) . Nie robią nic szczególnie dobrze, ale nie zachowują się też wyjątkowo źle.

Wreszcie, BST są znacznie łatwiejsze do zaimplementowania w (czystych) językach funkcjonalnych w porównaniu do tablic mieszających i nie wymagają implementacji destrukcyjnych aktualizacji ( argument persystencji Pascala powyżej).

Główną zaletą drzewa binarnego w porównaniu z tablicą mieszającą jest to, że drzewo binarne zapewnia dwie dodatkowe operacje, których nie można wykonać (łatwo i szybko) z tablicą mieszającą

• znajdź element najbliższy (niekoniecznie równy) jakiejś dowolnej wartości klucza (lub najbliższy powyżej / poniżej)

• iteruj zawartość drzewa w posortowanej kolejności

Te dwa elementy są ze sobą połączone - drzewo binarne utrzymuje swoją zawartość w posortowanej kolejności, więc rzeczy, które wymagają tego posortowanego porządku, są łatwe do wykonania.

(Zrównoważone) drzewo wyszukiwania binarnego ma również tę zaletę, że jego asymptotyczna złożoność jest w rzeczywistości górną granicą, podczas gdy „stałe” czasy dla tabel skrótów są amortyzowane: jeśli masz nieodpowiednią funkcję skrótu, możesz skończyć degradacją do czasu liniowego zamiast stałego.

Tablica haszująca zajmowałaby więcej miejsca, gdy została utworzona po raz pierwszy - będzie miała dostępne miejsca na elementy, które nie zostały jeszcze wstawione (niezależnie od tego, czy zostały kiedykolwiek wstawione), drzewo wyszukiwania binarnego będzie tak duże, jak to konieczne być. Ponadto, gdy tablica skrótów potrzebuje więcej miejsca, rozszerzenie do innej struktury może być czasochłonne, ale może to zależeć od implementacji.

Drzewo wyszukiwania binarnego można zaimplementować za pomocą trwałego interfejsu, w którym zwracane jest nowe drzewo, ale stare drzewo nadal istnieje. Starannie wdrożone, stare i nowe drzewa mają wspólne większość węzłów. Nie można tego zrobić ze standardową tabelą skrótów.

Drzewo binarne jest wolniejsze do przeszukiwania i wstawiania, ale ma bardzo fajną funkcję przechodzenia przez wrostek, co zasadniczo oznacza, że ​​możesz iterować po węzłach drzewa w posortowanej kolejności.

Iterowanie po wpisach tablicy skrótów nie ma większego sensu, ponieważ wszystkie są rozproszone w pamięci.

Z Cracking the Coding Interview, 6. wydanie

Możemy zaimplementować tablicę skrótów ze zrównoważonym drzewem wyszukiwania binarnego (BST). To daje nam czas wyszukiwania O (log n). Zaletą tego jest potencjalnie mniejsze wykorzystanie miejsca, ponieważ nie przydzielamy już dużej tablicy. Możemy również iterować po klawiszach w kolejności, co czasami może być przydatne.

BST zapewniają również operacje "findPredecessor" i "findSuccessor" (aby znaleźć następny najmniejszy i następny największy element) w czasie O (logn), co również może być bardzo przydatne. Hash Table nie może zapewnić w tym czasie wydajności.

Jeśli chcesz uzyskać dostęp do danych w sposób posortowany, posortowana lista musi być utrzymywana równolegle do tabeli skrótów. Dobrym przykładem jest Dictionary w .Net. (patrz http://msdn.microsoft.com/en-us/library/3fcwy8h6.aspx ).

Ma to efekt uboczny nie tylko spowolnienia wstawiania, ale również zużywa większą ilość pamięci niż b-drzewo.

Ponadto, ponieważ drzewo b jest posortowane, łatwo jest znaleźć zakresy wyników lub wykonać połączenia lub scalenia.

Zależy to również od zastosowania, Hash pozwala zlokalizować dokładne dopasowanie. Jeśli chcesz zapytać o zakres, wybierz BST. Załóżmy, że masz dużo danych e1, e2, e3 ..... en.

Dzięki tablicy skrótów możesz zlokalizować dowolny element w stałym czasie.

Jeśli chcesz znaleźć wartości zakresu większe niż e41 i mniejsze niż e8, BST może to szybko znaleźć.

Kluczową sprawą jest funkcja skrótu używana do unikania kolizji. Oczywiście nie możemy całkowicie uniknąć kolizji, w takim przypadku stosujemy łańcuchy lub inne metody. To sprawia, że ​​w najgorszych przypadkach pobieranie nie jest już stałym czasem.

Po zapełnieniu tabela skrótów musi zwiększyć rozmiar zasobnika i ponownie skopiować wszystkie elementy. Jest to dodatkowy koszt, który nie występuje w porównaniu z BST.

Tabele skrótów nie nadają się do indeksowania. Kiedy szukasz zakresu, BST są lepsze. To jest powód, dla którego większość indeksów baz danych używa drzew B + zamiast tabel skrótów

Drzewa wyszukiwania binarnego są dobrym wyborem do implementacji słownika, jeśli klucze mają zdefiniowaną jakąś całkowitą kolejność (klucze są porównywalne) i chcesz zachować informacje o kolejności.

Ponieważ BST zachowuje informacje o zamówieniu, udostępnia cztery dodatkowe operacje na zestawach dynamicznych, których nie można wykonać (efektywnie) przy użyciu tabel skrótów. Te operacje to:

1. Maksymalny
2. Minimum
3. Następca
4. Poprzednik

Wszystkie te operacje, jak każda operacja BST, mają złożoność czasową O (H). Ponadto wszystkie przechowywane klucze pozostają posortowane w BST, dzięki czemu można uzyskać posortowaną sekwencję kluczy po prostu przechodząc przez drzewo w odpowiedniej kolejności.

Podsumowując, jeśli wszystko, czego chcesz, to operacje wstawiania, usuwania i usuwania, to tabela skrótów jest bezkonkurencyjna (przez większość czasu) pod względem wydajności. Ale jeśli chcesz wykonać jedną lub wszystkie operacje wymienione powyżej, powinieneś użyć BST, najlepiej samobalansującego BST.

Główną zaletą tablicy mieszającej jest to, że wykonuje ona prawie wszystkie operacje w ~ = O (1). Jest bardzo łatwy do zrozumienia i wdrożenia. Skutecznie rozwiązuje wiele „problemów z rozmową kwalifikacyjną”. Więc jeśli chcesz złamać wywiad z kodowaniem, zaprzyjaźnij się z tablicą haszującą ;-)

Hashmap to zestaw tablicy asocjacyjnej. Tak więc tablica wartości wejściowych jest gromadzona w zasobnikach. W otwartym schemacie adresowania masz wskaźnik do zasobnika i za każdym razem, gdy dodajesz nową wartość do zasobnika, dowiadujesz się, gdzie w zasobniku są wolne miejsca. Można to zrobić na kilka sposobów - zaczynasz od początku segmentu i za każdym razem zwiększasz wskaźnik i sprawdzasz, czy jest zajęty. Nazywa się to sondowaniem liniowym. Następnie możesz przeprowadzić wyszukiwanie binarne, takie jak add, gdzie podwajasz różnicę między początkiem segmentu a miejscem, w którym podwajasz lub cofasz za każdym razem, gdy szukasz wolnego miejsca. Nazywa się to sondowaniem kwadratowym. DOBRZE. Teraz problem w obu tych metodach polega na tym, że jeśli wiadro przepełnia się do następnego adresu wiadra, to musisz:

1. Podwoić rozmiar każdego segmentu - malloc (N pojemników) / zmienić funkcję skrótu - Wymagany czas: zależy od implementacji malloc
2. Przenieś / skopiuj wszystkie wcześniejsze dane zasobników do nowych danych zasobników. Jest to operacja O (N), w której N reprezentuje wszystkie dane

DOBRZE. ale jeśli używasz listy linkowanej, nie powinno być takiego problemu, prawda? Tak, na połączonych listach nie masz tego problemu. Biorąc pod uwagę, że każdy zasobnik zaczyna się od połączonej listy, a jeśli masz 100 elementów w zasobniku, musisz przejść przez te 100 elementów, aby dotrzeć do końca połączonej listy, dlatego List.add (Element E) zajmie trochę czasu -

1. Haszuj element do zasobnika - normalny, jak we wszystkich implementacjach
2. Poświęć trochę czasu, aby znaleźć ostatni element we wspomnianej operacji wiadra O (N).

Zaletą implementacji połączonej listy jest to, że nie jest potrzebna operacja alokacji pamięci i przesyłanie / kopiowanie O (N) wszystkich zasobników, jak w przypadku otwartej implementacji adresowania.

Tak więc sposobem na zminimalizowanie operacji O (N) jest przekonwertowanie implementacji na implementację drzewa wyszukiwania binarnego, w którym operacje wyszukiwania to O (log (N)) i dodanie elementu w jego pozycji na podstawie jego wartości. Dodatkową cechą BST jest to, że jest posortowany!

Drzewa wyszukiwania binarnego mogą być szybsze, gdy są używane z kluczami łańcuchowymi. Zwłaszcza gdy struny są długie.

Drzewa wyszukiwania binarnego używające porównań dla mniejszych / większych, które są szybkie dla łańcuchów (gdy nie są równe). Więc BST może szybko odpowiedzieć, gdy ciąg nie zostanie znaleziony. Kiedy zostanie znaleziony, będzie musiał wykonać tylko jedno pełne porównanie.

W tabeli skrótów. Musisz obliczyć hash ciągu, a to oznacza, że ​​musisz przejść przez wszystkie bajty co najmniej raz, aby obliczyć hash. Z drugiej strony, gdy zostanie znaleziony pasujący wpis.