重要概念
红黑树的资料网上资料很多，对红黑树的定义、性质、以及操作都做了详细的分析，这篇博文也参考了网上的部分文章，不过主要是学习了腾讯课堂-零声king老师的课之后，对红黑树的一些理解。肯定有一些错误的地方，如果觉得不对，可以给我指出。
参考资料
如果你对红黑树的基本概念，用途，性质等不了解，那么请先看红黑树(一)之 原理和算法详细介绍的文章，里面对红黑树的了解很仔细，这篇博客主要是用C语言来实现红黑树。
红黑树性质
（1）每个节点或者是黑色，或者是红色。
（2）根节点是黑色。
（3）每个叶子节点（NIL）是黑色。 [注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！]
（4）如果一个节点是红色的，则它的子节点必须是黑色的。
（5）从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。
特别是要理解第3条性质的叶子节点（NIL）的概念：红黑树的叶子节点不同于二叉树的叶子节点的概念：二叉树里面 叶子是最下面的。 红黑树在表述的时候，叶子是隐藏不表述的,如果还是不懂，可以在代码里去看实现，代码里有对NIL的说明。
红黑树用途
在说明红黑树的用途之前，我们要知道有很多类似红黑树的结构，比如AVL树、B+树、B-树等。红黑树最基本的是一颗二叉查找树，那么就需要满足二叉查找树的性质，最基本的就是左子树节点的key值要小于根节点，根节点值要小于右子树的值。但是由于二叉查找树可能会由于节点的key的分布问题，导致查找效率很慢，最差的查询情况会导致为O(n)(即是说单向链表的情况)。AVL树则是左右高度平衡树（左右高度相差不超过1），AVL每个节点有一个表示高度的属性，每次插入一个节点，都要判断左右子树的高度，然后在决定是否需要进行相应的调整，这就存在在插入时会频繁的进行旋转操作。
红黑树的主要有2个用途：（1）利用红黑树是按照中序排序是有序的（2）利用key去查找结点
红黑树相对于二叉排序树和AVL树的一个折衷，即是插入节点或者删除节点时可能不需要AVL树那么频繁的左旋或者右旋的操作**（频繁的左旋和右旋也需要花费大量的时间），红黑树不需要左右子树高度相差1，从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点即可**，而且比二叉查找树的查询效率要高（这是二叉查找树在最坏的情况的查询效率为O(n),这种情况是当我们在构建二叉树时，每次添加的节点要么是升序，要么是降序），因此通常，红黑树优于二叉排序树和AVL树。
红黑树的实现主要在各种语言的MAP,SET中，比如JAVA的TreeMap，TreeSet,C++ STL中的set、map，在应用方面有内存管理、CFS（完全公平调度算法）、以及定时器,nginx等应用中。
比如STL的std::map的底层实现使用的红黑树，我们知道map是由key和value组成的键值对，比较时，std::map为有序的，以key作为排序。 通常std::map的查询效率比较高，查询效率为O(logn)(这是由红黑树的查询效率决定的)。
在比如内存管理中，我们知道表示分配的内存可以有2种表示方式：一种是起始位置+内存块的长度，另一种是起始位置+结束位置。假如我们以前一种为例，每次分配内存时，我们就根据当前分配内存的起始位置作为key插入到红黑树中，分配的起始位置最小的一块内存，一定是树的最左下角的节点（由红黑树的中序排序是有序决定的），同时将value设置为分配内存块的大小，同时使用一个指针指向分配的节点(方便我们知道在何处分配了内存，以便可以快速操作分配的内存)
特别说明
很多重要的概念以及实现的详细过程都在本文说明的参考资料进行了详细的说明，特别希望对红黑树不理解的朋友去看了这篇博客在来看红黑树的实现代码。
参考资料里面有一个小错误，把右旋说成了左旋。一眼就可以发现错误。红黑树最重要的操作时插入和删除操作。
主要分析了插入操作，删除或者其他操作请读者自己分析。
红黑树操作
左右旋转
旋转不是红黑树特有的性质，平衡二叉树AVL也具有左右旋转的操作，AVL树旋转的目的是主要是为了保持左右子树的相差高度不超过1，红黑色的旋转主要是为了保持红黑树的特性。在对红黑树做插入或者删除操作之前，树满足红黑色的性质。如果在一个红色结点下插入一个红色的结点，那么插入操作过后就违背了红黑树的性质4，要通过旋转来再次满足红黑色的性质，注意每次插入的节点都必须是红色。参考文章有说明
由于在插入节点和删除节点时，经常会打破红黑树的平衡(不在满足红黑树的性质)，因此需要将旋转操作作为一个原子操作(代码体现就是一个具体的函数)，由于旋转不是红黑树特有的，因此旋转不涉及到颜色的操作，判断插入和删除之后是否需要旋转红黑树是由插入和删除节点之后，如果不满足红黑树特性，就需要旋转。
左旋
对x进行左旋，意味着"将x变成一个左节点"。首选不管左旋还是右旋，要把某个节点作为基准点，然后往下旋转变成孩子节点的孩子，具体来说，左旋之后，自身变成右孩子的左节点。以图片来说从左变成右需要修改3个方向，6个指针来完成（注意1个方向有2个指针）。
仔细观察左旋，由于左旋之后，Y的父指针指向了X的父指针，因此我们在表示红黑树结点结构体时，需要使用父指针的缘故
（1）X->right = Y->left(β)
（2） Y->left->parent = X
（3） Y->parent = X->parent
（4） X->parent = Y（注意）
（5） Y->left = X
（6） X->parent = Y
代码如下
//左旋-插入和删除时调整树 void rbtree_left_rotate(rbtree *T, rbtree_node *x) { rbtree_node *y = x->right; x->right = y->left; //1 1 x的右指针设置为右孩子的左指针 if (y->left != T->nil) { //1 2 y->left->parent = x; } y->parent = x->parent; //1 3 将y的父亲指针连接到X的父亲商 if (x->parent == T->nil) { //1 4 如果X为根节点 T->root = y;//将Y设置为根节点 } else if (x == x->parent->left) { //如果当前旋转节点位于其父亲节点树在树的左边，需要作为在树的左边分支 x->parent->left = y; } else { //树的右边，那么就需要作为树的右边分支 x->parent->right = y; } y->left = x; //1 5 x->parent = y; //1 6 }
右旋
右旋恰好和左旋相反，右旋之后，参考点（图片的Y）来说，变成左孩子的右节点，同样也是需要经过3个方向，6个指针完成右旋。具体来说，在具体实现的时候，可以将左旋代码搬过来，然后x变成y，y变成x，left变成right，right变成left）
插入和删除节点
我们以下图来作为例子来说明插入和删除操作
在插入和删除节点之前，都需要满足红黑树性质，请记住这个在插入和删除当中是前提条件，同时我这里说明一下，图中的1，86，129，296等都不是叶子节点，叶子节点不会在红黑树中显示出来，我们使用Nil来代替，像节点1的左右子树都是Nil
插入节点
在介绍插入节点步骤之前，我们先介绍一下，我们需要将插入的节点的颜色设置为红色，假如我们设置为黑树，那么必然会造成旋转操作，仔细想一想，在插入之前，已经满足红黑树性质，如果往一边添加黑色节点，必然添加黑色节点的一边多余另一边，从而造成旋转，如果设置为红色，可能不会引起旋转操作，比如添加670节点，会作为673的左子树添加。添加操作并不会引起旋转操作，因此，为了方便，插入的节点的颜色设置为红色。
由于插入节点之后可能会引起旋转操作，我们观察前面的旋转操作，一般会涉及到添加节点，节点的父节点，以及节点父节点的父节点3个节点，我们以添加350节点为例来说明，350节点会添加到344的右边。由于添加的350节点为红色，父节点344也为红色，那么需要旋转。那么要如何旋转359，344，350，达到最终的平衡呢，首先以344为旋转节点左旋，最终从上到下为359，350，344，350为359的左子树，344为350的左子树；然后在以350右旋，形成350作为344和359的左右子树。然后将350修改为黑色，359修改为红色，这样就达到了平衡，注意，如果不太清楚的朋友，需要自己使用草稿自己把图画出来。
插入节点时，主要有以下三个步骤：
（1）根据插入结点的key找到要插入的位置**(从根节点开始从上往下一直寻找)**
（2）初始化节点的相关属性**(节点key，value已初始化，parent需要找到插入位置在设置，颜色设置为红色，左右孩子设置在为Nil)**
（3）插入修正处理（左旋，右旋，或者修改节点颜色）使得满足红黑色性质。
其中插入的（1)(2)是插入的必须步骤，第（3）步却是可选的。比如插入670，就不需要左插入修正处理，因为父节点673是黑色，插入670(红色)节点并不会影响红黑树的性质，不需要旋转操作。但是如前面提到的添加350，却是要进行插入修正处理，保证插入节点后，同样能保证树满足红黑树的性质。那么在需要进行步骤(3)的时候，插入的节点的情况到底分为几种呢，这个需要同学们自己拿出草稿自己画出来。下面简单的说一下
首先，插入节点是红色(插入节点要求)，插入节点的父亲必须是红色(如果是黑色就不需要旋转)，插入节点的父节点的父节点必须是黑色(如果是红色，在插入之前不满足红黑树)，同时，还需要关注插入节点的叔父节点（插入节点的父节点的兄弟节点）情况，我们以上面359与344，539，470和549 2棵子树来分析，前面说过插入350，需要进行2次旋转；而如果我们插入480.却不需要进行旋转操作，具体操作就是将539变为红色，470，549变为黑色，480为红色，这样不需要旋转就能满足红黑树的性质。起始我们已经确定插入节点，插入节点的父节点，插入节点的父节点的父节点的颜色，那么只要确定叔父节点的情况即可，其实就只有以下2种情况：
（1）叔父节点不存在(Nil)，即前面提到的359，344，要插入350的情况，另外如果插入340和350的操作也是不一样的。插入340，只需要以344为旋转中心右旋，然后修改344为黑色，359为红色即可。
(2) 叔父节点为红色
叔父节点是不可能为黑色的，假如为黑色，树本身是不满足红黑树性质的。
以上例子都是将节点插入到左子树的情况，将节点插入到右子树的情况和左子树类似，同学们自己去分析即可。
删除节点
将红黑树内的某一个节点删除。需要执行的操作依次是：首先，将红黑树当作一颗二叉查找树，将该节点从二叉查找树中删除；然后，通过"旋转和重新着色"等一系列来修正该树，使之重新成为一棵红黑树。删除节点操作我这里就不展开细节了，因为我也没有完全理解。
红黑树的遍历
代码实现
#include <stdio.h> #include <stdlib.h> #include <string.h> #define RED 1 #define BLACK 2 typedef int KEY_TYPE; typedef struct _rbtree_node { unsigned char color; struct _rbtree_node *right; struct _rbtree_node *left; struct _rbtree_node *parent;//旋转时需要用到父结点的指针 KEY_TYPE key; void *value; } rbtree_node; typedef struct _rbtree { rbtree_node *root; //公用的nil节点-可以理解为隐藏的叶子节点 //（也可以理解为一个万能的"空"节点， //所有节点的3个指针没有具体指向时，需要指向这个节点 rbtree_node *nil; } rbtree; rbtree_node *rbtree_mini(rbtree *T, rbtree_node *x) { while (x->left != T->nil) { x = x->left; } return x; } rbtree_node *rbtree_maxi(rbtree *T, rbtree_node *x) { while (x->right != T->nil) { x = x->right; } return x; } rbtree_node *rbtree_successor(rbtree *T, rbtree_node *x) { rbtree_node *y = x->parent; if (x->right != T->nil) { return rbtree_mini(T, x->right); } while ((y != T->nil) && (x == y->right)) { x = y; y = y->parent; } return y; } //左旋-插入和删除时调整树 void rbtree_left_rotate(rbtree *T, rbtree_node *x) { rbtree_node *y = x->right; x->right = y->left; //1 1 x的右指针设置为右孩子的左指针 if (y->left != T->nil) { //1 2 y->left->parent = x; } y->parent = x->parent; //1 3 if (x->parent == T->nil) { //1 4 T->root = y; } else if (x == x->parent->left) { x->parent->left = y; } else { x->parent->right = y; } y->left = x; //1 5 x->parent = y; //1 6 } //右旋-插入和删除时调整树（和左旋的实现的代码区别， //x变成y，y变成x，left变成right，right变成left） void rbtree_right_rotate(rbtree *T, rbtree_node *y) { rbtree_node *x = y->left; y->left = x->right; if (x->right != T->nil) { x->right->parent = y; } x->parent = y->parent; if (y->parent == T->nil) { T->root = x; } else if (y == y->parent->right) { y->parent->right = x; } else { y->parent->left = x; } x->right = y; y->parent = x; } //插入修正处理-为了保持红黑树的性质（要保证插入之后也是一棵红黑树） //要想理解这个过程，请自己画图表示-重点是理解红黑树性质 void rbtree_insert_fixup(rbtree *T, rbtree_node *z) { //为什么需要while? 从insert调用的第一步可以先当成if来理解 //然后看后面有z---->RED代表递归处理祖父节点。 while (z->parent->color == RED) { //z ---> RED ，父亲是红色违背了红黑树的性质4 if (z->parent == z->parent->parent->left) {//父亲节点是祖父节点的左孩子 rbtree_node *y = z->parent->parent->right; if (y->color == RED) {//叔父节点是红色，这种情况不需要旋转， z->parent->color = BLACK;// y->color = BLACK; z->parent->parent->color = RED;//注意，这里修改了祖父的颜色为红 //这里为什么将z设置为z的祖父，然后进行循环处理呢？因为上面一句代码将祖父设置为了红，那么祖父的父亲 //会不会也为红呢？是不是又违背了红黑树的性质4呢。那么指导为什么要使用while循环递归处理了吧 z = z->parent->parent; //z --> RED, } else {//叔叔是黑色 if (z == z->parent->right) {//当前节点是是父亲右孩子,将当前节点旋转到和父亲与祖父都在左子树中 z = z->parent;//将“父节点”作为“新的当前节点”。 rbtree_left_rotate(T, z);//以“新的当前节点”为支点进行左旋。 } z->parent->color = BLACK;//插入的节点变为黑色 z->parent->parent->color = RED;//祖父节点变为红色 //祖父节点为基点，右旋，此时插入的节点为父亲节点、祖父节点的父亲，父亲为左节点，祖父变成右节点。 rbtree_right_rotate(T, z->parent->parent); } }else {//父亲节点是祖父节点的左孩子，类似上面的分析 rbtree_node *y = z->parent->parent->left; if (y->color == RED) { z->parent->color = BLACK; y->color = BLACK; z->parent->parent->color = RED; z = z->parent->parent; //z --> RED } else { if (z == z->parent->left) { z = z->parent; rbtree_right_rotate(T, z); } z->parent->color = BLACK; z->parent->parent->color = RED; rbtree_left_rotate(T, z->parent->parent); } } } T->root->color = BLACK; } //代码的详细说明在博客的引文都有详细说明 void rbtree_insert(rbtree *T, rbtree_node *z) { rbtree_node *y = T->nil; //新建节点y，初始设置为nil节点（表示插入节点的父亲节点） rbtree_node *x = T->root; // while (x != T->nil) {//藏根节点循环找到要插入的位置 y = x; if (z->key < x->key) {//插入的节点值在树的左边 x = x->left; } else if (z->key > x->key) { x = x->right; } Exist，插入的节点的key,红黑树已经存在对应的key， //不做任何操作，这个要看具体的逻辑，比如在定时器来串联任务时， //用红黑树来表示多个定期器时，这就相当于2个任务在同一个时间 //执行，这时候如果不插入，那么就相当于丢掉了一个任务。 //实现时，需要将定时器的key+一个很小值，或者key减去一个很小值， //然后在进行插入。 else { return ; } } z->parent = y; if (y == T->nil) {//要插入的节点的父亲节点为NULL,将z设置为根节点 T->root = z;// } else if (z->key < y->key) {//若“z所包含的值” < “z父亲所包含的值”，则将z设为“z父亲的左孩子” y->left = z; } else { y->right = z; } z->left = T->nil;//左右指向公共的节点 z->right = T->nil; z->color = RED;//默认为红色(请参考博客引文说明为啥需要为红色) rbtree_insert_fixup(T, z); } void rbtree_delete_fixup(rbtree *T, rbtree_node *x) { while ((x != T->root) && (x->color == BLACK)) { if (x == x->parent->left) { rbtree_node *w= x->parent->right; if (w->color == RED) { w->color = BLACK; x->parent->color = RED; rbtree_left_rotate(T, x->parent); w = x->parent->right; } if ((w->left->color == BLACK) && (w->right->color == BLACK)) { w->color = RED; x = x->parent; } else { if (w->right->color == BLACK) { w->left->color = BLACK; w->color = RED; rbtree_right_rotate(T, w); w = x->parent->right; } w->color = x->parent->color; x->parent->color = BLACK; w->right->color = BLACK; rbtree_left_rotate(T, x->parent); x = T->root; } } else { rbtree_node *w = x->parent->left; if (w->color == RED) { w->color = BLACK; x->parent->color = RED; rbtree_right_rotate(T, x->parent); w = x->parent->left; } if ((w->left->color == BLACK) && (w->right->color == BLACK)) { w->color = RED; x = x->parent; } else { if (w->left->color == BLACK) { w->right->color = BLACK; w->color = RED; rbtree_left_rotate(T, w); w = x->parent->left; } w->color = x->parent->color; x->parent->color = BLACK; w->left->color = BLACK; rbtree_right_rotate(T, x->parent); x = T->root; } } } x->color = BLACK; } rbtree_node *rbtree_delete(rbtree *T, rbtree_node *z) { rbtree_node *y = T->nil; rbtree_node *x = T->nil; if ((z->left == T->nil) || (z->right == T->nil)) { y = z; } else { y = rbtree_successor(T, z); } if (y->left != T->nil) { x = y->left; } else if (y->right != T->nil) { x = y->right; } x->parent = y->parent; if (y->parent == T->nil) { T->root = x; } else if (y == y->parent->left) { y->parent->left = x; } else { y->parent->right = x; } if (y != z) { z->key = y->key; z->value = y->value; } if (y->color == BLACK) { rbtree_delete_fixup(T, x); } return y; } rbtree_node *rbtree_search(rbtree *T, KEY_TYPE key) { rbtree_node *node = T->root; while (node != T->nil) { if (key < node->key) { node = node->left; } else if (key > node->key) { node = node->right; } else { return node; } } return T->nil; } void rbtree_traversal(rbtree *T, rbtree_node *node) { if (node != T->nil) { rbtree_traversal(T, node->left); printf("key:%d, color:%d\n", node->key, node->color); rbtree_traversal(T, node->right); } } int main() { int keyArray[20] = {24,25,13,35,23, 26,67,47,38,98, 20,19,17,49,12, 21,9,18,14,15}; rbtree *T = (rbtree *)malloc(sizeof(rbtree)); if (T == NULL) { printf("malloc failed\n"); return -1; } //初始化nil节点 T->nil = (rbtree_node*)malloc(sizeof(rbtree_node)); T->nil->color = BLACK;//默认nil的节点为黑色，红黑树性质3 T->root = T->nil;//root默认指向nil，代表还没有结点 rbtree_node *node = T->nil; int i = 0; for (i = 0;i < 20;i ++) { node = (rbtree_node*)malloc(sizeof(rbtree_node));//分配节点内存 node->key = keyArray[i]; node->value = NULL; rbtree_insert(T, node); } rbtree_traversal(T, T->root); printf("----------------------------------------\n"); for (i = 0;i < 20;i ++) { rbtree_node *node = rbtree_search(T, keyArray[i]); rbtree_node *cur = rbtree_delete(T, node); free(cur); rbtree_traversal(T, T->root); printf("----------------------------------------\n"); } }
动图分析
代码说明
代码来源：零声学院-king老师，本文还没完成，会继续完善
