AVL-Baum

In diesem Tutorial erfahren Sie, was ein AVL-Baum ist. Außerdem finden Sie Arbeitsbeispiele für verschiedene Operationen, die an einem AVL-Baum in C, C ++, Java und Python ausgeführt werden.

Der AVL-Baum ist ein selbstausgleichender binärer Suchbaum, in dem jeder Knoten zusätzliche Informationen verwaltet, die als Ausgleichsfaktor bezeichnet werden und deren Wert entweder -1, 0 oder +1 ist.

Der AVL-Baum erhielt seinen Namen nach seinen Erfindern Georgy Adelson-Velsky und Landis.

Ausgleichsfaktor

Der Ausgleichsfaktor eines Knotens in einem AVL-Baum ist die Differenz zwischen der Höhe des linken Teilbaums und der des rechten Teilbaums dieses Knotens.

Balance Factor = (Höhe des linken Teilbaums - Höhe des rechten Teilbaums) oder (Höhe des rechten Teilbaums - Höhe des linken Teilbaums)

Die selbstausgleichende Eigenschaft eines avl-Baums wird durch den Ausgleichsfaktor aufrechterhalten. Der Wert des Ausgleichsfaktors sollte immer -1, 0 oder +1 sein.

Ein Beispiel für einen ausgeglichenen AVL-Baum ist:

Avl Baum

Operationen an einem AVL-Baum

Verschiedene Operationen, die an einem AVL-Baum ausgeführt werden können, sind:

Drehen der Teilbäume in einem AVL-Baum

Im Rotationsbetrieb werden die Positionen der Knoten eines Teilbaums vertauscht.

Es gibt zwei Arten von Rotationen:

Links drehen

Bei der Linksdrehung wird die Anordnung der Knoten auf der rechten Seite in die Anordnung auf dem linken Knoten umgewandelt.

Algorithmus

Der ursprüngliche Baum sei: Links drehen
Wenn y einen linken Teilbaum hat, weisen Sie x als übergeordnetes Element des linken Teilbaums von y zu. Weisen Sie x als übergeordnetes Element des linken Teilbaums von y zu
Wenn das übergeordnete Element von x ist NULL, machen Sie y als Wurzel des Baums.
Andernfalls, wenn x das linke Kind von p ist, machen Sie y als das linke Kind von p.
Andernfalls weisen Sie y als das richtige Kind von p zu. Ändern Sie das übergeordnete Element von x in das von y
Machen Sie y zum übergeordneten Element von x. Weisen Sie y als übergeordnetes Element von x zu.

Rechts drehen

Bei der Linksdrehung wird die Anordnung der Knoten auf der linken Seite in die Anordnung auf dem rechten Knoten umgewandelt.

Der Anfangsbaum sei: Anfangsbaum
Wenn x einen rechten Teilbaum hat, weisen Sie y als übergeordnetes Element des rechten Teilbaums von x zu. Weisen Sie y als übergeordnetes Element des rechten Teilbaums von x zu
Wenn das übergeordnete Element von y ist NULL, machen Sie x als Wurzel des Baums.
Andernfalls, wenn y das richtige Kind seines Elternteils p ist, machen Sie x zum richtigen Kind von p.
Andernfalls weisen Sie x als linkes Kind von p zu. Weisen Sie das übergeordnete Element von y dem übergeordneten Element von x zu.
Machen Sie x zum übergeordneten Element von y. Weisen Sie x als übergeordnetes Element von y zu

Links-rechts und rechts-links drehen

Bei der Links-Rechts-Drehung werden die Anordnungen zuerst nach links und dann nach rechts verschoben.

Drehe links auf xy. Links xy drehen
Drehe rechts auf yz. Rechts drehen zy

Bei der Drehung von rechts nach links werden die Anordnungen zuerst nach rechts und dann nach links verschoben.

Drehe rechts auf xy. Rechts xy drehen
Drehung nach links auf zy. Links zy drehen

Algorithmus zum Einfügen eines neuen Knotens

Ein neuer Knoten wird immer als Blattknoten mit einem Ausgleichsfaktor von 0 eingefügt.

Der Anfangsbaum sei: Anfangsbaum zum Einfügen
Sei der einzufügende Knoten : Neuer Knoten
Wechseln Sie mit den folgenden rekursiven Schritten zum entsprechenden Blattknoten, um einen neuen Knoten einzufügen. Vergleichen Sie newKey mit rootKey des aktuellen Baums.
1. Wenn newKey <rootKey, rufen Sie den Einfügealgorithmus im linken Teilbaum des aktuellen Knotens auf, bis der Blattknoten erreicht ist.
2. Andernfalls rufen Sie bei newKey> rootKey den Einfügealgorithmus im rechten Teilbaum des aktuellen Knotens auf, bis der Blattknoten erreicht ist.
3. Andernfalls geben Sie leafNode zurück. Suchen des Speicherorts zum Einfügen von newNode
Vergleichen Sie leafKey aus den obigen Schritten mit newKey:
1. Wenn newKey <leafKey, machen Sie newNode als leftChild von leafNode.
2. Andernfalls machen Sie newNode als rightChild von leafNode. Einfügen des neuen Knotens
Aktualisieren Sie balanceFactor der Knoten. Aktualisieren des Ausgleichsfaktors nach dem Einfügen
Wenn die Knoten nicht ausgeglichen sind, gleichen Sie den Knoten neu aus.
1. Wenn balanceFactor> 1 ist, bedeutet dies, dass die Höhe des linken Teilbaums größer ist als die des rechten Teilbaums. Führen Sie also eine Rechts- oder Links-Rechts-Drehung durch
  1. Wenn newNodeKey <leftChildKey, drehen Sie nach rechts.
  2. Andernfalls drehen Sie von links nach rechts. Balancieren des Baums mit Rotation Balancieren des Baums mit Rotation
2. Wenn balanceFactor <-1 ist, bedeutet dies, dass die Höhe des rechten Teilbaums größer ist als die des linken Teilbaums. Drehen Sie also nach rechts oder rechts nach links
  1. Wenn newNodeKey> rightChildKey, drehen Sie nach links.
  2. Andernfalls drehen Sie sich von rechts nach links
Der letzte Baum ist: Endlicher ausgeglichener Baum

Algorithmus zum Löschen eines Knotens

Ein Knoten wird immer als Blattknoten gelöscht. Nach dem Löschen eines Knotens werden die Ausgleichsfaktoren der Knoten geändert. Um den Ausgleichsfaktor auszugleichen, werden geeignete Rotationen durchgeführt.

Suchen Sie nodeToBeDeleted (die Rekursion wird verwendet, um nodeToBeDeleted im unten verwendeten Code zu finden). Suchen des zu löschenden Knotens
Es gibt drei Fälle zum Löschen eines Knotens:
1. Wenn nodeToBeDeleted der Blattknoten ist (dh kein untergeordnetes Element hat), entfernen Sie nodeToBeDeleted.
2. Wenn nodeToBeDeleted ein Kind hat, ersetzen Sie den Inhalt von nodeToBeDeleted durch den des Kindes. Entfernen Sie das Kind.
3. Wenn nodeToBeDeleted zwei untergeordnete Elemente hat, suchen Sie den Inorder-Nachfolger w von nodeToBeDeleted (dh Knoten mit einem Mindestwert für Schlüssel im rechten Teilbaum). Den Nachfolger finden
  1. Ersetzen Sie den Inhalt von nodeToBeDeleted durch den von w. Ersetzen Sie den zu löschenden Knoten
  2. Entfernen Sie den Blattknoten w. Entfernen Sie w
Aktualisieren Sie balanceFactor der Knoten. Update bf
Balancieren Sie den Baum neu, wenn der Ausgleichsfaktor eines der Knoten nicht gleich -1, 0 oder 1 ist.
1. Wenn balanceFactor von currentNode> 1 ist,
  1. Wenn balanceFactor von leftChild> = 0 ist, drehen Sie nach rechts. Zum Ausbalancieren des Baumes nach rechts drehen
  2. Andernfalls drehen Sie von links nach rechts.
2. Wenn balanceFactor von currentNode <-1 ist,
  1. Wenn balanceFactor von rightChild <= 0 ist, drehen Sie nach links.
  2. Andernfalls drehen Sie sich von rechts nach links.
Der letzte Baum ist: Avl Baum endgültig

Beispiele für Python, Java und C / C ++

Python Java C C ++

 # AVL tree implementation in Python import sys # Create a tree node class TreeNode(object): def __init__(self, key): self.key = key self.left = None self.right = None self.height = 1 class AVLTree(object): # Function to insert a node def insert_node(self, root, key): # Find the correct location and insert the node if not root: return TreeNode(key) elif key 1: if key < root.left.key: return self.rightRotate(root) else: root.left = self.leftRotate(root.left) return self.rightRotate(root) if balanceFactor root.right.key: return self.leftRotate(root) else: root.right = self.rightRotate(root.right) return self.leftRotate(root) return root # Function to delete a node def delete_node(self, root, key): # Find the node to be deleted and remove it if not root: return root elif key root.key: root.right = self.delete_node(root.right, key) else: if root.left is None: temp = root.right root = None return temp elif root.right is None: temp = root.left root = None return temp temp = self.getMinValueNode(root.right) root.key = temp.key root.right = self.delete_node(root.right, temp.key) if root is None: return root # Update the balance factor of nodes root.height = 1 + max(self.getHeight(root.left), self.getHeight(root.right)) balanceFactor = self.getBalance(root) # Balance the tree if balanceFactor> 1: if self.getBalance(root.left)>= 0: return self.rightRotate(root) else: root.left = self.leftRotate(root.left) return self.rightRotate(root) if balanceFactor < -1: if self.getBalance(root.right) <= 0: return self.leftRotate(root) else: root.right = self.rightRotate(root.right) return self.leftRotate(root) return root # Function to perform left rotation def leftRotate(self, z): y = z.right T2 = y.left y.left = z z.right = T2 z.height = 1 + max(self.getHeight(z.left), self.getHeight(z.right)) y.height = 1 + max(self.getHeight(y.left), self.getHeight(y.right)) return y # Function to perform right rotation def rightRotate(self, z): y = z.left T3 = y.right y.right = z z.left = T3 z.height = 1 + max(self.getHeight(z.left), self.getHeight(z.right)) y.height = 1 + max(self.getHeight(y.left), self.getHeight(y.right)) return y # Get the height of the node def getHeight(self, root): if not root: return 0 return root.height # Get balance factore of the node def getBalance(self, root): if not root: return 0 return self.getHeight(root.left) - self.getHeight(root.right) def getMinValueNode(self, root): if root is None or root.left is None: return root return self.getMinValueNode(root.left) def preOrder(self, root): if not root: return print("(0) ".format(root.key), end="") self.preOrder(root.left) self.preOrder(root.right) # Print the tree def printHelper(self, currPtr, indent, last): if currPtr != None: sys.stdout.write(indent) if last: sys.stdout.write("R----") indent += " " else: sys.stdout.write("L----") indent += "| " print(currPtr.key) self.printHelper(currPtr.left, indent, False) self.printHelper(currPtr.right, indent, True) myTree = AVLTree() root = None nums = (33, 13, 52, 9, 21, 61, 8, 11) for num in nums: root = myTree.insert_node(root, num) myTree.printHelper(root, "", True) key = 13 root = myTree.delete_node(root, key) print("After Deletion: ") myTree.printHelper(root, "", True)

 // AVL tree implementation in Java // Create node class Node ( int item, height; Node left, right; Node(int d) ( item = d; height = 1; ) ) // Tree class class AVLTree ( Node root; int height(Node N) ( if (N == null) return 0; return N.height; ) int max(int a, int b) ( return (a> b) ? a : b; ) Node rightRotate(Node y) ( Node x = y.left; Node T2 = x.right; x.right = y; y.left = T2; y.height = max(height(y.left), height(y.right)) + 1; x.height = max(height(x.left), height(x.right)) + 1; return x; ) Node leftRotate(Node x) ( Node y = x.right; Node T2 = y.left; y.left = x; x.right = T2; x.height = max(height(x.left), height(x.right)) + 1; y.height = max(height(y.left), height(y.right)) + 1; return y; ) // Get balance factor of a node int getBalanceFactor(Node N) ( if (N == null) return 0; return height(N.left) - height(N.right); ) // Insert a node Node insertNode(Node node, int item) ( // Find the position and insert the node if (node == null) return (new Node(item)); if (item node.item) node.right = insertNode(node.right, item); else return node; // Update the balance factor of each node // And, balance the tree node.height = 1 + max(height(node.left), height(node.right)); int balanceFactor = getBalanceFactor(node); if (balanceFactor> 1) ( if (item node.left.item) ( node.left = leftRotate(node.left); return rightRotate(node); ) ) if (balanceFactor node.right.item) ( return leftRotate(node); ) else if (item < node.right.item) ( node.right = rightRotate(node.right); return leftRotate(node); ) ) return node; ) Node nodeWithMimumValue(Node node) ( Node current = node; while (current.left != null) current = current.left; return current; ) // Delete a node Node deleteNode(Node root, int item) ( // Find the node to be deleted and remove it if (root == null) return root; if (item root.item) root.right = deleteNode(root.right, item); else ( if ((root.left == null) || (root.right == null)) ( Node temp = null; if (temp == root.left) temp = root.right; else temp = root.left; if (temp == null) ( temp = root; root = null; ) else root = temp; ) else ( Node temp = nodeWithMimumValue(root.right); root.item = temp.item; root.right = deleteNode(root.right, temp.item); ) ) if (root == null) return root; // Update the balance factor of each node and balance the tree root.height = max(height(root.left), height(root.right)) + 1; int balanceFactor = getBalanceFactor(root); if (balanceFactor> 1) ( if (getBalanceFactor(root.left)>= 0) ( return rightRotate(root); ) else ( root.left = leftRotate(root.left); return rightRotate(root); ) ) if (balanceFactor < -1) ( if (getBalanceFactor(root.right) <= 0) ( return leftRotate(root); ) else ( root.right = rightRotate(root.right); return leftRotate(root); ) ) return root; ) void preOrder(Node node) ( if (node != null) ( System.out.print(node.item + " "); preOrder(node.left); preOrder(node.right); ) ) // Print the tree private void printTree(Node currPtr, String indent, boolean last) ( if (currPtr != null) ( System.out.print(indent); if (last) ( System.out.print("R----"); indent += " "; ) else ( System.out.print("L----"); indent += "| "; ) System.out.println(currPtr.item); printTree(currPtr.left, indent, false); printTree(currPtr.right, indent, true); ) ) // Driver code public static void main(String() args) ( AVLTree tree = new AVLTree(); tree.root = tree.insertNode(tree.root, 33); tree.root = tree.insertNode(tree.root, 13); tree.root = tree.insertNode(tree.root, 53); tree.root = tree.insertNode(tree.root, 9); tree.root = tree.insertNode(tree.root, 21); tree.root = tree.insertNode(tree.root, 61); tree.root = tree.insertNode(tree.root, 8); tree.root = tree.insertNode(tree.root, 11); tree.printTree(tree.root, "", true); tree.root = tree.deleteNode(tree.root, 13); System.out.println("After Deletion: "); tree.printTree(tree.root, "", true); ) )

 // AVL tree implementation in C #include #include // Create Node struct Node ( int key; struct Node *left; struct Node *right; int height; ); int max(int a, int b); // Calculate height int height(struct Node *N) ( if (N == NULL) return 0; return N->height; ) int max(int a, int b) ( return (a> b) ? a : b; ) // Create a node struct Node *newNode(int key) ( struct Node *node = (struct Node *) malloc(sizeof(struct Node)); node->key = key; node->left = NULL; node->right = NULL; node->height = 1; return (node); ) // Right rotate struct Node *rightRotate(struct Node *y) ( struct Node *x = y->left; struct Node *T2 = x->right; x->right = y; y->left = T2; y->height = max(height(y->left), height(y->right)) + 1; x->height = max(height(x->left), height(x->right)) + 1; return x; ) // Left rotate struct Node *leftRotate(struct Node *x) ( struct Node *y = x->right; struct Node *T2 = y->left; y->left = x; x->right = T2; x->height = max(height(x->left), height(x->right)) + 1; y->height = max(height(y->left), height(y->right)) + 1; return y; ) // Get the balance factor int getBalance(struct Node *N) ( if (N == NULL) return 0; return height(N->left) - height(N->right); ) // Insert node struct Node *insertNode(struct Node *node, int key) ( // Find the correct position to insertNode the node and insertNode it if (node == NULL) return (newNode(key)); if (key key) node->left = insertNode(node->left, key); else if (key> node->key) node->right = insertNode(node->right, key); else return node; // Update the balance factor of each node and // Balance the tree node->height = 1 + max(height(node->left), height(node->right)); int balance = getBalance(node); if (balance> 1 && key left->key) return rightRotate(node); if (balance node->right->key) return leftRotate(node); if (balance> 1 && key> node->left->key) ( node->left = leftRotate(node->left); return rightRotate(node); ) if (balance < -1 && key right->key) ( node->right = rightRotate(node->right); return leftRotate(node); ) return node; ) struct Node *minValueNode(struct Node *node) ( struct Node *current = node; while (current->left != NULL) current = current->left; return current; ) // Delete a nodes struct Node *deleteNode(struct Node *root, int key) ( // Find the node and delete it if (root == NULL) return root; if (key key) root->left = deleteNode(root->left, key); else if (key> root->key) root->right = deleteNode(root->right, key); else ( if ((root->left == NULL) || (root->right == NULL)) ( struct Node *temp = root->left ? root->left : root->right; if (temp == NULL) ( temp = root; root = NULL; ) else *root = *temp; free(temp); ) else ( struct Node *temp = minValueNode(root->right); root->key = temp->key; root->right = deleteNode(root->right, temp->key); ) ) if (root == NULL) return root; // Update the balance factor of each node and // balance the tree root->height = 1 + max(height(root->left), height(root->right)); int balance = getBalance(root); if (balance> 1 && getBalance(root->left)>= 0) return rightRotate(root); if (balance> 1 && getBalance(root->left) left = leftRotate(root->left); return rightRotate(root); ) if (balance right) <= 0) return leftRotate(root); if (balance right)> 0) ( root->right = rightRotate(root->right); return leftRotate(root); ) return root; ) // Print the tree void printPreOrder(struct Node *root) ( if (root != NULL) ( printf("%d ", root->key); printPreOrder(root->left); printPreOrder(root->right); ) ) int main() ( struct Node *root = NULL; root = insertNode(root, 2); root = insertNode(root, 1); root = insertNode(root, 7); root = insertNode(root, 4); root = insertNode(root, 5); root = insertNode(root, 3); root = insertNode(root, 8); printPreOrder(root); root = deleteNode(root, 3); printf("After deletion: "); printPreOrder(root); return 0; )

 // AVL tree implementation in C++ #include using namespace std; class Node ( public: int key; Node *left; Node *right; int height; ); int max(int a, int b); // Calculate height int height(Node *N) ( if (N == NULL) return 0; return N->height; ) int max(int a, int b) ( return (a> b) ? a : b; ) // New node creation Node *newNode(int key) ( Node *node = new Node(); node->key = key; node->left = NULL; node->right = NULL; node->height = 1; return (node); ) // Rotate right Node *rightRotate(Node *y) ( Node *x = y->left; Node *T2 = x->right; x->right = y; y->left = T2; y->height = max(height(y->left), height(y->right)) + 1; x->height = max(height(x->left), height(x->right)) + 1; return x; ) // Rotate left Node *leftRotate(Node *x) ( Node *y = x->right; Node *T2 = y->left; y->left = x; x->right = T2; x->height = max(height(x->left), height(x->right)) + 1; y->height = max(height(y->left), height(y->right)) + 1; return y; ) // Get the balance factor of each node int getBalanceFactor(Node *N) ( if (N == NULL) return 0; return height(N->left) - height(N->right); ) // Insert a node Node *insertNode(Node *node, int key) ( // Find the correct postion and insert the node if (node == NULL) return (newNode(key)); if (key key) node->left = insertNode(node->left, key); else if (key> node->key) node->right = insertNode(node->right, key); else return node; // Update the balance factor of each node and // balance the tree node->height = 1 + max(height(node->left), height(node->right)); int balanceFactor = getBalanceFactor(node); if (balanceFactor> 1) ( if (key left->key) ( return rightRotate(node); ) else if (key> node->left->key) ( node->left = leftRotate(node->left); return rightRotate(node); ) ) if (balanceFactor node->right->key) ( return leftRotate(node); ) else if (key right->key) ( node->right = rightRotate(node->right); return leftRotate(node); ) ) return node; ) // Node with minimum value Node *nodeWithMimumValue(Node *node) ( Node *current = node; while (current->left != NULL) current = current->left; return current; ) // Delete a node Node *deleteNode(Node *root, int key) ( // Find the node and delete it if (root == NULL) return root; if (key key) root->left = deleteNode(root->left, key); else if (key> root->key) root->right = deleteNode(root->right, key); else ( if ((root->left == NULL) || (root->right == NULL)) ( Node *temp = root->left ? root->left : root->right; if (temp == NULL) ( temp = root; root = NULL; ) else *root = *temp; free(temp); ) else ( Node *temp = nodeWithMimumValue(root->right); root->key = temp->key; root->right = deleteNode(root->right, temp->key); ) ) if (root == NULL) return root; // Update the balance factor of each node and // balance the tree root->height = 1 + max(height(root->left), height(root->right)); int balanceFactor = getBalanceFactor(root); if (balanceFactor> 1) ( if (getBalanceFactor(root->left)>= 0) ( return rightRotate(root); ) else ( root->left = leftRotate(root->left); return rightRotate(root); ) ) if (balanceFactor right) right = rightRotate(root->right); return leftRotate(root); ) ) return root; ) // Print the tree void printTree(Node *root, string indent, bool last) ( if (root != nullptr) ( cout << indent; if (last) ( cout << "R----"; indent += " "; ) else ( cout << "L----"; indent += "| "; ) cout  right, indent, true); ) ) int main() ( Node *root = NULL; root = insertNode(root, 33); root = insertNode(root, 13); root = insertNode(root, 53); root = insertNode(root, 9); root = insertNode(root, 21); root = insertNode(root, 61); root = insertNode(root, 8); root = insertNode(root, 11); printTree(root, "", true); root = deleteNode(root, 13); cout << "After deleting " << endl; printTree(root, "", true); )