<<算法导论>>一起学之二:红黑树的实现C源码

anthony1983

看到红黑树就头大~~~~

anthony1983

好像所有的平衡二叉树的删除操作都很麻烦~~~~~

iceviewer

  哈哈，跟你一起看，不懂就骚扰你

yjm0573

1. 
   
2. /*-----------------------------------------------------------
   
3. |        函数作用:查找key值对应的结点指针
   
4. |        输入参数:根节点root,待查找关键值key
   
5. |        返回参数:如果找到返回结点指针,否则返回NULL
   
6. -------------------------------------------------------------*/
   
7. PRBTree Find_Node(PRBTree root, KEY key)
   
8. {
   
9.         PRBTree x;
   
10. 
    
11.         // 找到key所在的node
    
12.         x = root;
    
13.         do
    
14.         {
    
15.                 if (key == x->key)
    
16.                         break;
    
17.                 if (key < x->key)
    
18.                 {
    
19.                         if (NULL != x->left)
    
20.                                 x = x->left;
    
21.                         else
    
22.                                 break;
    
23.                 }
    
24.                 else
    
25.                 {
    
26.                         if (NULL != x->right)
    
27.                                 x = x->right;
    
28.                         else
    
29.                                 break;
    
30.                 }
    
31.         } while (NULL != x);
    
32. 
    
33.         return x;
    
34. }
    

复制代码

对于这一段：我有点疑问
按你的要求是否应该是这样：

1. 
   
2. /*-----------------------------------------------------------
   
3. |        函数作用:查找key值对应的结点指针
   
4. |        输入参数:根节点root,待查找关键值key
   
5. |        返回参数:如果找到返回结点指针,否则返回NULL
   
6. -------------------------------------------------------------*/
   
7. PRBTree Find_Node(PRBTree root, KEY key)
   
8. {
   
9.         PRBTree x;
   
10. 
    
11.         // 找到key所在的node
    
12.         x = root;
    
13.         do
    
14.         {
    
15.                 if (key == x->key)
    
16.                         break;
    
17.                 if (key < x->key)
    
18.                 {                    
    
19.                        x = x->left;                     
    
20.                 }
    
21.                 else
    
22.                 {
    
23.                        x = x->right;                  
    
24.                 }
    
25.         } while (NULL != x);
    
26. 
    
27.         return x;
    
28. }
    

复制代码

1. 
   
2.     10              
   
3.    / \            
   
4.   5   15  
   
5. / \               
   
6. 3   6   
   

复制代码

假如你要找4，当x指向3的时候，你直接判断其右结点为null, 结果你直接break了，那么这个时候x指向的是3,实际上应该返回的是null.

yjm0573

1. 
   
2. 3)空节点是黑色的（红黑树中，根节点的parent以及所有叶节点lchild、rchild都不指向NULL，而是指向一个定义好的空节点）。
   
3. 
   
4.   // 设置z的左右子树为空并且颜色是red，注意新插入的节点颜色都是red
   
5.         z->parent = y;   
   
6.         z->left = z->right = NULL;
   
7.         z->color = RED;
   

复制代码

看了半天,感觉第3条你没有实现