Hashing mit Suchbäumen anstelle von Listen

Ich habe Probleme mit Hashing und binärem Suchbaummaterial. Und ich habe gelesen, dass anstelle von Listen zum Speichern von Einträgen mit denselben Hashwerten auch binäre Suchbäume verwendet werden können. Und ich versuche zu verstehen, was die schlechteste und durchschnittliche Laufzeit für die Operationen ist

1. insert,
2. find und
3. delete

ist wert. Durchschnittsfall. Verbessern sie sich in Bezug auf Listen?

Bei Listen erfolgt das Einfügen, Suchen und Löschen in , O ( n ) , O ( n ) . Sortierte Liste sind schlechter. Die binäre Suche selbst erfolgt nach sortierten Arrays, in denen sich die Operationen in O ( n ) , O ( log n ) , O ( n ) befinden . Wenn Sie "Einfügen" und "Löschen" möchten, benötigen Sie mehr als nur eine binäre Suche.$O(1)$$O(n)$$O(n)$$O(n)$$O(\log n)$$O(n)$

Sie möchten wahrscheinlich so etwas wie binäre Suchbäume . Es ist viel einfacher, Referenzen darüber zu finden, wenn Sie die richtige Terminologie haben. Diese Operationen sind in Worst-Case-Zeit, beispielsweise für Implementierungen mitAVL-Bäumenundrot-schwarzen Bäumen.$O(\log n)$

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