Advertisement
Guest User

Untitled

a guest
Dec 12th, 2019
122
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.25 KB | None | 0 0
  1. void rotateRight(RBTree *tree, Node* node)
  2. {
  3. Node *cur = node->left;
  4. node->left = cur->right;
  5. if(node->left != NULL)
  6. {
  7. node->left->parent = node;
  8. }
  9. cur->left = node;
  10. if(node->parent == NULL)
  11. {
  12. tree->root = cur;
  13. }
  14. else if(node == node->parent->left)
  15. {
  16. node->parent->left = cur;
  17. }
  18. else
  19. {
  20. node->parent->right = cur;
  21. }
  22. cur->right = node;
  23. node->parent = cur;
  24. }
  25. void rotateLeft(RBTree *tree, Node* node)
  26. {
  27. Node *cur = node->right;
  28. node->right = cur->left;
  29. if(node->right != NULL)
  30. {
  31. node->right->parent = node;
  32. }
  33. cur->left = node;
  34. if(node->parent == NULL)
  35. {
  36. tree->root = cur;
  37. }
  38. else if(node == node->parent->left)
  39. {
  40. node->parent->left = cur;
  41. }
  42. else
  43. {
  44. node->parent->right = cur;
  45. }
  46. cur->left = node;
  47. node->parent = cur;
  48. }
  49. /**
  50. * given a node and a tree rotate the tree's nodes according to the
  51. * current situation
  52. * @param cur - the node we want to insert.
  53. * @param tree
  54. */
  55. void rotateNodes(RBTree *tree, Node* cur)//TODO what about a NULL uncle
  56. {
  57. Node* grandparent = NULL;
  58. Node* father = NULL;
  59.  
  60. while((cur != tree->root)&&(cur->color != BLACK)&&(cur->parent->color == RED))
  61. {
  62. father = cur->parent;
  63. grandparent = cur->parent->parent;
  64. int result = tree->compFunc(cur->data, cur->parent->data);
  65. int resultParents = tree->compFunc(cur->parent->data, cur->parent->parent->data);
  66. if(resultParents < 0)
  67. {
  68. Node *uncle = cur->parent->parent->right;
  69. if((uncle != NULL)&&(uncle->color == RED))
  70. {
  71. grandparent->color = RED;
  72. father->color = BLACK;
  73. uncle->color = BLACK;
  74. cur = cur->parent->parent;
  75. }
  76. else
  77. {
  78. if(resultParents > 0)
  79. {
  80. rotateLeft(tree, cur);
  81. cur = father;
  82. father = cur->parent;
  83. }
  84. rotateRight(tree, cur);
  85. int fatherColor = father->color;
  86. int grandpaColor = grandparent->color;
  87. father->color = grandpaColor;
  88. grandparent->color = fatherColor;
  89. cur = father;
  90. }
  91. }
  92. else
  93. {
  94. Node *uncle = grandparent->left;
  95. if((uncle != NULL) && (uncle->color == RED))
  96. {
  97. grandparent->color = RED;
  98. father->color = BLACK;
  99. uncle->color = BLACK;
  100. cur = grandparent;
  101. }
  102. else
  103. {
  104. if(cur = father->left)
  105. {
  106. rotateRight(tree, father);
  107. cur = father;
  108. father = cur->parent;
  109. }
  110. rotateLeft(tree, grandparent);
  111. int faColor = father->color;
  112. int grandColor = grandparent->color;
  113. father->color = grandColor;
  114. grandparent->color = faColor;
  115. }
  116. }
  117. }
  118. tree->root->color = BLACK;
  119. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement