AVL medis

Šioje pamokoje sužinosite, kas yra avl medis. Taip pat rasite įvairių operacijų, atliktų naudojant „avl“ medį C, C ++, „Java“ ir „Python“, pavyzdžius.

AVL medis yra savaime balansuojantis dvejetainis paieškos medis, kuriame kiekvienas mazgas palaiko papildomą informaciją, vadinamą balanso koeficientu, kurio vertė yra -1, 0 arba +1.

AVL medis gavo savo vardą po išradėjo Georgijaus Adelsono-Velsky ir Landiso.

Balanso koeficientas

AVL medžio mazgo balanso koeficientas yra skirtumas tarp kairiojo ir dešiniojo to mazgo medžių aukščio.

Balanso koeficientas = (Kairiojo potemio aukštis - Dešiniojo potemio aukštis) arba (Dešiniojo potemio aukštis - Kairio potemio aukštis)

Savaiminio balansavimo savybę medžio medyje palaiko balanso koeficientas. Balanso koeficiento vertė visada turėtų būti -1, 0 arba +1.

Subalansuoto avl medžio pavyzdys yra:

Avl medis

Operacijos su AVL medžiu

Įvairios operacijos, kurias galima atlikti su AVL medžiu, yra šios:

Submedžių sukimas AVL medyje

Sukimosi operacijoje porūšio mazgų pozicijos yra keičiamos.

Yra dviejų tipų pasukimai:

Pasukti kairėn

Sukant kairėje, mazgų išdėstymas dešinėje transformuojamas į kairio mazgo išdėstymus.

Algoritmas

  1. Tegul pradinis medis būna toks: kairysis sukasi
  2. Jei y turi kairįjį pomedį, priskirkite x kaip y kairio potemio tėvą. Paskirkite x kaip kairiojo y potemio tėvą
  3. Jei x yra vienas iš tėvų NULL, padarykite y kaip medžio šaknį.
  4. Jei ne, x yra kairysis p vaikas, padarykite y kaip kairįjį p vaiką.
  5. Kitu atveju priskirkite y tinkamą vaiką p. Pakeiskite x tėvą į y
  6. Padarykite y kaip x tėvą. Priskirkite y kaip x tėvą.

Pasukti dešinėn

Sukant kairėje, kairiųjų mazgų išdėstymas transformuojamas į dešiniojo mazgo išdėstymus.

  1. Tegu pradinis medis būna: Pradinis medis
  2. Jei x turi dešinį potentį, priskirkite y kaip dešiniojo x medžio tėvą. Priskirkite y kaip dešiniojo x potemio tėvą
  3. Jei y yra tėvas NULL, padarykite x kaip medžio šaknį.
  4. Kitu atveju, jei y yra tinkamas jo tėvų p vaikas, padarykite x kaip tinkamą p vaiką.
  5. Kitu atveju priskirkite x kaip kairįjį p. Paskirkite y tėvą kaip x tėvą.
  6. Padarykite x kaip y tėvą. Paskirkite x kaip y tėvą

Pasukite kairę-dešinę ir dešinę-kairę

Sukant kairėn-dešinėn, išdėstymai pirmiausia perkeliami į kairę, tada į dešinę.

  1. Sukite kairę kairėje xy. Kairysis sukasi xy
  2. Darykite dešinę sukdami yz. Dešinėn pasukite zy

Sukant dešinėje ir kairėje, išdėstymai pirmiausia perkeliami į dešinę, o paskui į kairę.

  1. Darykite dešinę sukimosi kryptį xy. Pasukite dešinėn xy
  2. Sukite kairę zy. Kairysis sukasi zy

Algoritmas įterpti naująNode

„NewNode“ visada įterpiamas kaip lapo mazgas, kurio balanso koeficientas lygus 0.

  1. Tegul pradinis medis bus: Pradinis medis įterpimui
    Tegul įterpiamas mazgas yra: Naujas mazgas
  2. Eikite į atitinkamą lapų mazgą, kad įterptumėte naująNode atlikdami šiuos rekursinius veiksmus. Palyginkite „newKey“ su dabartinio medžio „rootKey“.
    1. Jei newKey <rootKey, iškvieskite įterpimo algoritmą kairiajame dabartinio mazgo potemyje, kol pasieksite lapų mazgą.
    2. Else if newKey> rootKey, iškvieskite įterpimo algoritmą dešiniajame dabartinio mazgo poskyryje, kol pasieksite lapų mazgą.
    3. Kita, grįžkite leafNode. „NewNode“ įterpimo vietos radimas
  3. Palyginkite „leafKey“, gautą atlikus anksčiau nurodytus veiksmus, su „newKey“:
    1. Jei newKey <leafKey, padarykite newNode kaip „leafNode“ kairįjį vaiką.
    2. Kita vertus, padarykite newNode kaip rightChild of leafNode. Įterpiamas naujas mazgas
  4. Atnaujinti mazgų koeficientą. Balanso koeficiento atnaujinimas po įterpimo
  5. Jei mazgai nesubalansuoti, tada subalansuokite mazgą.
    1. Jei „balanceFactor“> 1, tai reiškia, kad kairiojo pogrindžio aukštis yra didesnis nei dešiniojo pogrindžio. Taigi, pasukite dešinę arba kairę-dešinę
      1. Jei newNodeKey <leftChildKey sukasi teisingai.
      2. Kitaip, pasukite kairę į dešinę. Medžio balansavimas pasukant Medžio balansavimas pasukant
    2. Jei „balanceFactor“ yra <-1, tai reiškia, kad dešiniojo pogrindžio aukštis yra didesnis nei kairiojo pogrindžio. Taigi, pasukite į dešinę arba į kairę
      1. Jei newNodeKey> rightChildKey sukasi kairėn.
      2. Kitaip, pasukite dešinę į kairę
  6. Galutinis medis yra: Galutinis subalansuotas medis

Mazgo ištrynimo algoritmas

Mazgas visada ištrinamas kaip lapų mazgas. Ištrynus mazgą, pasikeičia mazgų balanso faktoriai. Siekiant subalansuoti pusiausvyros koeficientą, atliekami tinkami sukimai.

  1. Raskite „nodeToBeDeleted“ (rekursija naudojama norint surasti „nodeToBeDeleted“ žemiau naudojamame kode). Ištrintino mazgo nustatymas
  2. Yra trys mazgų ištrynimo atvejai:
    1. Jei „nodeToBeDeleted“ yra lapo mazgas (t. Y. Neturi vaiko), tada pašalinkite „nodeToBeDeleted“.
    2. Jei „nodeToBeDeleted“ turi vieną vaiką, tada pakeiskite „nodeToBeDeleted“ turinį vaiko. Pašalinkite vaiką.
    3. Jei „nodeToBeDeleted“ turi du vaikus, suraskite „nodeToBeDeleted“ eilinį įpėdinį w (t. Y. Mazgą su minimalia rakto verte dešiniajame medyje). Surasti įpėdinį
      1. Pakeiskite nodeToBeDeleted turinį w. Pakeiskite mazgą, kurį norite ištrinti
      2. Nuimkite lapo mazgą w. Pašalinti w
  3. Atnaujinti mazgų koeficientą. Atnaujinti bf
  4. Subalansuokite medį, jei kurio nors mazgo balanso koeficientas nėra lygus -1, 0 arba 1.
    1. Jei balansas: currentNode koeficientas> 1,
      1. Jei balanceFactor of leftChild> = 0, pasukite į dešinę. Pasukite dešinėn, kad subalansuotumėte medį
      2. Kitu atveju pasukite kairę ir dešinę.
    2. Jei balansas currentNode <-1 koeficientas,
      1. Jei „rightChild“ veiksnys <= 0, pasukite kairėn.
      2. Kitu atveju pasukite dešinę ir kairę.
  5. Galutinis medis yra: Avl medžio galutinis

„Python“, „Java“ ir „C / C ++“ pavyzdžiai

„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); )

Įvairių AVL medžio operacijų sudėtingumas

Įterpimas Ištrinti Paieška
O (log n) O (log n) O (log n)

AVL medžio programos

  • Didelių įrašų indeksavimui duomenų bazėse
  • Paieškai didelėse duomenų bazėse

Įdomios straipsniai...