АВЛ Трее

У овом упутству ћете научити шта је авл дрво. Такође ћете наћи радне примере различитих операција изведених на авл стаблу на Ц, Ц ++, Јава и Питхон.

АВЛ стабло је самобалансирајуће бинарно стабло претраживања у којем сваки чвор одржава додатне информације које се називају фактор равнотеже чија је вредност -1, 0 или +1.

Дрво АВЛ добило је име по проналазачу Георгиу Аделсон-Велскиу и Ландису.

Фактор равнотеже

Фактор равнотеже чвора у АВЛ стаблу је разлика између висине левог подстабла и висине десног подстабла тог чвора.

Фактор равнотеже = (Висина левог подстабла - Висина десног подстабла) или (Висина десног подстабла - Висина левог подстабла)

Својство самобалансирања авл стабла одржава се фактором равнотеже. Вредност билансног фактора увек треба да буде -1, 0 или +1.

Пример уравнотеженог авл стабла је:

Авл дрво

Операције на АВЛ стаблу

Разне операције које се могу изводити на АВЛ стаблу су:

Ротирање подстабала у АВЛ стаблу

У операцији ротације, положаји чворова подстабла се замењују.

Постоје две врсте ротација:

Ротирај улево

У ротацији лево, распоред чворова на десној страни се трансформише у аранжмане на левом чвору.

Алгоритам

  1. Нека почетно стабло буде: Ротирајте лево
  2. Ако и има лево подстабло, доделите к као родитеља левог подстабла и. Доделите к као родитеља левог подстабла и
  3. Ако је родитељ к NULL, направите и као корен стабла.
  4. Иначе ако је к лево дете п, нека и буде лево дете п.
  5. Иначе доделити и као право дете п. Промените надређеног к у и
  6. Нека и буде родитељ к-а. Доделите и као надређену к.

Десно ротирај

У левој ротацији, распоред чворова на левој страни трансформише се у аранжмане на десном чвору.

  1. Нека почетно стабло буде: Иницијално стабло
  2. Ако к има право подстабло, доделите и као родитеља правог подстабла к. Доделите и као родитеља правог подстабла к
  3. Ако је родитељ и NULL, направите к као корен стабла.
  4. Иначе ако је и право дете свог родитеља п, нека к буде право дете п.
  5. Иначе доделити к као лево дете п. Додели родитеља и као родитеља к.
  6. Направите к као родитеља од и. Доделите к као родитеља и

Ротирање лијево-десно и десно-лијево

У ротацији лево-десно, аранжмани се прво померају улево, а затим удесно.

  1. Направите ротацију улево на ки. Ротирајте лево ки
  2. Направите ротацију десно на из. Окрените десно зи

У ротацији десно-лево, распоред се прво помера удесно, а затим улево.

  1. Направите ротацију удесно на ки. Окрените десно ки
  2. Направите ротацију улево на зи. Ротирајте лево зи

Алгоритам за уметање новогНоде

Нови чвор се увек убацује као лисни чвор са фактором равнотеже једнаким 0.

  1. Нека почетно стабло буде: Иницијално стабло за уметање
    Нека чвор који се убацује буде: Нови чвор
  2. Идите на одговарајући чвор листа да бисте уметнули нови чвор користећи следеће рекурзивне кораке. Упоредите невКеи са роотКеи-ом тренутног стабла.
    1. Ако је невКеи <роотКеи, позовите алгоритам за уметање на левом подстаблу тренутног чвора док се не достигне чвор листа.
    2. Иначе, ако је невКеи> роотКеи, алгоритам за уметање позива на десном подстаблу тренутног чвора док се не достигне чвор листа.
    3. У супротном, вратите леафНоде. Проналажење локације за уметање новогНоде
  3. Упоредите леафКеи добијен из горњих корака са невКеи:
    1. Ако је невКеи <леафКеи, направите невНоде као лефтЦхилд оф леафНоде.
    2. Иначе, направи невНоде као ригхтЦхилд оф леафНоде. Уметање новог чвора
  4. Ажурирајте фактор равнотеже чворова. Ажурирање фактора равнотеже након уметања
  5. Ако су чворови неуравнотежени, поново уравнотежите чвор.
    1. Ако је баланцеФацтор> 1, то значи да је висина левог подстабла већа од висине десног подстабла. Дакле, направите ротацију десно или лево-десно
      1. Ако је невНодеКеи <лефтЦхилдКеи, изврши ротацију удесно.
      2. Иначе, врти ротацију лево-десно. Балансирање дрвета са ротацијом Балансирање дрвета са ротацијом
    2. Ако је баланцеФацтор <-1, то значи да је висина десног подстабла већа од висине левог подстабла. Дакле, направите ротацију десно или десно-лево
      1. Ако невНодеКеи> ригхтЦхилдКеи изврши ротацију улево.
      2. Иначе, направите ротацију десно-лево
  6. Коначно стабло је: Коначно уравнотежено дрво

Алгоритам за брисање чвора

Чвор се увек брише као чвор листа. Након брисања чвора, фактори равнотеже чворова се мењају. Да би се уравнотежио фактор равнотеже, изводе се одговарајуће ротације.

  1. Пронађите нодеТоБеДелетед (рекурзија се користи за проналажење нодеТоБеДелетед у коду који се користи доле). Лоцирање чвора за брисање
  2. Постоје три случаја за брисање чвора:
    1. Ако је нодеТоБеДелетед чвор листа (тј. Нема ниједно дете), тада уклоните нодеТоБеДелетед.
    2. Ако нодеТоБеДелетед има једно дете, тада замените садржај нодеТоБеДелетед садржајем детета. Уклоните дете.
    3. Ако нодеТоБеДелетед има двоје деце, пронађите наследника в од нодеТоБеДелетед (тј. Чвор са минималном вредношћу кључа у десном подстаблу). Проналажење наследника
      1. Замените садржај нодеТоБеДелетед садржајем в. Замените чвор који желите да избришете
      2. Уклоните чвор листа в. Уклоните в
  3. Ажурирајте фактор равнотеже чворова. Ажурирај бф
  4. Поново уравнотежите стабло ако фактор равнотеже било ког од чворова није једнак -1, 0 или 1.
    1. Ако је баланцеФацтор тренутногНоде> 1,
      1. Ако је баланцеФацтор лефтЦхилд> = 0, извршите ротацију удесно. Окрените се удесно за балансирање стабла
      2. Иначе врте ротацију лево-десно.
    2. Ако је баланцеФацтор тренутногНоде <-1,
      1. Ако је баланцеФацтор ригхтЦхилд <= 0, извршите ротацију улево.
      2. Иначе врте ротацију десно-лево.
  5. Коначно стабло је: Авл стабло коначно

Примери за Питхон, Јава и Ц / Ц ++

Питхон Јава Ц Ц ++ 
 # 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); )

Сложеност различитих операција на АВЛ стаблу

Уметање Делетион Претрага
О (лог н) О (лог н) О (лог н)

Апликације АВЛ стабла

  • За индексирање великих записа у базама података
  • За претрагу у великим базама података

Занимљиви Чланци...