SHARE
TWEET

AVL.CPP

a guest Oct 21st, 2019 73 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include "AVL.h"
  2. #include <iostream>
  3. using namespace std;
  4. int iq = 0;
  5. int max(int a, int b)
  6. {
  7.     return (a > b ? a : b);
  8. }
  9.  
  10. //calculates the longest path from a current node to a leaf
  11. int maxPathLength(NodeAVL* node)
  12. {
  13.     if (node == NULL)
  14.         return 0;
  15.     return (max(maxPathLength(node->right), maxPathLength(node->left)) + 1);
  16. }
  17.  
  18. //calculates the balance indicator of each node of the tree
  19. void computeBalanceFactor(NodeAVL* node)
  20. {
  21.     int maxLeft = 0, maxRight = 0;
  22.  
  23.     if (node->left != NULL)
  24.         maxLeft = maxPathLength(node->left);
  25.     else
  26.         maxLeft = 0;
  27.  
  28.     if (node->right != NULL)
  29.         maxRight = maxPathLength(node->right);
  30.     else
  31.         maxRight = 0;
  32.  
  33.     node->echi = maxRight - maxLeft;
  34. }
  35.  
  36. //simple left rotation
  37. NodeAVL* leftRotation(NodeAVL* root, NodeAVL* node) //p is critical node
  38. {
  39.     NodeAVL* heavyChild;
  40.  
  41.     heavyChild = node->right;
  42.     node->right = heavyChild->left;
  43.     heavyChild->left = node;
  44.  
  45.     computeBalanceFactor(node);
  46.     computeBalanceFactor(heavyChild);
  47.  
  48.     node = heavyChild;
  49.     cout << "Rotation number " << ++iq << endl;
  50.     displayAVLTree(root, 10);
  51.     return node;
  52. }
  53.  
  54. //simple right rotation
  55. NodeAVL* rightRotation(NodeAVL* root, NodeAVL* node)
  56. {
  57.     NodeAVL* heavyChild;
  58.  
  59.     heavyChild = node->left;
  60.     node->left = heavyChild->right;
  61.     heavyChild->right = node;
  62.  
  63.     computeBalanceFactor(node);
  64.     computeBalanceFactor(heavyChild);
  65.  
  66.     node = heavyChild;
  67.     cout << "Rotation number " << ++iq << endl;
  68.     displayAVLTree(root, 10);
  69.     return node;
  70. }
  71.  
  72. //double left rotation
  73. NodeAVL* doubleLeftRotation(NodeAVL* root, NodeAVL* node)
  74. {
  75.     node->right = rightRotation(root, node->right);
  76.     node = leftRotation(root, node);
  77.     cout << "Rotation number " << ++iq << endl;
  78.     displayAVLTree(root, 10);
  79.     return node;
  80. }
  81.  
  82. //double right rotation
  83. NodeAVL* doubleRightRotation(NodeAVL* root, NodeAVL* node)
  84. {
  85.     node->left = leftRotation(root, node->left);
  86.     node = rightRotation(root, node);
  87.     cout << "Rotation number " << ++iq << endl;
  88.     displayAVLTree(root, 10);
  89.     return node;
  90. }
  91.  
  92. //tree balancing function
  93. NodeAVL* balance(NodeAVL* root, NodeAVL* node)
  94. {
  95.     NodeAVL* heavyChild;
  96.  
  97.     computeBalanceFactor(node);
  98.  
  99.     if (node->echi == -2)   // if p is a critical junction (LEFT hanging)
  100.     {
  101.         heavyChild = node->left;    // heavyChild - left child of p
  102.  
  103.         if (heavyChild->echi == 1)
  104.             node = doubleRightRotation(root, node);
  105.         else
  106.             node = rightRotation(root, node);
  107.     }
  108.     else
  109.         if (node->echi == 2)        // // if p is a critical junction (RIGHT hanging)
  110.         {
  111.             heavyChild = node->right;   // heavyChild - right child of p
  112.  
  113.             if (heavyChild->echi == -1)
  114.                 node = doubleLeftRotation(root, node);
  115.             else
  116.                 node = leftRotation(root, node);
  117.         }
  118.  
  119.     return node;
  120. }
  121.  
  122. //function for inserting a node
  123. NodeAVL* insertAVLNode(NodeAVL* root, NodeAVL* node, int value)
  124. {
  125.     if (node == NULL)
  126.     {
  127.         node = new NodeAVL;
  128.         node->key = value;
  129.         node->echi = 0;
  130.         node->left = NULL;
  131.         node->right = NULL;
  132.         return node;
  133.     }
  134.     else
  135.         if (value < node->key)
  136.             node->left = insertAVLNode(root, node->left, value);
  137.         else
  138.             if (value > node->key)
  139.                 node->right = insertAVLNode(root, node->right, value);
  140.             else
  141.                 printf("The key %d already exists! \n", value);
  142.  
  143.     node = balance(root, node);
  144.  
  145.     return node;
  146. }
  147.  
  148. //printing function
  149. void displayAVLTree(NodeAVL* node, int level)
  150. {
  151.     if (node != NULL)
  152.     {
  153.         displayAVLTree(node->right, level + 7);
  154.         for (int i = 0; i < level; i++)
  155.             printf(" ");
  156.  
  157.         printf("%d(%d) \n", node->key, node->echi);
  158.         displayAVLTree(node->left, level + 7);
  159.     }
  160. }
  161.  
  162. //function for deleting a node
  163. NodeAVL* deleteAVLNode(NodeAVL* root, NodeAVL* node, int value)
  164. {
  165.     if (node == NULL)
  166.     {
  167.         printf("Can't delete key %d, it is not in AVL tree!\n", value);
  168.         return node;
  169.     }
  170.  
  171.     if (value < node->key)
  172.         node->left = deleteAVLNode(root, node->left, value);
  173.  
  174.     else if (value > node->key)
  175.         node->right = deleteAVLNode(root, node->right, value);
  176.  
  177.     else
  178.     {
  179.         // node with only one child or no child
  180.         if ((node->left == NULL) || (node->right == NULL))
  181.         {
  182.             NodeAVL* temp;
  183.  
  184.             if (node->left != NULL)
  185.                 temp = node->left;
  186.             else
  187.                 temp = node->right;
  188.  
  189.             // No child case
  190.             if (temp == NULL)
  191.                 node = NULL;
  192.  
  193.             else // One child case
  194.             {
  195.                 *node = *temp;
  196.                 free(temp);
  197.             }
  198.         }
  199.         else
  200.         {
  201.             // node with two children: Get the inorder successor
  202.             // (smallest in the right subtree)
  203.             NodeAVL* temp = node->right;
  204.  
  205.             while (temp->left != NULL)
  206.                 temp = temp->left;
  207.  
  208.             // Copy the inorder successor's data to this node
  209.             node->key = temp->key;
  210.  
  211.             // Delete the inorder successor
  212.             node->right = deleteAVLNode(root, node->right, temp->key);
  213.         }
  214.     }
  215.  
  216.     // If the tree had only one node then return
  217.     if (node != NULL)
  218.         node = balance(root, node);
  219.  
  220.     return node;
  221. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top