Zalety binarnych drzew wyszukiwania nad tabelami skrótów

104

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.

Oddany
źródło
jakie są czasy wykonywania funkcji find () insert () i remove () w przypadku tablic mieszających? theta (1) theta (1) i theta (1) prawda?
Poświęcony
8
Prawie zawsze tak. Jeśli napotkasz wiele kolizji, czasy te mogą wzrosnąć do O (n).
Christian Mann
1
Te czasy zależą również od funkcji haszującej. Jeśli z jakiegoś dziwnego powodu nie jest to O (1), oczywiście twoje operacje będą miały minimalną granicę wydajności, z jaką działa funkcja skrótu.
Christian Mann,
Powiedziałbym, że największą zaletą BST jest posortowana struktura danych. Szczegółowy przypadek użycia już wymieniony tutaj .
Yuantao
Możliwy duplikat drzew binarnych, list połączonych i tabel
skrótów

Odpowiedzi:

93

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.

Christian Mann
źródło
33
Nie jest prawdą, że w tablicy musi istnieć cały zakres danych wyjściowych funkcji skrótu. Wartości skrótu można po prostu zmodyfikować przez długość tablicy, aby umożliwić mniejszą tablicę. Oczywiście ostateczna liczba dodawanych elementów może nie być znana, więc tablica skrótów może nadal przydzielać więcej miejsca niż jest to konieczne. Drzewa wyszukiwania binarnego mogą jednak marnować tyle samo lub więcej pamięci. Powiązane implementacje wymagają miejsca na co najmniej dwa dodatkowe wskaźniki na element (trzy, jeśli używa się wskaźnika nadrzędnego), a oparte na tablicach BST mogą marnować dużo pamięci na niewypełnione części drzewa.
Solaraeus,
4
@Solaraeus: BST oparte na tablicach najlepiej porównuje się z tabelami haszującymi i nie są one bardziej marnotrawne niż tabele skrótów. Możesz także rozszerzyć BST za pomocą niewiele więcej niż kopii pamięci, w porównaniu z przeliczeniem całej tabeli.
Guvante,
127

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)

Alex
źródło
11
BST wydajnie przeszukuje zakresy! Dla mnie to najlepsza odpowiedź z punktu widzenia praktycznego i algorytmicznego podejścia.
ady
4
wow, to naprawdę wyjaśnia, dlaczego drzewa są tak powiązane z bazami danych; ich zalety są najbardziej widoczne, gdy trzeba przeprowadzić filtrowanie na podstawie kluczy. w przypadku map skrótów musisz zapętlić wszystkie klucze, aby rozwiązać „znajdź wszystkie elementy z kluczem między 1000 a 3290”
Dmitry
77

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.

NealB
źródło
3
przechodzenie w dowolnej kolejności prawdopodobnie nie miałoby sensu na tablicy haszującej.
FrustratedWithFormsDesigner
2
@FrustratedWithFormsDesigner. Zobacz sortowaną liniową tabelę
haszowania
Dzięki za link, to intersingowy pomysł! Nie sądzę, żebym kiedykolwiek widział lub używał implementacji tego (przynajmniej nieświadomie).
FrustratedWithFormsDesigner
1
Link Wayback Machine do artykułu - web.archive.org/web/20100323091632/http://www.concentric.net/ ...
rahulroy9202
51

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

DAJĘ ODPOWIEDZI CRAP
źródło
3
BSTs are much easier to implement in (pure) functional languages compared to hash-tables- naprawdę? Chcę się teraz nauczyć języka funkcjonalnego!
nawfal
1
Tablica skrótów musi być trwała w języku funkcjonalnym. To często komplikuje implementacje.
DAWĘ ODPOWIEDZI CRAPowi
aby rozwinąć, jeśli tworzysz struktury danych prezydenta w językach funkcyjnych, wszystko, co naprawdę robisz, to pisanie tego samego kodu, co w asemblerze, z wyjątkiem każdej operacji, w której jawnie transformujesz swoją tablicę pamięci / rejestrów lub rozmawiasz z serwerem, aby udawać aby to zrobić. Jestem za bycie świadomym twojego stanu, ale jest to izomorficzne z podejściem imperatywnym, jeśli zostanie wykonane poprawnie (nie możesz realistycznie skopiować dużej ilości danych na temat każdej transformacji w prawdziwym życiu, musisz oszukiwać).
Dmitry
27

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.

Chris Dodd
źródło
BST znajduje najbliższe dopasowanie, tylko jeśli dokładne dopasowanie nie istnieje, prawda? Co się stanie, jeśli znajdziesz dokładne dopasowanie w samym katalogu głównym?
programista747,
2
@ developer747: Kolejne najbliższe poniżej i powyżej to skrajnie prawy liść lewego poddrzewa i skrajny lewy liść prawego poddrzewa.
Chris Dodd,
16

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

jamesnvc
źródło
3
Aby to wyjaśnić, zdegenerowany przypadek ma miejsce, gdy kolekcja zawiera wiele kopii tylko 1 klucza. w BST wstaw O (log n), w tabeli Hash wstaw O (n)
SingleNegationElimination
2
Gdy tablica skrótów zawiera wiele kopii tylko 1 klucza, insert to (nadal) O (1), a nie O (n). Problem z tabelami skrótów polega na tym, że istnieje wiele różnych kluczy z tym samym hashem. Można tego uniknąć dzięki dynamicznemu schematowi mieszania, który przełącza się na inną funkcję skrótu, gdy występuje wiele kolizji.
Chris Dodd,
Zauważ, że niezrównoważone drzewo może zdegenerować się w listę, a także mieć wyszukiwanie O (n).
awiebe
9

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.

FrustratedWithFormsDesigner
źródło
8

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.

Pascal Cuoq
źródło
6

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.

Blagovest Buyukliev
źródło
6

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.

Guy Kahlon
źródło
5

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.

Balaji
źródło
Jeśli szukasz operacji „findPredecessor” i „findSuccessor”, to HashTable jest przede wszystkim złym wyborem dla struktury danych.
AKDesai
1

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.

IamIC
źródło
1

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.

sreeprasad
źródło
1

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

ssD
źródło
indeksy baz danych są typu hash i B +. Jeśli chcesz wykonać porównanie, takie jak większe lub mniejsze niż, indeks drzew B + jest przydatny, w przeciwnym razie indeks haszowania jest przydatny do wyszukiwania. Pomyśl także o tym, kiedy dane nie są porównywalne i jeśli chcesz utworzyć indeks, to db utworzy indeks skrótu, a nie indeks drzewa B +. @ssD
Sukhmeet Singh
1

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.

mightyWOZ
źródło
0

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ą ;-)

rajya vardhan
źródło
Myślę, że OP poprosił o zalety BST nad mieszaniem.
Snajper
0

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!

Vamsavardhana Vijay
źródło
0

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.

Calmarius
źródło