SHARE
TWEET

Untitled

a guest Dec 12th, 2019 70 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /**
  2.  * @brief Helper func: rotate left (Black-Red tree rotation)
  3.  * @param node a node
  4.  * @param tree a tree
  5.  */
  6. void rotateLeft(Node *node, RBTree *tree)
  7. {
  8.     Node *new_node = node->right;
  9.     Node *par = node->parent;
  10.     int rootValidator = 0;
  11.     if (node->parent == NULL)
  12.     {
  13.         rootValidator = 1;
  14.     }
  15.     if (new_node == NULL)
  16.     {
  17.         return;
  18.     }
  19.     node->right = new_node->left;
  20.     new_node->left = node;
  21.     node->parent = new_node;
  22.     if (node->right != NULL)
  23.     {
  24.         node->right->parent = node;
  25.     }
  26.     if (par != NULL)
  27.     {
  28.         if (node == par->left)
  29.         {
  30.             par->left = new_node;
  31.         }
  32.         else if (node == par->right)
  33.         {
  34.             par->right = new_node;
  35.         }
  36.     }
  37.     new_node->parent = par;
  38.     if ((node->parent != NULL) && (rootValidator == 1))
  39.     {
  40.         tree->root = node->parent;
  41.     }
  42.  
  43. }
  44.  
  45. /**
  46.  * @brief Helper func: rotate right (Black-Red tree rotation)
  47.  * @param node a node
  48.  * @param tree a tree
  49.  */
  50. void rotateRight(Node *nodePtr, RBTree *tree)
  51. {
  52.     Node *new_node = nodePtr->left;
  53.     Node *par = nodePtr->parent;
  54.     int rootValidator = 0;
  55.  
  56.     if (nodePtr->parent == NULL)
  57.     {
  58.         rootValidator = 1;
  59.     }
  60.     if (new_node == NULL)
  61.     {
  62.         return;
  63.     }
  64.     nodePtr->left = new_node->right;
  65.     new_node->right = nodePtr;
  66.     nodePtr->parent = new_node;
  67.  
  68.     if (nodePtr->left != NULL)
  69.     {
  70.         nodePtr->left->parent = nodePtr;
  71.     }
  72.  
  73.     if (par != NULL)
  74.     {
  75.         if (nodePtr == par->left)
  76.         {
  77.             par->left = new_node;
  78.         }
  79.         else if (nodePtr == par->right)
  80.         {
  81.             par->right = new_node;
  82.         }
  83.     }
  84.     new_node->parent = par;
  85.     if ((nodePtr->parent != NULL) && (rootValidator == 1))
  86.     {
  87.         tree->root = nodePtr->parent;
  88.     }
  89. }
  90.  
  91.  
  92. /**
  93. * Scenario 4 from the specifications
  94. * @param node a node
  95. * @param tree a tree
  96. */
  97. void scenario4Insertion(Node *nodePtr, RBTree *tree)
  98. {
  99.     Node *par = nodePtr->parent;
  100.     Node *grand = nodePtr->parent->parent;
  101.  
  102.     if (grand->left == par)
  103.     {
  104.         if (par->right == nodePtr)
  105.         {
  106.             rotateLeft(par, tree);
  107.             rotateRight(grand, tree);
  108.             nodePtr->color = BLACK;
  109.             grand->color = RED;
  110.  
  111.         }
  112.         else
  113.         {
  114.  
  115.             rotateRight(grand, tree);
  116.             par->color = BLACK;
  117.             grand->color = RED;
  118.  
  119.         }
  120.  
  121.     }
  122.  
  123.     else if (grand->right == par)
  124.     {
  125.         if (par->left == nodePtr)
  126.         {
  127.             rotateRight(par, tree);
  128.             rotateLeft(grand, tree);
  129.             nodePtr->color = BLACK;
  130.             grand->color = RED;
  131.         }
  132.         else
  133.         {
  134.             rotateLeft(grand, tree);
  135.             par->color = BLACK;
  136.             grand->color = RED;
  137.         }
  138.  
  139.     }
  140.  
  141. }
  142.  
  143.  
  144. /**
  145.  * @brief Fix tree function. this function is called in order to fix the tree structure aftetr
  146.  * insert
  147.  * @param node a node that was inserted
  148.  * @param tree a tree to fix
  149.  */
  150. void rotate(Node *node, RBTree *tree)
  151. {
  152.     if (node->parent == NULL)
  153.     {   //INSERT - CASE 1
  154.         if (node->parent == NULL)
  155.         {
  156.             node->color = BLACK;
  157.         }
  158.     }
  159.     else if (node->parent->color == BLACK)
  160.     {
  161.         return;
  162.     }
  163.     else if (getUncle(tree, node) != NULL && getUncle(tree, node)->color == RED
  164.              && node->color == RED)
  165.     {
  166.         node->parent->color = BLACK;
  167.         getUncle(tree, node)->color = BLACK;
  168.         node->parent->parent->color = RED;
  169.         rotate(node->parent->parent, tree);
  170.     }
  171.     else if ((getUncle(tree, node) != NULL && getUncle(tree, node)->color == BLACK
  172.              && node->parent->color == RED) ||
  173.              (getUncle(tree, node) == NULL
  174.              && node->parent->color == RED))
  175.     {
  176.         scenario4Insertion(node, tree);
  177.     }
  178. }
  179.  
  180.  
  181. /**
  182.  * add an item to the tree
  183.  * @param tree: the tree to add an item to.
  184.  * @param data: item to add to the tree.
  185.  * @return: 0 on failure, other on success. (if the item is already in the tree - failure).
  186.  */
  187. int addToRBTree(RBTree *tree, void *data)
  188. {
  189.     // Check If Contains
  190.     if (containsRBTree(tree, data) != 0)        // data is already in the tree
  191.     {
  192.         return 0;
  193.     }
  194.  
  195.     // Create Node
  196.     Node *nodePtr = (Node *) malloc(sizeof(Node));
  197.  
  198.     Node createdNode = {NULL, NULL, NULL, RED, data};
  199.     *nodePtr = createdNode;
  200.  
  201.     // Case 1
  202.     if (tree->size == 0)
  203.     {
  204.         addCaseOne(tree, nodePtr);    // size++ inside
  205.         return 1;
  206.     }
  207.  
  208.  
  209.     // aggressive - insert node
  210.     insertAggressive(tree, nodePtr);
  211.  
  212.  
  213.     // rotate (Cases 2,3,4)
  214.     rotate(nodePtr, tree);
  215.  
  216.     // update Tree Root (tree field)
  217.     if (tree->root->parent != NULL)
  218.     {
  219.         tree->root = tree->root->parent;
  220.     }
  221.  
  222.     tree->size++;
  223.     return 1;
  224.  
  225.  
  226. }
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
 
Top