Ein ausgeglichener Binärbaum wird auch als höhenbalancierter Baum bezeichnet. Er wird als binärer Baum definiert, wenn der Unterschied zwischen der Höhe des linken Teilbaums und des rechten Teilbaums nicht mehr als m beträgt, wobei m normalerweise gleich 1 ist. Die Höhe eines Baums ist die Anzahl der Kanten auf dem längsten Pfad zwischen den Wurzelknoten und Blattknoten.
Der obige Baum ist ein binärer Suchbaum . Ein binärer Suchbaum ist ein Baum, in dem jeder Knoten auf der linken Seite einen niedrigeren Wert als sein übergeordneter Knoten hat und der Knoten auf der rechten Seite einen höheren Wert als sein übergeordneter Knoten hat. Im obigen Baum ist n1 ein Wurzelknoten und n4, n6, n7 sind die Blattknoten. Der n7-Knoten ist der am weitesten vom Wurzelknoten entfernte Knoten. n4 und n6 enthalten zwei Kanten und es gibt drei Kanten zwischen dem Wurzelknoten und dem Knoten n7. Da n7 am weitesten vom Wurzelknoten entfernt ist; Daher beträgt die Höhe des obigen Baums 3.
Jetzt werden wir sehen, ob der obige Baum ausgeglichen ist oder nicht. Der linke Teilbaum enthält die Knoten n2, n4, n5 und n7, während der rechte Teilbaum die Knoten n3 und n6 enthält. Der linke Teilbaum hat zwei Blattknoten, nämlich n4 und n7. Es gibt nur eine Kante zwischen den Knoten n2 und n4 und zwei Kanten zwischen den Knoten n7 und n2; Daher ist Knoten n7 am weitesten vom Wurzelknoten entfernt. Die Höhe des linken Teilbaums beträgt 2. Der rechte Teilbaum enthält nur einen Blattknoten, d. h. n6, und hat nur eine Kante; Daher beträgt die Höhe des rechten Teilbaums 1. Der Unterschied zwischen den Höhen des linken Teilbaums und des rechten Teilbaums beträgt 1. Da wir den Wert 1 erhalten haben, können wir sagen, dass der obige Baum ein Baum mit ausgeglichener Höhe ist. Dieser Prozess der Berechnung der Differenz zwischen den Höhen sollte für jeden Knoten wie n2, n3, n4, n5, n6 und n7 durchgeführt werden. Wenn wir jeden Knoten verarbeiten, werden wir feststellen, dass der Wert von k nicht mehr als 1 beträgt, sodass wir sagen können, dass der obige Baum ausgeglichen ist Binärbaum .
Im obigen Baum sind n6, n4 und n3 die Blattknoten, wobei n6 der Knoten ist, der am weitesten vom Wurzelknoten entfernt ist. Zwischen dem Wurzelknoten und dem Blattknoten existieren drei Kanten; Daher beträgt die Höhe des obigen Baums 3. Wenn wir n1 als Wurzelknoten betrachten, enthält der linke Teilbaum die Knoten n2, n4, n5 und n6, während der Teilbaum den Knoten n3 enthält. Im linken Teilbaum ist n2 ein Wurzelknoten und n4 und n6 sind Blattknoten. Unter den Knoten n4 und n6 ist n6 der Knoten, der am weitesten von seinem Wurzelknoten entfernt ist, und n6 hat zwei Kanten; Daher beträgt die Höhe des linken Teilbaums 2. Der rechte Teilbaum hat links und rechts ein Kind; Daher beträgt die Höhe des rechten Teilbaums 0. Da die Höhe des linken Teilbaums 2 und die des rechten Teilbaums 0 beträgt, beträgt der Unterschied zwischen der Höhe des linken Teilbaums und des rechten Teilbaums 2. Gemäß der Definition ist der Unterschied zwischen der Höhe des linken Teilbaums und des rechten Teilbaums darf nicht größer als 1 sein. In diesem Fall beträgt die Differenz 2, was größer als 1 ist; Daher ist der obige Binärbaum ein unausgeglichener binärer Suchbaum.
Warum brauchen wir einen ausgeglichenen Binärbaum?
Lassen Sie uns die Notwendigkeit eines ausgewogenen Binärbaums anhand eines Beispiels verstehen.
Der obige Baum ist ein binärer Suchbaum, da alle linken Teilbaumknoten kleiner als sein übergeordneter Knoten und alle rechten Teilbaumknoten größer als sein übergeordneter Knoten sind. Angenommen, wir möchten den Wert 79 im obigen Baum finden. Zuerst vergleichen wir den Wert von Knoten n1 mit 79; Da der Wert von 79 nicht gleich 35 und größer als 35 ist, bewegen wir uns zum Knoten n3, also 48. Da der Wert 79 nicht gleich 48 ist und 79 größer als 48 ist, bewegen wir uns nach rechts Kind von 48. Der Wert des rechten Kindes von Knoten 48 ist 79, was dem zu suchenden Wert entspricht. Die Anzahl der erforderlichen Sprünge zum Durchsuchen eines Elements 79 beträgt 2 und die maximale Anzahl der erforderlichen Sprünge zum Durchsuchen eines beliebigen Elements beträgt 2. Der durchschnittliche Fall zum Durchsuchen eines Elements ist O(logn).
Der obige Baum ist auch ein binärer Suchbaum, da alle linken Teilbaumknoten kleiner als sein übergeordneter Knoten und alle rechten Teilbaumknoten größer als sein übergeordneter Knoten sind. Angenommen, wir möchten den Wert 79 im obigen Baum finden. Zuerst vergleichen wir den Wert 79 mit einem Knoten n4, also 13. Da der Wert 79 größer als 13 ist, gehen wir zum rechten Kind von Knoten 13, also n2 (21). Der Wert des Knotens n2 ist 21, was kleiner als 79 ist, also bewegen wir uns wieder nach rechts von Knoten 21. Der Wert des rechten untergeordneten Knotens von Knoten 21 ist 29. Da der Wert 79 größer als 29 ist, bewegen wir uns nach rechts Kind von Knoten 29. Der Wert des rechten Kindes von Knoten 29 ist 35, was kleiner als 79 ist, also bewegen wir uns zum rechten Kind von Knoten 35, d. h. 48. Der Wert 79 ist größer als 48, also bewegen wir uns zum rechten Kind von Knoten 48. Der Wert des rechten untergeordneten Knotens von 48 ist 79, was dem zu suchenden Wert entspricht. In diesem Fall beträgt die Anzahl der zum Durchsuchen eines Elements erforderlichen Sprünge 5. In diesem Fall ist O(n) der ungünstigste Fall.
Wenn die Anzahl der Knoten zunimmt, ist die im Baumdiagramm1 verwendete Formel effizienter als die im Baumdiagramm2 verwendete Formel. Angenommen, die Anzahl der in beiden oben genannten Bäumen verfügbaren Knoten beträgt 100.000. Für die Suche nach einem beliebigen Element in einem Baumdiagramm2 wird eine Zeit von 100.000 µs benötigt, während die Zeit für die Suche nach einem Element in einem Baumdiagramm log(100.000) beträgt, was 16,6 µs entspricht. Wir können den enormen Zeitunterschied zwischen den beiden oben genannten Bäumen beobachten. Daher kommen wir zu dem Schluss, dass der Balance-Binärbaum eine schnellere Suche ermöglicht als die lineare Baumdatenstruktur.