红黑树（转）

1. struct mytype {  
2.   
3.     struct rb_node node;  
4.   
5.     char *keystring;  

1. #define container_of(ptr, type, member) ({\  
2.   
3.     const typeof( ((type *)0)->member )*__mptr = (ptr);\  
4.   
5.     (type *)( (char *)__mptr -offsetof(type,member) );})  
6.   
7.     
8.   
9.     #define offsetof(TYPE, MEMBER) ((size_t)&((TYPE *)0)->MEMBER)  

1. ({  
2.   
3.        const typeof( ((struct mytype*)0)->node ) *__mptr = (pnode);  
4.   
5.        (struct mytype *)((char*)__mptr-((size_t)&((struct mytype*)0)->node));  
6.   
7.    })  

1. x = y - offset  
2.   
3.    ---------- rb_node;  
4.   
5.    
6.   
7.        while (node) {  
8.   
9.            struct mytype *data =container_of(node, struct mytype, node);  
10.   
11.            int result;  
12.   
13.             
14.   
15.            result = strcmp(string,data->keystring);  
16.   
17.             
18.   
19.            if (result rb_left;  
20.   
21.            else if (result > 0)  
22.   
23.            node = node->rb_right;  
24.   
25.            else  
26.   
27.            return data;  
28.   
29.        }  
30.   
31.        return NULL;  
32.   
33.    }  

1. int my_insert(struct rb_root *root, structmytype *data)  
2.   
3.     {  
4.   
5.         struct rb_node **new =&(root->rb_node), *parent = NULL;  
6.   
7.          
8.   
9.         /* Figure out where to put new node */  
10.   
11.         while (*new) {  
12.   
13.             struct mytype *this =container_of(*new, struct mytype, node);  
14.   
15.             int result =strcmp(data->keystring, this->keystring);  
16.   
17.          
18.   
19.             parent = *new;  
20.   
21.             if (result rb_left);  
22.   
23.             else if (result > 0)  
24.   
25.                 new =&((*new)->rb_right);  
26.   
27.             else  
28.   
29.                 return FALSE;  
30.   
31.         }  
32.   
33.          
34.   
35.         /* Add new node and rebalance tree. */  
36.   
37.         rb_link_node(data->node, parent,new);  
38.   
39.         rb_insert_color(data->node, root);  
40.   
41.          
42.   
43.         return TRUE;  
44.   
45.     }  

1. struct mytype *data = mysearch(mytree,"walrus");  
2.   
3.    
4.   
5.    if (data) {  
6.   
7.        rb_erase(data->node, mytree);  
8.   
9.        myfree(data);  
10.   
11.    }  

1. Struct rb_node  
2.   
3. {  
4.   
5. 　　unsigned long rb_parent_color; //保存父节点的指针值（父节点的地址）同时保存节点的color  
6.   
7. 　　#defineRB_RED         0  
8.   
9. 　　 #defineRB_BLACK       1  
10.   
11. 　　structrb_node *rb_right; //节点右孩子  
12.   
13. 　　structrb_node *rb_left;   //节点左孩子  
14.   
15. }__attribute__((aligned(sizeof(long))));  

1. struct rb_root  
2.   
3.  {  
4.   
5.         struct rb_node *rb_node;  
6.   
7.  };  

1. include/linux/rbtree.h中有几个与rb_parent_color相关的宏  
2.   
3. #definerb_parent(r)   ((struct rb_node*)((r)->rb_parent_color & ~3))  
4.   
5.  //取 r节点的父节点的地址，即把r节点的后两位清零后与r节点存储的父节点进行与操作。  
6.   
7.  //假设r->rb_parent_color 的内容为 0x20000001(表示父节点的地址为0x20000000,节点颜色为黑),那么执行//此操作后，取得父节点的地址为 0x20000000  
8.   
9. #definerb_color(r)   ((r)->rb_parent_color& 1)  
10.   
11. // 设置r节点的颜色为黑 ,只要看最后一位即可.  
12.   
13. #definerb_is_red(r)   (!rb_color(r))  
14.   
15. // 测试r节点是否为红  
16.   
17. #definerb_is_black(r) rb_color(r)  
18.   
19. //测试r节点是否为黑  
20.   
21. #definerb_set_red(r)  do {(r)->rb_parent_color &= ~1; } while (0)  
22.   
23. //设置r节点是为红  
24.   
25. #definerb_set_black(r)  do {(r)->rb_parent_color |= 1; } while (0)  
26.   
27.  //设置r节点是为黑  
28.   
29.   //内联函数，设置节点的父节点  
30.   
31.  static inline voidrb_set_parent(struct rb_node *rb, struct rb_node *p)  
32.   
33.  {  
34.   
35.          rb->rb_parent_color =(rb->rb_parent_color & 3) | (unsigned long)p;  
36.   
37.  }  
38.   
39.   //内联函数，设置节点的color  
40.   
41.  static inline voidrb_set_color(struct rb_node *rb, int color)  
42.   
43.  {  
44.   
45.          rb->rb_parent_color =(rb->rb_parent_color & ~1) | color;  
46.   
47.  }    

1.5 RB树的操作

红黑树的最主要特征，在于其颜色满足特定的性质。普通的节点添加，极有可能破坏红黑树的性质，所以在添加红黑树节点时，需要将整个红黑树的颜色进行调整。
在理解插入、删除操作之前要先理解两个函数，即红黑树的左旋和右旋。

左旋和右旋都是为了保证平衡二叉树的性质不变，即是通过左旋和右旋来保证红黑二叉树的第五条性质满足。红黑二叉树的添加跟普通的二叉树的添加类似。不过在添加节点后需要对节点的颜色进行调整，甚至对树的结构进行调整，来满足红黑树的性质。

1.5.1左旋

对照下图可以更好的理解下面的程序。将node设置为pivot，root为根。

//记住设置节点的左右孩子后，还要设置节点的parent