Drevo AVL

V tej vadnici boste izvedeli, kaj je avl drevo. Prav tako boste našli delovne primere različnih operacij, izvedenih na avl drevesu v C, C ++, Java in Python.

Drevo AVL je samoravnotežno binarno drevo iskanja, v katerem vsako vozlišče hrani dodatne informacije, imenovane faktor ravnotežja, katerih vrednost je -1, 0 ali +1.

Drevo AVL je ime dobilo po izumitelju Georgyju Adelson-Velskyju in Landisu.

Faktor ravnotežja

Faktor ravnotežja vozlišča v drevesu AVL je razlika med višino levega poddrevesa in višine desnega poddrevesa tega vozlišča.

Faktor ravnotežja = (višina levega podrevesa - višina desnega poddrevesa) ali (višina desnega poddrevesa - višina levega poddrevesa)

Lastnost samo uravnoteženja drevesa avl vzdržuje faktor ravnotežja. Vrednost bilančnega faktorja mora biti vedno -1, 0 ali +1.

Primer uravnoteženega drevesa avl je:

Avl drevo

Operacije na drevesu AVL

Različne operacije, ki jih je mogoče izvesti na drevesu AVL, so:

Vrtenje poddreves v drevesu AVL

Pri rotaciji se položaji vozlišč poddrevesa izmenjujejo.

Obstajata dve vrsti rotacij:

Zavrtite v levo

Pri levem vrtenju se razporeditev vozlišč na desni strani spremeni v razporeditve na levem vozlišču.

Algoritem

  1. Naj bo začetno drevo: vrti se levo
  2. Če ima y levo poddrevo, dodelite x kot nadrejeno za levo poddrevo y. Dodelite x kot nadrejeno za levo poddrevo y
  3. Če je nadrejeni x NULL, naredite y kot koren drevesa.
  4. V nasprotnem primeru, če je x levi podrejeni p, naj bo y levi podrejeni p.
  5. V nasprotnem primeru y dodelite kot pravega podrejenega p. Spremenite nadrejenega x v tistega y
  6. Naredite y kot nadrejeno x. Dodelite y kot nadrejeno x.

Zavrti desno

Pri vrtenju v levo se razporeditev vozlišč na levi spremeni v razporeditve na desnem vozlišču.

  1. Naj bo začetno drevo: Začetno drevo
  2. Če ima x desno poddrevo, dodelite y kot nadrejeno za desno poddrevo x. Dodelite y kot nadrejeno za desno poddrevo x
  3. Če je nadrejeni element y NULL, naredite x kot koren drevesa.
  4. V nasprotnem primeru, če je y pravi podrejen svojega starša p, naredi x pravi podrejen p.
  5. V nasprotnem primeru dodelite x kot levemu podrejenemu str. Nadrejenemu y dodelite nadrejenega x.
  6. Naj bo x nadrejen za y. Dodelite x kot nadrejeni element y

Zavrtite levo-desno in desno-levo

Pri rotaciji levo-desno se razporeditve najprej premaknejo v levo in nato v desno.

  1. Zavrtite levo na xy. Zavrtite levo xy
  2. Zavrtite desno na yz. Zavrtite desno zy

Pri rotaciji desno-levo se razporeditve najprej premaknejo v desno in nato v levo.

  1. Zavrtite desno na xy. Zavrtite v desno xy
  2. Zavrtite levo na zy. Zavrtite levo zy

Algoritem za vstavljanje novega vozlišča

Novo vozlišče se vedno vstavi kot listno vozlišče s faktorjem ravnotežja, ki je enak 0.

  1. Naj bo začetno drevo: Začetno drevo za vstavitev
    Naj bo vstavljeno vozlišče : Novo vozlišče
  2. Pojdite na ustrezno vozlišče listov, da vstavite novo vozlišče z naslednjimi rekurzivnimi koraki. Primerjaj newKey s rootKey trenutnega drevesa.
    1. Če je newKey <rootKey, pokličite algoritem za vstavljanje v levo poddrevo trenutnega vozlišča, dokler ni doseženo listno vozlišče.
    2. V nasprotnem primeru, če je newKey> rootKey, pokličite algoritem za vstavljanje klica na desno poddrevo trenutnega vozlišča, dokler ne dosežete listnega vozlišča.
    3. V nasprotnem primeru vrnite leafNode. Iskanje lokacije za vstavljanje novegaNode
  3. Primerjajte leafKey, pridobljen iz zgornjih korakov, z newKey:
    1. Če je newKey <leafKey, naredite newNode kot leftChild of leafNode.
    2. V nasprotnem primeru naredite newNode kot rightChild of leafNode. Vstavljanje novega vozlišča
  4. Posodobi balanceFactor vozlišč. Posodabljanje faktorja ravnotežja po vstavitvi
  5. Če vozlišča niso uravnotežena, vozlišče znova uravnotežite.
    1. Če je balanceFactor> 1, to pomeni, da je višina levega drevesa večja od višine desnega drevesa. Torej, naredite desno vrtenje ali levo-desno rotacijo
      1. Če je newNodeKey <leftChildKey, vrti desno.
      2. V nasprotnem primeru izvedite rotacijo levo-desno. Uravnavanje drevesa z vrtenjem Uravnavanje drevesa z vrtenjem
    2. Če je balanceFactor <-1, to pomeni, da je višina desnega poddrevesa večja od višine levega poddrevesa. Torej, vrtenje v desno ali desno-levo
      1. Če newNodeKey> rightChildKey vrti levo.
      2. V nasprotnem primeru vrtenje desno-levo
  6. Končno drevo je: Končno uravnoteženo drevo

Algoritem za brisanje vozlišča

Vozlišče se vedno izbriše kot listno vozlišče. Po brisanju vozlišča se faktorji ravnovesja vozlišč spremenijo. Da bi uravnotežili faktor ravnotežja, se izvedejo ustrezne rotacije.

  1. Poiščite nodeToBeDeleted (rekurzija se uporablja za iskanje nodeToBeDeleted v spodnji kodi). Iskanje vozlišča, ki ga je treba izbrisati
  2. Obstajajo trije primeri brisanja vozlišča:
    1. Če je nodeToBeDeleted listno vozlišče (tj. Nima nobenega podrejenega), odstranite nodeToBeDeleted.
    2. Če ima nodeToBeDeleted enega podrejenega, vsebino nodeToBeDeleted nadomestite z vsebino otroka. Odstranite otroka.
    3. Če ima nodeToBeDeleted dva podrejena otroka, poiščite naslednjega naslova w nodeToBeDeleted (tj. Vozlišče z najmanjšo vrednostjo ključa v desnem poddrevesu). Iskanje naslednika
      1. Vsebino nodeToBeDeleted zamenjajte z vsebino w. Nadomestite vozlišče, ki ga želite izbrisati
      2. Odstranite listno vozlišče w. Odstranite w
  3. Posodobi balanceFactor vozlišč. Posodobite bf
  4. Ponovno uravnotežite drevo, če faktor ravnovesja katerega koli vozlišča ni enak -1, 0 ali 1.
    1. Če je balanceFactor trenutnega vozlišča> 1,
      1. Če je balanceFactor leftChild> = 0, vrti desno. Za uravnoteženje drevesa zasukajte desno
      2. V nasprotnem primeru vrtenje levo-desno.
    2. Če je balanceFactor trenutnegaNode <-1,
      1. Če je balanceFactor of rightChild <= 0, vrti levo.
      2. V nasprotnem primeru vrtenje desno-levo.
  5. Končno drevo je: Avl drevo končno

Primeri Python, Java in 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); )

Kompleksnosti različnih operacij na drevesu AVL

Vstavitev Izbris Iskanje
O (log n) O (log n) O (log n)

Aplikacije drevesa AVL

  • Za indeksiranje velikih zapisov v zbirkah podatkov
  • Za iskanje v velikih zbirkah podatkov

Zanimive Članki...