数学研发网设为首页收藏本站
切换到窄版

 找回密码
 欢迎注册
数学研发论坛»论坛 › 【算法研发】 › 算法交流 › 红黑树删除操作的疑问
返回列表 发新帖
查看: 12216|回复: 2

[提问] 红黑树删除操作的疑问

[复制链接]
sir_chen
发表于 2010-1-11 20:00:35 | 显示全部楼层 |阅读模式

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要 登录 才可以下载或查看，没有账号？欢迎注册

×
我照着<算法导论>上关于红黑树删除操作的伪代码编写了一个红黑树删除操作,但是测试的时候发现一直出现指针为空操作的异常,算法是完全照着书上的,不知道是书上的算法有问题还是怎么回事. 以下是红黑树的相关代码:
  1. #define and &&
  2. #define or ||
  3. #define NIL NULL
  4. class Node
  5. {
  6. public:
  7. int key;
  8. Node* left; //左孩子
  9. Node* right; //右孩子
  10. Node* parent; //父节点
  11. // int item;
  12. int color;
  13. Node()
  14. {
  15. left=NIL;
  16. right=NIL;
  17. parent=NIL;
  18. color=-1;
  19. }
  20. Node(int key)
  21. {
  22. this->key=key;
  23. left=NIL;
  24. right=NIL;
  25. parent=NIL;
  26. color=-1;
  27. }
  28. };
  29. class RedBlackTree
  30. {
  31. public:
  32. Node *root;
  33. Node* Successor(Node* node);
  34. void Insert(Node* node);
  35. void LeftRotate(Node* node);
  36. void RightRotate(Node* node);
  37. Node* Delete(Node* node);
  38. void InsertFixUp(Node* node);
  39. void DeleteFixUp(Node *node);
  40. Node* Search(int key);
  41. int getNodeNum()
  42. {
  43. return totalNodes;
  44. }
  45. RedBlackTree()
  46. {
  47. root=NIL;
  48. }
  49. };
复制代码
树的相关操作
  1. Node* RedBlackTree::Successor(Node* node)
  2. {
  3. Node* x=node;
  4. Node* y;
  5. if(node->right!=NIL)
  6. return Minimum(node->right);
  7. y=x->parent;
  8. while(y!=NIL and x==y->right)
  9. {
  10. x=y;
  11. y=y->parent;
  12. }
  13. return y;
  14. }
  15. Node* RedBlackTree::Search(int key)
  16. {
  17. Node* x=root;
  18. while((x!=NIL) and (x->key!=key))
  19. {
  20. if(key<x->key)
  21. x=x->left;
  22. else
  23. x=x->right;
  24. }
  25. return x;
  26. }
  27. void RedBlackTree::LeftRotate(Node* node)
  28. {
  29. Node* x=node;
  30. Node* y=node->right;
  31. if(x->right!=NIL and y!=NIL)
  32. x->right=y->left;//Turn y's left subtree into x's subtree
  33. if(y!=NIL and y->left!=NIL)
  34. y->left->parent=x;
  35. if(y!=NIL)
  36. y->parent=x->parent;//Link x's parent to y
  38. if(x->parent==NIL)
  39. root=y;
  40. else
  41. {
  42. if(x==x->parent->left)
  43. x->parent->left=y;
  44. else x->parent->right=y;
  45. }
  46. y->left=x;
  47. x->parent=y;
  48. }
  49. void RedBlackTree::RightRotate(Node* node)
  50. {
  51. Node* y=node;
  52. Node* x=node->left;
  53. y->left=x->right;
  54. if(x->right!=NIL)
  55. x->right->parent=y;
  56. x->parent=y->parent;
  57. if(y->parent==NIL)
  58. root=x;
  59. else
  60. {
  61. if(y==y->parent->left)
  62. y->parent->left=x;
  63. else y->parent->right=x;
  64. }
  65. x->right=y;
  66. y->parent=x;
  67. }
  68. void RedBlackTree::Insert(Node* node)
  69. {
  70. Node* x=root;
  71. Node* y=NIL;
  72. while(x!=NIL)
  73. {
  74. y=x;
  75. if(node->key<x->key)
  76. x=x->left;
  77. else x=x->right;
  78. }
  79. node->parent=y;
  80. if(y==NIL)
  81. root=node;
  82. else
  83. {
  84. if(node->key<y->key)
  85. y->left=node;
  86. else y->right=node;
  87. }
  88. node->left=NIL;
  89. node->right=NIL;
  90. node->color=RED;
  91. InsertFixUp(node);
  92. totalNodes++;
  93. }
  95. void RedBlackTree::InsertFixUp(Node* node)
  96. {
  97. Node* z=node;
  98. Node* y;
  99. while(z->parent!=NIL and z->parent->color==RED)
  100. {
  101. if(z->parent==z->parent->parent->left)
  102. {
  103. y=z->parent->parent->right;
  104. if(y!=NIL and y->color==RED)
  105. {
  106. z->parent->color=BLACK;
  107. y->color=BLACK;
  108. z->parent->parent->color=RED;
  109. z=z->parent->parent;
  110. }
  111. else
  112. {
  113. if(z==z->parent->right)
  114. {
  115. z=z->parent;
  116. LeftRotate(z);
  117. }
  118. z->parent->color=BLACK;
  119. z->parent->parent->color=RED;
  120. RightRotate(z->parent->parent);
  121. }
  122. }
  123. else
  124. {
  125. y=z->parent->parent->left;
  126. if(y!=NIL and y->color==RED)
  127. {
  128. z->parent->color=BLACK;
  129. y->color=BLACK;
  130. z->parent->parent->color=RED;
  131. z=z->parent->parent;
  132. }
  133. else
  134. {
  135. if(z==z->parent->left)
  136. {
  137. z=z->parent;
  138. RightRotate(z);
  139. }
  140. z->parent->color=BLACK;
  141. z->parent->parent->color=RED;
  142. LeftRotate(z->parent->parent);
  143. }
  144. }
  145. }
  146. root->color=BLACK;
  147. }
  149. Node* RedBlackTree::Delete(Node* node)
  150. {
  151. Node* z=node;
  152. Node* x;
  153. Node* y;
  154. if(z->left==NIL or z->right==NIL)
  155. y=z;
  156. else y=Successor(z);
  157. if(y->left!=NIL)
  158. x=y->left;
  159. else x=y->right;
  160. if(x!=NIL)
  161. x->parent=y->parent;
  162. if(y->parent==NIL)
  163. root=x;
  164. else
  165. {
  166. if(y==y->parent->left)
  167. y->parent->left=x;
  168. else y->parent->right=x;
  169. }
  170. if(y!=z)
  171. {
  172. z->key=y->key;
  173. z->color=y->color;
  174. //copy y's satellite data into z
  175. }
  176. if(y->color==BLACK)
  177. DeleteFixUp(x);
  178. totalNodes--;
  179. return y;
  180. }
  182. void RedBlackTree::DeleteFixUp(Node* node)
  183. {
  184. Node* x=node;
  185. Node* w;
  186. while(x!=root and x->color==BLACK)
  187. {
  188. if(x==x->parent->left)
  189. {
  190. w=x->parent->right;
  191. if(w->color==RED)
  192. {
  193. w->color=BLACK;
  194. x->parent->color=RED;
  195. LeftRotate(x->parent);
  196. w=x->parent->right;
  197. }
  198. if(w->left->color==BLACK and w->right->color==BLACK)
  199. {
  200. w->color=RED;
  201. x=x->parent;
  202. }
  203. else
  204. {
  205. if(w->right->color==BLACK)
  206. {
  207. w->left->color=BLACK;
  208. w->color=RED;
  209. RightRotate(w);
  210. w=x->parent->right;
  211. }
  212. w->color=x->parent->color;
  213. x->parent->color=BLACK;
  214. w->right->color=BLACK;
  215. LeftRotate(x->parent);
  216. x=root;
  217. }
  218. }
  219. else
  220. {
  221. w=x->parent->left;
  222. if(w->color==RED)
  223. {
  224. w->color=BLACK;
  225. x->parent->color=RED;
  226. RightRotate(x->parent);
  227. w=x->parent->left;
  228. }
  229. if(w->right->color==BLACK and w->left->color==BLACK)
  230. {
  231. w->color=RED;
  232. x=x->parent;
  233. }
  234. else
  235. {
  236. if(w->left->color==BLACK)
  237. {
  238. w->right->color=BLACK;
  239. w->color=RED;
  240. LeftRotate(w);
  241. w=x->parent->left;
  242. }
  243. w->color=x->parent->color;
  244. x->parent->color=BLACK;
  245. w->left->color=BLACK;
  246. RightRotate(x->parent);
  247. x=root;
  248. }
  249. }
  250. x->color=BLACK;
  251. }
  252. }
复制代码
测试函数:
  1. void main()
  2. {
  3. Node *node[100];
  4. Node *x;
  5. RedBlackTree t;
  6. //BinarySearchTree t;
  8. int key[]={5,3,8,2,4,7,9,1,6,10};
  9. int i,j,k;
  10. int n=sizeof(key)/sizeof(*key);
  12. for(i=0;i<n;i++)
  13. {
  14. node[i]=new Node(key[i]);
  15. t.Insert(node[i]);
  17. }
  18. printf("root->key=%d\n",t.root->key);
  19. printf("\n");//i=0;
  20. for(i=0;i<n;i++)
  21. {
  22. x=t.Delete(t.Search(i+1));
  23. printf("delete key=%d\n",x->key);
  24. printf("root->key=%d\n",t.root->key);
  25. printf("\n\n");
  26. }
  27. }
复制代码
每次运行循环进行了两次就出现了异常,通过Debug发现在第2轮循环DeleteFixUp操作中node为空指针,由此出现了异常.以上的DeleteFixUp是照着书上编的, 估计伪代码也有问题, 不知道如何改正
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复

使用道具 举报

sir_chen
 楼主| 发表于 2010-1-11 20:03:36 | 显示全部楼层
昨天在测试Insert操作时也出现了同样的情况,但是今天重新运行昨天的代码却又没有问题了.但是Delete操作一直有问题.
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

sir_chen
 楼主| 发表于 2010-1-11 20:35:35 | 显示全部楼层
以下是仅能正常输出的部分,由于输出树形结构的代码很长,所以这里给出的代码仅输出根结点
bug.PNG
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-11-25 11:21 , Processed in 0.030106 second(s), 20 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表