Bevor wir uns über die Unterschiede zwischen dem binären Suchbaum und dem AVL-Baum informieren, sollten wir den binären Suchbaum und den AVL-Baum getrennt kennen.
Was ist ein binärer Suchbaum?
Der binärer Suchbaum ist ein Baum Binärbaum. Wie wir wissen, kann dieser Baum eine Anzahl von Kindern haben, wohingegen; Der Binärbaum kann maximal zwei Kinder enthalten. Der Einschränkung eines Binärbaums folgt also auch der binäre Suchbaum. Jeder Knoten in einem binären Suchbaum sollte maximal zwei untergeordnete Knoten haben; Mit anderen Worten: Wir können sagen, dass der binäre Suchbaum eine Variante des binären Baums ist.
Auch der binäre Suchbaum folgt den Eigenschaften der binären Suche. Bei der binären Suche müssen alle Elemente in einem Array in sortierter Reihenfolge vorliegen. Wir berechnen das mittlere Element in der binären Suche, wobei der linke Teil des mittleren Elements den Wert enthält, der kleiner als der mittlere Wert ist, und der rechte Teil des mittleren Elements die Werte enthält, die größer als der mittlere Wert sind.
Im binären Suchbaum wird das mittlere Element zum Wurzelknoten, der rechte Teil zum rechten Teilbaum und der linke Teil zum linken Teilbaum. Daher können wir sagen, dass der binäre Suchbaum eine Kombination aus a ist Binärbaum Und binäre Suche .
Hinweis: Der binäre Suchbaum kann als Binärbaum definiert werden, in dem alle Elemente des linken Teilbaums kleiner als der Wurzelknoten und alle Elemente des rechten Teilbaums größer als der Wurzelknoten sind.
Zeitkomplexität im binären Suchbaum
Wenn der binäre Suchbaum nahezu ein ausgeglichener Baum ist, haben alle Operationen eine zeitliche Komplexität von O(logn) weil die Suche entweder in den linken oder rechten Teilbaum unterteilt ist.
Java-String zum Zeichen
Wenn der binäre Suchbaum entweder links- oder rechtsschief ist, haben alle Operationen die zeitliche Komplexität von An) weil wir bis zu den n Elementen durchlaufen müssen.
Was ist der AVL-Baum?
Ein AVL-Baum ist ein selbstausgleichender binärer Suchbaum, bei dem der Unterschied zwischen den Höhen des linken und rechten Teilbaums nicht mehr als eins betragen darf. Dieser Unterschied wird als Balancefaktor bezeichnet. Im AVL-Baum können die Werte des Ausgleichsfaktors entweder -1, 0 oder 1 sein.
Wie erfolgt der Selbstausgleich des binären Suchbaums?
Wie wir wissen, ist der AVL-Baum ein selbstausgleichender binärer Suchbaum. Wenn der binäre Suchbaum nicht ausgeglichen ist, kann er durch einige Neuanordnungen selbst ausgeglichen werden. Diese Neuanordnungen können durch einige Rotationen erfolgen.
Lassen Sie uns den Selbstausgleich anhand eines Beispiels verstehen.
Angenommen, wir möchten einfügen 10, 20, 30 in einem AVL-Baum.
Es gibt folgende Möglichkeiten, 10, 20, 30 in einen AVL-Baum einzufügen:
Schritt 1: Zuerst erstellen wir einen binären Suchbaum, wie unten gezeigt:
Schritt 2: In der obigen Abbildung können wir beobachten, dass der Baum unausgeglichen ist, da der Gleichgewichtsfaktor von Knoten 30 2 beträgt. Um daraus einen AVL-Baum zu machen, müssen wir einige Rotationen durchführen. Wenn wir den Knoten 20 nach rechts drehen, bewegt sich der Knoten 30 nach unten, während sich der Knoten 20 nach oben bewegt, wie unten gezeigt:
Zeile und Spalte
Wie wir beobachten können, folgt der endgültige Baum den Eigenschaften des binären Suchbaums und eines ausgeglichenen Baums; daher handelt es sich um einen AVL-Baum.
In dem Fall war der Baum einen unausgeglichenen Baum hinterlassen, Also führen wir die richtige Drehung am Knoten durch.
Schritt 1: Zuerst erstellen wir einen binären Suchbaum wie unten gezeigt:
Schritt 2: In der obigen Abbildung können wir beobachten, dass der Baum unausgeglichen ist, da der Gleichgewichtsfaktor von Knoten 10 -2 beträgt. Um daraus einen AVL-Baum zu machen, müssen wir einige Rotationen durchführen. Da es sich um einen nach rechts unausgeglichenen Baum handelt, führen wir eine Linksdrehung durch. Wenn wir Knoten 20 nach links drehen, bewegt sich Knoten 20 nach oben und Knoten 10 nach unten, wie unten gezeigt:
Wie wir beobachten können, folgt der endgültige Baum der Eigenschaft von Binärer Suchbaum und ein ausgeglichener Baum ; daher handelt es sich um einen AVL-Baum.
Schritt 1: Zuerst erstellen wir den binären Suchbaum wie unten gezeigt:
Rudyard Kipling, wenn Erklärung
Schritt 2: In der obigen Abbildung können wir beobachten, dass der Baum unausgeglichen ist, da der Ausgleichsfaktor des Wurzelknotens 2 beträgt. Um daraus einen AVL-Baum zu machen, müssen wir einige Rotationen durchführen. Das obige Szenario ist von links nach rechts unausgeglichen, da sich ein Knoten links von seinem übergeordneten Knoten und ein anderer rechts von seinem übergeordneten Knoten befindet. Zuerst führen wir die Linksdrehung durch, und die Drehung erfolgt zwischen den Knoten 10 und 20. Nach der Linksdrehung bewegt sich 20 nach oben und 10 nach unten, wie unten gezeigt:
Dennoch ist der Baum unausgeglichen, also führen wir die richtige Drehung am Baum durch. Sobald die richtige Drehung am Baum durchgeführt wurde, würde der Baum wie folgt aussehen:
Wie wir im obigen Baum beobachten können, folgt der Baum den Eigenschaften des binären Suchbaums und eines ausgeglichenen Baums; daher handelt es sich um einen AVL-Baum.
Schritt 1: Zuerst erstellen wir den binären Suchbaum, wie unten gezeigt:
Schritt 2: In der obigen Abbildung können wir beobachten, dass der Baum unausgeglichen ist, da der Ausgleichsfaktor des Wurzelknotens 2 beträgt. Um daraus einen AVL-Baum zu machen, müssen wir einige Rotationen durchführen. Das obige Szenario ist rechts-links-unausgeglichen, da sich ein Knoten rechts von seinem übergeordneten Knoten und ein anderer Knoten links von seinem übergeordneten Knoten befindet. Zuerst führen wir die Rechtsdrehung durch, die zwischen den Knoten 30 und 20 stattfindet. Nach der Rechtsdrehung bewegt sich 20 nach oben und 30 nach unten, wie unten gezeigt:
Dennoch ist der obige Baum unausgeglichen, daher müssen wir eine Linksdrehung des Knotens durchführen. Sobald die Linksdrehung ausgeführt wird, bewegt sich Knoten 20 nach oben und Knoten 10 nach unten, wie unten gezeigt:
Wie wir im obigen Baum beobachten können, folgt der Baum den Eigenschaften des binären Suchbaums und eines ausgeglichenen Baums; daher handelt es sich um einen AVL-Baum.
Unterschiede zwischen binärem Suchbaum und AVL-Baum
| Binärer Suchbaum | AVL-Baum |
|---|---|
| Jeder binäre Suchbaum ist ein binärer Baum, da beide Bäume die höchsten zwei Kinder enthalten. | Jeder AVL-Baum ist auch ein Binärbaum, da der AVL-Baum auch die beiden höchsten Kinder hat. |
| In BST gibt es keinen Begriff wie z. B. Ausgleichsfaktor. | Im AVL-Baum enthält jeder Knoten einen Ausgleichsfaktor und der Wert des Ausgleichsfaktors muss entweder -1, 0 oder 1 sein. |
| Jeder binäre Suchbaum ist kein AVL-Baum, da BST entweder ein ausgeglichener oder ein unausgeglichener Baum sein kann. | Jeder AVL-Baum ist ein binärer Suchbaum, da der AVL-Baum der Eigenschaft des BST folgt. |
| Jeder Knoten im binären Suchbaum besteht aus drei Feldern, nämlich dem linken Teilbaum, dem Knotenwert und dem rechten Teilbaum. | Jeder Knoten im AVL-Baum besteht aus vier Feldern, nämlich dem linken Teilbaum, dem Knotenwert, dem rechten Teilbaum und dem Ausgleichsfaktor. |
| Wenn wir im Fall eines binären Suchbaums einen beliebigen Knoten in den Baum einfügen möchten, vergleichen wir den Knotenwert mit dem Stammwert. Wenn der Wert des Knotens größer als der Wert des Wurzelknotens ist, wird der Knoten in den rechten Teilbaum eingefügt, andernfalls wird der Knoten in den linken Teilbaum eingefügt. Sobald der Knoten eingefügt ist, muss der Höhenausgleichsfaktor nicht mehr überprüft werden, damit das Einfügen abgeschlossen ist. | Im Falle eines AVL-Baums suchen wir zunächst nach der geeigneten Stelle zum Einfügen des Knotens. Sobald der Knoten eingefügt ist, berechnen wir den Ausgleichsfaktor jedes Knotens. Wenn der Ausgleichsfaktor jedes Knotens erfüllt ist, ist die Einfügung abgeschlossen. Wenn der Ausgleichsfaktor größer als 1 ist, müssen wir einige Drehungen durchführen, um den Baum auszugleichen. |
| Im binären Suchbaum beträgt die Höhe oder Tiefe des Baums O(n), wobei n die Anzahl der Knoten im binären Suchbaum ist. | Im AVL-Baum beträgt die Höhe oder Tiefe des Baums O(logn). |
| Die Implementierung ist einfach, da wir den Eigenschaften der binären Suche folgen müssen, um den Knoten einzufügen. | Die Implementierung ist komplex, da wir im AVL-Baum zuerst den AVL-Baum erstellen und dann den Höhenausgleich überprüfen müssen. Wenn die Höhe unausgeglichen ist, müssen wir einige Drehungen durchführen, um den Baum auszubalancieren. |
| BST ist kein ausgeglichener Baum, da er nicht dem Konzept des Gleichgewichtsfaktors folgt. | Der AVL-Baum ist ein höhenausgeglichener Baum, da er dem Konzept des Gleichgewichtsfaktors folgt. |
| Die Suche ist in BST ineffizient, wenn im Baum eine große Anzahl verfügbarer Knoten vorhanden ist, da die Höhe nicht ausgeglichen ist. | Die Suche im AVL-Baum ist auch dann effizient, wenn der Baum eine große Anzahl von Knoten enthält, da die Höhe ausgeglichen ist. |