SHARE
TWEET

Untitled

a guest Nov 13th, 2019 91 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. void findPredecessor(Node** predecessor, Node** parent)
  2. {
  3.     //profiler.countOperation(nrOfOperations[0], sizeCount, 1);
  4.     //if (*predecessor == NULL)
  5.         //return;
  6.  
  7.     (*parent)->size--;
  8.     while ((*predecessor)->right != NULL)
  9.     {
  10.         profiler.countOperation(nrOfOperations[0], sizeCount, 3);
  11.         *parent = *predecessor;
  12.         (*parent)->size--;
  13.         *predecessor = (*predecessor)->right;
  14.     }
  15.     profiler.countOperation(nrOfOperations[0], sizeCount, 1);
  16. }
  17.  
  18. Node* osDelete(Node* root, int rank)
  19. {
  20.     if (root == NULL) //rank too big
  21.         return root;
  22.     int rankOfRoot;
  23.  
  24.     //profiler.countOperation(nrOfOperations[1], sizeCount, 1);
  25.     if (root->left == NULL)
  26.         rankOfRoot = 1;
  27.     else
  28.         rankOfRoot = root->left->size + 1;
  29.  
  30.    
  31.         if (rank < rankOfRoot)
  32.         {
  33.             root->left = osDelete(root->left, rank);
  34.             root->size--;
  35.             return root;
  36.         }
  37.         else
  38.             if (rank > rankOfRoot)
  39.             {
  40.                 root->right = osDelete(root->right, rank - rankOfRoot);
  41.                 root->size--;
  42.                 return root;
  43.             }
  44.             else // node with needed rank found
  45.             {
  46.                 if(root->left == NULL)
  47.                     if (root->right == NULL) //leaf
  48.                     {
  49.                         free(root);
  50.                         return NULL;
  51.                     }
  52.                     else //single child to the right
  53.                     {
  54.                         root->size--;
  55.                         Node* aux = root->right;
  56.                         free(root);
  57.                         return aux;
  58.                     }
  59.                 else // we have child on left
  60.                     if (root->right == NULL) // single child to the left
  61.                     {
  62.                         root->size--;
  63.                         Node* aux = root->left;
  64.                         free(root);
  65.                         return aux;
  66.                     }
  67.                     else // 2 children.
  68.                     {
  69.  
  70.                         Node* predecessor = root->left;
  71.                         Node* parent = root;
  72.                         //in findPredecessor we update the size field
  73.                         findPredecessor(&predecessor, &parent);
  74.                         //printf("predecessor is %d, parent is %d\n", predecessor->key, parent->key);
  75.                         root->key = predecessor->key;
  76.                         if (parent == root)
  77.                         {
  78.                             root->key = predecessor->key;
  79.                             root->left = predecessor->left;
  80.                             free(predecessor);
  81.                         }
  82.                         else
  83.                         {
  84.                             root->key = predecessor->key;
  85.                             parent->right = predecessor->left;
  86.                             free(predecessor);
  87.                         }
  88.                         return root;
  89.                     }
  90.             }
  91.    
  92. }
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