二叉搜索树
（一）概念
一个二叉搜索树是一个节点有序的二叉树，
（1）根的左分支节点值都小于根节点的值
（2）右分支节点值都大于根节点值
（3）所有子树也都是二叉搜索树

自平衡二叉搜索树
平衡二叉树：一个所有叶子节点的深度差不超过1的二叉搜索树
自平衡二叉搜索树：是指其操作都试图维持平衡的二叉搜索树


红黑树
红黑树是一种自平衡二叉搜索树，红黑树有以下特性：
       1.每个节点不是黑色就是红色的
       2.根节点是黑色的
       3.每个叶节点(NIL)是黑色的
       4.如果一个节点是红色的，那么它的两个子女都是黑色的
       5.从某一个节点到达其子孙叶节点的每一条简单路径上包含相同数量的黑色节点
linux内核中实现的红黑树为rbtree,在rbtree.c文件中，红黑树的优点是所有操作都可以在O（log n）时间内完成，、

linux内核中红黑树的节点用以下结构体表示：

[cpp] view plaincopy

 

1. 100 struct rb_node  
2. 101 {  
3. 102         unsigned long  rb_parent_color;  
4. 103 #define RB_RED          0  
5. 104 #define RB_BLACK        1  
6. 105         struct rb_node *rb_right;  
7. 106         struct rb_node *rb_left;  
8. 107 } __attribute__((aligned(sizeof(long))));  

linux的rb_node结构体中隐藏了一个指向其父节点的指针，在rb_parent_color成员中，因为表示红黑只需要一个bit，而指针是以4字节对齐

[cpp] view plaincopy

 

1. 116 #define rb_parent(r)   ((struct rb_node *)((r)->rb_parent_color & ~3))  
2. 117 #define rb_color(r)   ((r)->rb_parent_color & 1)  

linux内核通过红黑树找到具体成员是通过容器的形式实现的
#define containner_of(ptr,type,member)

红黑树的根节点以如下的形式表现，这样做的好处是可以不用传递二级指针

[cpp] view plaincopy

 

1. #define RB_ROOT (struct rb_root) { NULL, }  
2. 110 struct rb_root  
3. 111 {  
4. 112         struct rb_node *rb_node;  
5. 113 };  

（二）红黑树的左旋，右旋以及插入操作

关于左旋和右旋具体图解可以参考如下网址点击打开链接

rbtree.c中关于左旋的代码如下所示：

[cpp] view plaincopy

 

1. 26 static void __rb_rotate_left(struct rb_node *node, struct rb_root *root)  
2. 27 {  
3. 28         struct rb_node *right = node->rb_right;  
4. 29         struct rb_node *parent = rb_parent(node);  
5. 30   
6. 31         if ((node->rb_right = right->rb_left))  
7. 32                 rb_set_parent(right->rb_left, node);  
8. 33         right->rb_left = node;  
9. 34   
10. 35         rb_set_parent(right, parent);  
11. 36   
12. 37         if (parent)  
13. 38         {  
14. 39                 if (node == parent->rb_left)  
15. 40                         parent->rb_left = right;  
16. 41                 else  
17. 42                         parent->rb_right = right;  
18. 43         }  
19. 44         else  
20. 45                 root->rb_node = right;  
21. 46         rb_set_parent(node, right);  
22. 47 }  

 红黑树的插入可以参考以下网址点击打开链接

红黑树详细讲解

[数据结构]红黑树