AVL-puu

Tässä opetusohjelmassa opit, mikä on AVL-puu. Löydät myös toimivia esimerkkejä erilaisista toiminnoista, jotka suoritetaan avl-puulla C, C ++, Java ja Python.

AVL-puu on itsetasapainotettu binäärihakupuu, jossa kukin solmu ylläpitää ylimääräistä tietoa, jota kutsutaan tasapainokertoimeksi, jonka arvo on joko -1, 0 tai +1.

AVL-puu sai nimensä keksijän Georgy Adelson-Velskyn ja Landisin mukaan.

Tasapainokerroin

AVL-puun solmun tasapainotekijä on vasemman ja oikean alipuun korkeuden ero.

Tasapainokerroin = (Vasemman alipuun korkeus - Oikean alipuun korkeus) tai (Oikean alipuun korkeus - Vasemman alipuun korkeus)

Tasapainokerroin ylläpitää avl-puun itsetasapainoa. Tasapainokertoimen arvon tulisi aina olla -1, 0 tai +1.

Esimerkki tasapainotetusta avl-puusta on:

Keskimääräinen puu

Toiminnot AVL-puulla

Eri toimintoja, jotka voidaan suorittaa AVL-puulla, ovat:

Alipuiden kääntäminen AVL-puussa

Kiertooperaatiossa osapuun solmujen sijainnit vaihdetaan.

Kierroksia on kahdenlaisia:

Kierrä vasemmalle

Vasemmalla kiertämällä oikeanpuoleisten solmujen järjestely muutetaan vasemman solmun järjestelyiksi.

Algoritmi

  1. Olkoon alkuperäinen puu: Vasen kiertää
  2. Jos y: llä on vasen alipuu, määritä x y: n vasemman osapuun vanhemmaksi. Määritä x y: n vasemman alipuun vanhemmaksi
  3. Jos x: n vanhempi on NULL, tee puun juureksi y.
  4. Muutoin, jos x on p: n vasen lapsi, tee y p: n vasemmaksi lapseksi.
  5. Määritä muuten y p: n oikealle lapselle. Muuta x: n vanhempi y: ksi
  6. Tee y x: n vanhemmaksi. Määritä y x: n vanhemmaksi.

Kierrä oikealle

Vasemmalla kiertämällä vasemmanpuoleisten solmujen järjestely muutetaan oikean solmun järjestelyiksi.

  1. Olkoon alkuperäinen puu: Alkuperäinen puu
  2. Jos x: llä on oikea alipuu, määritä y x: n oikean osapuun vanhemmaksi. Määritä y x: n oikean alipuun vanhemmaksi
  3. Jos y: n vanhempi on NULL, tee x puun juureksi.
  4. Muuten, jos y on vanhemmansa p oikea lapsi, tee x p: n oikealla lapsella.
  5. Määritä muutoin x p: n vasemmaksi lapseksi. Määritä y: n vanhempi x: n vanhemmaksi.
  6. Tee x y: n vanhemmaksi. Määritä x y: n vanhemmaksi

Vasen-oikea ja oikea-vasen kääntyvät

Vasemman ja oikean käänteessä järjestelyt siirretään ensin vasemmalle ja sitten oikealle.

  1. Tee vasemmalle kiertäminen xy: llä. Kierrä vasemmalle xy
  2. Kiertää oikealla puolella yz. Kierrä oikealle zy

Oikean ja vasemman käännöksen yhteydessä järjestelyt siirretään ensin oikealle ja sitten vasemmalle.

  1. Käännä oikealle xy. Kierrä oikealle xy
  2. Tee vasemmalle kiertäminen zy: llä. Kierrä vasemmalle zy

Algoritmi uuden solmun lisäämiseksi

NewNode lisätään aina lehtisolmuksi, jonka tasapainokerroin on 0.

  1. Olkoon alkupuu: Alkuperäinen puu lisättäväksi
    Olkoon lisättävä solmu: Uusi solmu
  2. Siirry sopivaan lehtisolmuun ja lisää uusi solmu seuraavien rekursiivisten vaiheiden avulla. Vertaa newKey: tä nykyisen puun rootKey-avaimeen.
    1. Jos newKey <rootKey, kutsu lisäysalgoritmi nykyisen solmun vasemmalle alipuun, kunnes lehti solmu on saavutettu.
    2. Muuten jos newKey> rootKey, kutsu lisäysalgoritmi nykyisen solmun oikealle alipuun, kunnes lehti-solmu on saavutettu.
    3. Muuten, paluu leafNode. NewNode-paikan lisäämisen sijainnin etsiminen
  3. Vertaa edellisistä vaiheista saatua leafKey-näppäintä newKey:
    1. Jos newKey <leafKey, tee newNode leafNode leftChildiksi.
    2. Muuten, tee newNode nimellä leafNode oikeaksi lapseksi. Lisätään uusi solmu
  4. Päivitä solmujen tekijä. Tasapainokertoimen päivitys lisäyksen jälkeen
  5. Jos solmut ovat epätasapainossa, tasapainota sitten solmu uudelleen.
    1. Jos balanceFactor> 1, se tarkoittaa, että vasemman osapuun korkeus on suurempi kuin oikean osapuun korkeus. Joten tee oikea kierto tai vasen-oikea kääntö
      1. Jos newNodeKey <leftChildKey kiertää oikein.
      2. Muuten, käännä vasemmalta oikealle. Puun tasapainotus kiertämällä Puun tasapainotus kiertämällä
    2. Jos balanceFactor <-1, se tarkoittaa, että oikean osapuun korkeus on suurempi kuin vasemman osapuun korkeus. Tee siis oikea tai vasen kierto
      1. Jos newNodeKey> rightChildKey kiertää vasemmalle.
      2. Muuten käännä oikealta vasemmalle
  6. Viimeinen puu on: Lopullinen tasapainoinen puu

Algoritmi solmun poistamiseksi

Solmu poistetaan aina lehtisolmuna. Solmun poistamisen jälkeen solmujen tasapainokertoimet muuttuvat. Tasapainokertoimen tasapainottamiseksi suoritetaan sopivat kierrot.

  1. Etsi nodeToBeDeleted (rekursiota käytetään etsimään nodeToBeDeleted alla käytetystä koodista). Poistettavan solmun sijainti
  2. Solmun poistamiseen on kolme tapausta:
    1. Jos nodeToBeDeleted on lehtisolmu (ts. Sillä ei ole lapsia), poista sitten nodeToBeDeleted.
    2. Jos nodeToBeDeletedillä on yksi lapsi, korvaa nodeToBeDeleted -sisältö lapsen sisällöllä. Poista lapsi.
    3. Jos nodeToBeDeletedillä on kaksi lasta, etsi nodeToBeDeleted: n peräkkäinen seuraaja w (eli solmu, jonka avaimen vähimmäisarvo on oikeassa alipuussa). Seuraavan löytäminen
      1. Korvaa solmunToBeDeleted sisältö w: n sisällöllä. Korvaa poistettava solmu
      2. Irrota lehtisolmu w. Poista w
  3. Päivitä solmujen tekijä. Päivitä bf
  4. Tasapainota puu uudelleen, jos jonkin solmun tasapainokerroin ei ole yhtä suuri kuin -1, 0 tai 1.
    1. Jos BalanceFactor of currentNode> 1,
      1. Jos BalFactor of leftChild> = 0, käännä oikealle. Kierrä oikealle puun tasapainottamiseksi
      2. Muuten käännä vasemmalta oikealle.
    2. Jos BalanceFactor of currentNode <-1,
      1. Jos balanceFactor of rightChild <= 0, käännä vasemmalle.
      2. Muuten käännä oikealta vasemmalle.
  5. Viimeinen puu on: Avl-puu lopullinen

Python-, Java- ja C / C ++ -esimerkkejä

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

Eri toimintojen monimutkaisuus AVL-puulla

Lisäys Poistaminen Hae
O (log n) O (log n) O (log n)

AVL Tree -sovellukset

  • Suurten tietueiden indeksointiin tietokannoissa
  • Suuriin tietokantoihin etsimiseen

Mielenkiintoisia artikkeleita...