Suchzeiten für den binären Suchbaum

Question

Kann jemand die Suchzeit für einen binären Suchbaum (d. H. Worst-Case, Best-Case und Average-Case) berechnen?

Answer 1

Für einen nicht selbstausgleichenden Baum (möglich, aber ungewöhnlich für einen Suchbaum) ist der schlechteste Fall O (n), was für den entarteten Binärbaum (eine verkettete Liste) gilt.

In diesem Fall müssen Sie im Durchschnitt die Hälfte der Liste suchen, bevor Sie das gewünschte Element finden.

Der beste Fall ist O (log n) für einen perfekt ausgeglichenen Baum, da Sie den Suchraum für jede Baumebene halbiert haben.

Durchschnittliche Fall ist irgendwo zwischen diesen beiden und hängt ganz von den Daten :-)

Da man selten die Folge zu steuern bekommen, in der Daten in einen Baum eingefügt wird, selbst ausgleichenden Bäume sind in der Regel bevorzugt, da Obwohl sie bei jeder Einfügung oder Löschung eine kleine Menge an Zeit hinzufügen, beschleunigen sie die Suche erheblich. Ihr schlimmster Fall ist so viel besser als unausgeglichene Bäume.

    8 
     _______/ \_______ 
     /    \ 
     4     12 
    __/ \__    __/ \__ 
/  \   /  \ 
    2   6  10  14 
/\  /\  /\  /\ 
1 3  5 7  9 11 13 15 

In diesem perfekt ausgewogenen Baum, können Sie, dass Sie für alle n Ebenen erhalten 2 ⁿ -1 Knoten sehen. Das bedeutet, dass Sie für 15 Knoten nie mehr als vier Knoten suchen müssen, um diesen zu finden (z. B. um zu finden, suchen Sie 8, 12, 14 und 13). Das ist, wo das Protokoll n Abbildung stammt.

Ein entarteter unausgeglichener Baum, wie bereits erwähnt, ist eine verkettete Liste. Wenn Ihre Daten in Folge angekommen und Sie es in einem unausgeglichenen binären Baum eingefügt, dann würden Sie erhalten:

1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -+ 
              | 
+------------------------------------------+ 
| 
+-> 10 -> 11 -> 12 -> 13 -> 14 -> 15 

Um 13 in diesem Fall zu finden, würden Sie 1, 2, 3, 4, suchen müssen 5 , 6, 8, 9, 10, 11, 12 und 13, daher O (n).

Answer 2

Möchte diesen als "Hausaufgabe" markieren. Hier ist ein guter Ausgangspunkt: http://en.wikipedia.org/wiki/Binary_search_tree

Im Allgemeinen ist eine ausgewogene binärer Suchbaum ein Worst-Case-Lookup von O hat (log n), am besten Fall von O (1) (wenn der gewünschte Wert ist die Wurzel) und ein durchschnittlicher Fall von O (log n) (die Blätter enthalten exponentiell mehr Werte als ihre Eltern). Der schlimmste Fall ist der interessanteste und wird leicht erkannt, wenn man erkennt, dass die erste Ebene eines binären Baums 1 Knoten hat, der zweite 2, der dritte 4 und so weiter. Somit ist die Anzahl der Knoten in einem Binärbaum der Tiefe n genau 2^n - 1. Das mathematische Inverse der Exponentialfunktion ist der Logarithmus, also: O (log n).

Ein unausgewogener Baum so schlecht, wie eine verknüpfte Liste sein kann und eine Form wie die folgenden hat:

1 
/\ 
    2 
/\ 
     3 
    /\ 
     4 
    /\ 

In dieser Situation ist die Zugriffszeit Worst-Case ist O (n).

Answer 3

Am besten ist O (1). Das erste Element könnte das Objekt sein, nach dem Sie suchen. der schlechteste Fall ist O (n), dh in einem schiefen Baum, und der durchschnittliche Fall ist O (lg n).