[Powered by Google Translate] Wie würden Sie repräsentieren alle Mitglieder Ihrer Familie in einem Computer? Wir könnten einfach eine Liste, aber es gibt eine klare Hierarchie hier. 

Lassen Sie uns sagen, dass wir mit Ihrer Urgroßmutter Alice beginnt. Sie hat 2 Söhne, Bob und dein Großvater, Charlie. Charlie hat 3 Kinder, Ihr Onkel, Dave, Ihre Tante, Eve, und dein Vater, Fred. Sie sind Fred einziges Kind. 

Warum sollte die Organisation Ihrer Familienmitglieder auf diese Weise besser sein als die einfache Liste Repräsentation? Ein Grund dafür ist, dass dieser hierarchischen Struktur, genannt "tree" enthält mehr Informationen als eine einfache Liste. Wir kennen die familiären Beziehungen zwischen allen nur durch die Untersuchung der Baum. Außerdem kann es zu beschleunigen Look-up-Zeit enorm, wenn Baum Daten sortiert. 

Wir können nicht die Vorteile, dass hier, aber wir werden ein Beispiel dafür bald zu sehen. Jede Person wird durch einen Knoten auf dem Baum dargestellt. Knoten können über untergeordnete Knoten sowie einer übergeordneten Knoten. Dies sind die technischen Begriffe, auch bei Verwendung von Bäumen für Dinge neben Familien. Alices Knoten hat 2 Kinder und keine Eltern, , während Charlie Knoten hat 3 Kinder und 1 Elternteil. 

Ein Blattknoten ist einer, der keine Kinder am Außenrand des Baumes. Der oberste Knoten des Baumes, der Wurzelknoten, hat keine Eltern. 

Ein binärer Baum ist eine bestimmte Art des Baumes, in denen jeder Knoten, höchstens zwei Kinder. Hier ist die Struktur eines Knotens eines binären Baums in C. Jeder Knoten hat einige Daten zugeordnet und zwei Zeiger zu anderen Knoten. 

In unserem Stammbaum, die zugehörigen Daten wurde jede Person den Namen. Hier ist es ein int, obwohl es nichts sein könnte. Wie es sich herausstellt, ein binärer Baum wäre keine gute Darstellung für eine Familie zu sein, da die Menschen haben oft mehr als 2 Kinder. 

Ein binärer Suchbaum ist eine spezielle, geordnete Art von binären Baum das ermöglicht es uns, auf die Werte schnell zu suchen. Sie haben vielleicht bemerkt haben dass jeder Knoten unter der Wurzel eines Baums ist die Wurzel eines anderen Baumes, eine so genannte "Teilbaum. Hier ist die Wurzel des Baumes 6, und ihr Kind, 2, ist die Wurzel eines Teilbaums. 

In einem binären Suchbaum alle Werte eines Knotens ist richtig Teilbaum größer sind als die des Knotens Wert. Hier: 6. Nun, die Werte in einem Knoten der linken Teilbaum weniger als Wert des Knotens. Wenn wir brauchen, um doppelte Werte zu behandeln, können wir entweder derjenigen ändern, um eine lose Ungleichheit, dh identische Werte können entweder fallen auf der linken oder rechten, Solange wir konsequent darüber sind überall. Dieser Baum ist ein binärer Suchbaum weil es folgt diesen Regeln. 

Dies ist, wie es aussehen würde, wenn wir alle Knoten verwandelte sich in C Strukturen. Beachten Sie, dass, wenn ein Kind fehlt, der Zeiger ist null. Wie können wir überprüfen, ob 7 ist in dem Baum? Wir beginnen an der Wurzel. Seven ist größer als 6, also wenn es in dem Baum ist, muss es auf der rechten Seite. Dann ist es weniger als 8 ist, so muss es überlassen bleiben. Hier haben wir 7 gefunden. Jetzt werden wir für 5 zu überprüfen. Fünf kleiner als 6, so wird sie auf der linken Seite. Fünf größer als 2 ist, so muss es sein Recht, und es ist auch größer als 4, so muss es wieder gut. Es besteht jedoch kein Kind hier. Der Zeiger ist null. Dies bedeutet, dass 5 nicht in unserem Baum. 

Wir können die binären Baum mit dem folgenden Code suchen: An jedem Knoten, prüfen wir, ob wir gefunden haben, der Wert, den wir suchen. Wenn wir es nicht finden, bestimmen wir, wenn es sein sollte auf der linken oder rechten und prüfen Sie, ob Teilbaum. Diese Schleife wird weiterhin den Baum bis kein Kindknoten entweder an der linken oder rechten Seite. 

Beachten Sie, dass 5 nicht in den Baum. Wie setzen wir das? Der Prozess ähnelt suchen. Wir durchlaufen den Baum ab 6, links bis 2, rechts bis 4, und gleich wieder rechts, aber 4 hat kein Kind auf dieser Seite. Dies wird die neue Position für 5 sein kann, und es wird ohne Kinder beginnen. 

Wie schnell sind Operationen auf einem binären Suchbaum? Beachten Sie, dass Bigohnotation um eine obere Schranke erbringen will. Im ungünstigsten Fall, unser Baum könnte einfach eine verknüpfte Liste sein was bedeutet, dass Einfügen, Löschen und Suchen könnte Zeit proportional zu der Anzahl von Knoten im Baum zu nehmen. Dies ist O (n). 

Zum Beispiel ist das Folgende eine gültige binäre Suchbaum. Allerdings, wenn wir versuchen, 9 zu finden, wir müssen jeden Knoten durchqueren. Es ist nicht besser als eine verknüpfte Liste. Idealerweise würden wir wollen, dass jeder Knoten unserer binären Suchbaum zu haben 2 Kinder. Auf diese Weise, Einfügen, Löschen und suchen dauern würde, im schlimmsten Fall O (log n) Zeit. Der Baum aus der Zeit vor könnte ausgeglichener, wie diese. Nun blickte jeden Wert nimmt, höchstens 3 Schritten. Dieser Baum ist ausgeglichen, Bedeutung, ist eine minimale Tiefe bezogen auf die Anzahl von Knoten. 

Suche nach einem Wert in einem ausgewogenen binären Suchbaum ist ähnlich wie binäre Suche auf einem sortierten Array. In der Tat, wenn wir nicht brauchen, einfügen oder löschen, sie verhalten sich genau die gleiche Weise. Jedoch ist eine Baumstruktur bessere für den Umgang mit Insertionen und Deletionen 

Mein Name ist Bannus Van der Kloot. Dies ist CS50.