Mieszanie za pomocą drzew wyszukiwania zamiast list

11

Walczę z haszowaniem i materiałem do wyszukiwania binarnego. Przeczytałem, że zamiast używać list do przechowywania wpisów z tymi samymi wartościami skrótu, możliwe jest również użycie drzew wyszukiwania binarnego. I staram się zrozumieć, jaki jest najgorszy i średni przypadek wykonania operacji

insert,
find i
delete

jest wart. średni przypadek. Czy poprawiają się w odniesieniu do list?

— forrestGump
źródło

Jeśli masz dostęp do rygorystycznej analizy środowisk uruchomieniowych tablic mieszających z łańcuchem liniowym (tj. Listy liniowe), zamień tę część, w której średnie koszty na listach liniowych są podłączone, ze średnimi wynikami przypadków implementacji zrównoważonego drzewa wyszukiwania. Reszta to mechanika. (Oczywiście pomaga.)

— Raphael

4

$O(1)$ $O(n)$ $O(n)$ $O(n)$ $O(\log n)$ $O(n)$

$O(\log n)$

— jmad
źródło

1

To wszystko prawda, ale nie widzę odpowiedzi na postawione pytanie.

— rgrig

To nie było to samo pytanie w ogóle w tym czasie. (Nawet historia edycji nie ma oryginalnego pytania. Dziwne.) Mogłabym zaktualizować swoją odpowiedź, ale stałaby się zbędna z odpowiedzią Gillesa.

— jmad

4

$O(n)$ $n$ $n$ $n-1 = \Theta(n)$ $n-1$ $O(n)$ $O(1)$

$O(\log n)$

$O(1)$

$n$ $n/2$ $\Theta(n)$ $\Theta(\log n)$

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

2

„ze średnim rozkładem danych” powinien czytać „z wystarczająco losową funkcją skrótu”

— JeffE