AVL-Baum Java-javaLernprogramm-php.cn

Der AVL-Baum ist auch als selbstausgleichender Binärbaum bekannt, der zum Ausgleichen und Berechnen der Differenz zwischen den jeweiligen Höhen des linken und rechten Teilbaums verwendet wird, wobei das Ergebnis im gesamten ausgeglichenen Baum nicht mehr als eins sein kann. Die binäre Suchbaumoperation ermöglicht das Einfügen, Löschen, Suchen sowie Max- und Min-Operationen, die auch als Teil des AVL-Baums erforderlich sind. Alle diese Vorgänge gelten als kostspielige Angelegenheit, weshalb die damit verbundene Kosten- und Zeitkomplexität beibehalten werden kann, wenn der Unterschied zwischen den Höhen aller BST beibehalten wird.

Starten Sie Ihren kostenlosen Softwareentwicklungskurs

Webentwicklung, Programmiersprachen, Softwaretests und andere

Syntax:

Es gibt keine eigentlich richtige Syntax, aber bei der Implementierung in Java wird der AVL-Baum als Datenstruktur betrachtet, in der die Syntax wie folgt dargestellt wird:

Class Node_demo
{
int key, height_0;
Node left, right;
Node_demo (int d_1)
{
key = d_1;
height_0 = 1;
}
}
class AVLTree_demo1 {
Node root_0;
int height_0(Node N_1) {
if (N_1== null)
return 0;
return N_1.height;
}

Nach dem Login kopieren

Erklärung:

Im Syntaxablauf enthält die Klasse Node_demo hier Schlüssel, Höhe und Struktur, die das Schlüssel-Wert-Paar beschreibt, in dem die Elemente gespeichert werden. Gefolgt vom AVL_Tree demo_1-Knoten, der den Wurzelknoten und die zugehörigen Elemente mit Wertepaaren enthält, deren Höhe überall beizubehalten ist, wobei die Werte Null sind.

Wie funktioniert der AVL-Baum in Java?

Es gibt einen ordnungsgemäßen Ablauf, bei dem der AVL-Baum in Java funktioniert und 1962 von GM Adelson erfunden wurde.
AVL-Baum ist als höhenbalancierter binärer Suchbaum definiert, in dem jedem Knoten ein Ausgleichsfaktor zugeordnet ist, der durch Subtrahieren der Höhe seines rechten Teilbaums von der seines linken Teilbaums berechnet wird.
Ein Baum wird als ausgeglichen bezeichnet, wenn der Ausgleichsfaktor zwischen -1 und 1 liegt. Andernfalls muss der Baum von oben nach unten ausgeglichen werden.
Da der Balance-Baum die Höhe des binären Suchbaums steuert, beträgt die Höhe O(h), wohingegen es eine Bestimmung gibt, bei der es erforderlich ist, den binären Suchbaum zu erweitern, sobald er verzerrt ist, als in diesem Fall ergibt sich aufgrund seiner Manipulation als (n-1).
Sobald der verzerrte Baum begrenzt wird, legt er in diesem Fall eine Obergrenze für alle Operationen fest, die als O (log n) ausgegeben werden, wobei n die Anzahl der Knoten ist.
Es gibt auch Möglichkeiten, den AVL-Baum zu drehen, und dies geschieht nur unter einer Bedingung, wenn der Gleichgewichtsfaktor zwischen -1, 1 oder 0 liegt.
Es gibt vier Arten von Rotationen:
LL-Rotationen: Knoten wird eingefügt, wenn er im linken Teilbaum des Baums mit Knoten D liegt.
RR-Rotationen: Knoten wird eingefügt, wenn er im rechten Teilbaum des Baums mit Knoten D liegt.
LR-Rotationen: Knoten wird eingefügt, wenn er in den rechten Teilbaum eines linken Teilbaums mit Knoten D eingefügt wird.
RL-Rotationen: Knoten wird eingefügt, wenn er in den linken Teilbaum eines rechten Teilbaums mit Knoten D eingefügt wird.

Wobei D für den Knoten steht, dessen Höhe und Balancefaktor anders als -1, 1 und 0 liegen, weshalb alle diese Drehungen erforderlich sind, um sie in das richtige Format zu bringen.

Es gibt viele Operationen, und dafür müssen die richtigen Rotationen mit der richtigen Analyse zur Manipulation vorhanden sein.

Beispiel: Dieses Beispiel zeigt den AVL-Baum, bei dem die Einfügung, linke und rechte Einfügung mit einer Vorbestellungs-, Nachbestellungs- und Levelorder-Darstellung erfolgt, wie in der Ausgabe unten gezeigt.

import java. util.LinkedList;
import java.util.Queue;
class Node_8 {
int data_0, height_1;
Node_8 left_nd_0;
Node_8 right_nd_0;
Node_8(int d_2) {
data_0 = d_2;
height_1 = 1;
}
}
public class AVLTree_Demo
{
Node_8 root_0;
int height_1(Node_8 N) {
if (N == null)
return 0;
return N.height_1;
}
int max_2(int a_0,  int b_0) {
return (a_0 > b_0) ? a_0 : b_0;
}
Node_8 rightRotation_mode(Node_8 oldRoot_0) {
Node_8 newRoot_0 = oldRoot_0.left_nd_0;
Node_8 temp_0 = newRoot_0.right_nd_0;
newRoot_0.right_nd_0 = oldRoot_0;
oldRoot_0.left_nd_0 = temp_0;
newRoot_0.height_1 = max_2(height_1(newRoot_0.left_nd_0), height_1(newRoot_0.right_nd_0)) + 1;
oldRoot_0.height_1 = max_2(height_1(oldRoot_0.left_nd_0), height_1(oldRoot_0.right_nd_0)) + 1;
return newRoot_0;
}
Node_8 leftRotation_mode(Node_8 oldRoot_0) {
Node_8 newRoot_0 = oldRoot_0.right_nd_0;
Node_8 temp_0 = newRoot_0.left_nd_0;
newRoot_0.left_nd_0 = oldRoot_0;
oldRoot_0.right_nd_0 = temp_0;
newRoot_0.height_1 = max_2(height_1(newRoot_0.left_nd_0), height_1(newRoot_0.right_nd_0)) + 1;
oldRoot_0.height_1=max_2(height_1(oldRoot_0.left_nd_0), height_1(oldRoot_0.right_nd_0)) + 1;
return newRoot_0;
}
int balFactor_c(Node_8 root_0) {
if(root_0 == null)
return 0;
return height_1(root_0.left_nd_0) - height_1(root_0.right_nd_0);
}
Node_8 insert(Node_8 root_0, int data_0) {
if(root_0 == null)
return new Node_8(data_0);
else if(data_0 < root_0.data_0)
root_0.left_nd_0 = insert(root_0.left_nd_0, data_0);
else if(data_0 > root_0.data_0)
root_0.right_nd_0 = insert(root_0.right_nd_0, data_0);
else
return root_0;
root_0.height_1= max_2(height_1(root_0.left_nd_0), height_1(root_0.right_nd_0)) + 1;
int bal = balFactor_c(root_0);
if(bal > 1 && data_0 < root_0.left_nd_0.data_0)
return rightRotation_mode(root_0);
if(bal < -1 && data_0 > root_0.right_nd_0.data_0)
return leftRotation_mode(root_0);
if(bal > 1 && data_0 > root_0.left_nd_0.data_0) {
root_0.left_nd_0 = leftRotation_mode(root_0.left_nd_0);
return rightRotation_mode(root_0);
}
if(bal < -1 && data_0 < root_0.right_nd_0.data_0) {
root_0.right_nd_0 = rightRotation_mode(root_0.right_nd_0);
return leftRotation_mode(root_0);
}
return root_0;
}
void preOrder_traversal(Node_8 node) {
if (node != null) {
System.out.print(node.data_0 + " ");
preOrder_traversal(node.left_nd_0);
preOrder_traversal(node.right_nd_0);
}
}
void levelOrder_traversal(Node_8 root) {
Queue<Node_8> q_1 = new LinkedList<Node_8>();
q_1.add(root);
while(!q_1.isEmpty()) {
Node_8 current = q_1.peek();
System.out.print(current.data_0 + " ");
if(current.left_nd_0 != null)
q_1.add(current.left_nd_0);
if(current.right_nd_0 != null)
q_1.add(current.right_nd_0);
q_1.poll();
}
}
public static void main (String args[]) {
AVLTree_Demo tree = new AVLTree_Demo ();
tree. root_0 = tree.insert(tree.root_0, 15);
tree.root_0 = tree.insert(tree.root_0, 20);
tree.root_0 = tree.insert(tree.root_0, 19);
tree.root_0 = tree.insert(tree.root_0, 40);
tree.root_0 = tree.insert(tree.root_0, 50);
tree.root_0 = tree.insert(tree.root_0, 25);
System.out.println("order_of_Preorder_traversal_representation : ");
tree.preOrder_traversal(tree.root_0);
System.out.println();
System.out.println("Levelorder_of_traversal_representation : ");
tree.levelOrder_traversal(tree.root_0);
}
}

Nach dem Login kopieren

Ausgabe:

AVL-Baum Java

Erklärung: Dieses Programm führt das Einfügen von Elementen in den AVL-Baumbeitrag durch, bei dem eine gewisse Ordnung besteht, wobei einige Prüfungen durchgeführt werden, z. B. ob die aufgenommene Liste leer ist oder nicht und dann, ob der AVL-Baum leer ist Rotationen, die in einem Vorbestellungs-, Nachbestellungs- oder Level-Bestellformat durchgeführt werden sollen. Alle angegebenen Elemente nehmen automatisch Eingaben entgegen und ordnen sie in der richtigen Reihenfolge an.

Fazit

Der AVL-Baum in Java wird als geeignete Datenstruktur verwendet, die vielen Entwicklern gefällt, da sie einen Vorteil in Bezug auf den Betrieb bietet und dabei hilft, Zeit und Komplexität zu sparen und zu verbrauchen, die durch eine große Menge an Codes entsteht. Der AVL-Baum ist in der Lage, wichtige Vorgänge wie Einfügen, Löschen, Drehen und Entfernen aus den gesamten Teilbäumen durchzuführen, wenn die Höhen ordnungsgemäß beibehalten werden.

Das obige ist der detaillierte Inhalt vonAVL-Baum Java. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!