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

 找回密码
 欢迎注册
数学研发论坛»论坛 › 【算法研发】 › 算法交流 › 红黑树删除操作的疑问
返回列表 发新帖
查看: 8197|回复: 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
  37.        
  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;
  7.        
  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]);
  16.                
  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-5-19 05:34 , Processed in 0.060731 second(s), 20 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

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