Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- void rotateRight(RBTree *tree, Node* node)
- {
- Node *cur = node->left;
- node->left = cur->right;
- if(node->left != NULL)
- {
- node->left->parent = node;
- }
- cur->left = node;
- if(node->parent == NULL)
- {
- tree->root = cur;
- }
- else if(node == node->parent->left)
- {
- node->parent->left = cur;
- }
- else
- {
- node->parent->right = cur;
- }
- cur->right = node;
- node->parent = cur;
- }
- void rotateLeft(RBTree *tree, Node* node)
- {
- Node *cur = node->right;
- node->right = cur->left;
- if(node->right != NULL)
- {
- node->right->parent = node;
- }
- cur->left = node;
- if(node->parent == NULL)
- {
- tree->root = cur;
- }
- else if(node == node->parent->left)
- {
- node->parent->left = cur;
- }
- else
- {
- node->parent->right = cur;
- }
- cur->left = node;
- node->parent = cur;
- }
- /**
- * given a node and a tree rotate the tree's nodes according to the
- * current situation
- * @param cur - the node we want to insert.
- * @param tree
- */
- void rotateNodes(RBTree *tree, Node* cur)//TODO what about a NULL uncle
- {
- Node* grandparent = NULL;
- Node* father = NULL;
- while((cur != tree->root)&&(cur->color != BLACK)&&(cur->parent->color == RED))
- {
- father = cur->parent;
- grandparent = cur->parent->parent;
- int result = tree->compFunc(cur->data, cur->parent->data);
- int resultParents = tree->compFunc(cur->parent->data, cur->parent->parent->data);
- if(resultParents < 0)
- {
- Node *uncle = cur->parent->parent->right;
- if((uncle != NULL)&&(uncle->color == RED))
- {
- grandparent->color = RED;
- father->color = BLACK;
- uncle->color = BLACK;
- cur = cur->parent->parent;
- }
- else
- {
- if(resultParents > 0)
- {
- rotateLeft(tree, cur);
- cur = father;
- father = cur->parent;
- }
- rotateRight(tree, cur);
- int fatherColor = father->color;
- int grandpaColor = grandparent->color;
- father->color = grandpaColor;
- grandparent->color = fatherColor;
- cur = father;
- }
- }
- else
- {
- Node *uncle = grandparent->left;
- if((uncle != NULL) && (uncle->color == RED))
- {
- grandparent->color = RED;
- father->color = BLACK;
- uncle->color = BLACK;
- cur = grandparent;
- }
- else
- {
- if(cur = father->left)
- {
- rotateRight(tree, father);
- cur = father;
- father = cur->parent;
- }
- rotateLeft(tree, grandparent);
- int faColor = father->color;
- int grandColor = grandparent->color;
- father->color = grandColor;
- grandparent->color = faColor;
- }
- }
- }
- tree->root->color = BLACK;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement