理解了上面大部分的逻辑之后，我们就可以开始去实现红黑树了，本文用C语言实现了2-3 B树对应的左斜红黑树。

4.1 结构体定义

首先我们要定义红黑树的结构体和接口。

rbtree.h

enum color {BLACK, RED};struct rbnode{ int value; enum color color; struct rbnode *parent; struct rbnode *left; struct rbnode *right;}; struct rbtree{ struct rbnode *root; int size; int depth;}; int insert(struct rbtree *tree, int value);int delete(struct rbtree *tree, int value);struct rbnode * find(struct rbtree *tree, int value);

这个文件也很简单，定义了红黑树节点rbnode，颜色枚举值RED BLACK，以及rbtree，rbtree用来放置红黑树的根节点和一些其它信息。还声明了红黑树的三个接口函数insert、delete 和 find。

对于红黑树来说，find的实现很简单，二叉搜索树的查找：
rbtree.c

struct rbnode * find(struct rbtree *tree, int value){ struct rbnode *p = tree->root; while(p){ if (value == p->value) return p; if (value < p->value) p = p->left; else p = p->right; } return NULL;}

红黑树本身也是个二叉搜索树，所以它的查找函数和二叉搜索树的查找是一样的。

4.2 翻色与旋转代码

下面我们来说下翻色与旋转函数的实现

rbtree.c

static void color_flip_up(struct rbnode *node){ node->color = RED; node->left->color = BLACK; node->right->color = BLACK;} static void color_flip_down(struct rbnode *node){ node->color = BLACK; node->left->color = RED; node->right->color = RED;}

翻色函数很好理解，向上翻色就是把自己变红，把左子和右子都变黑，向下翻色正好相反。

再来看一下旋转函数
rbtree.c

void rotate_left(struct rbtree *tree, struct rbnode *y){ struct rbnode* x = y->right; if(!x) return;  x->parent = y->parent; if(y->parent){ int flag = y == y->parent->left; flag ? (y->parent->left = x) : (y->parent->right = x); } else { tree->root = x; }  y->right = x->left; if(x->left) x->left->parent = y;  x->left = y; y->parent = x;  enum color c = x->color; x->color = y->color; y->color = c; } void rotate_right(struct rbtree *tree, struct rbnode *y){ struct rbnode *x = y->left; if(!x) return;  x->parent = y->parent; if(y->parent){ int flag = y->parent->left == y; flag ? (y->parent->left = x) : (y->parent->right = x); } else { tree->root = x; }  y->left = x->right; if(x->right) x->right->parent = y;  x->right = y; y->parent = x; enum color color = x->color; x->color = y->color; y->color = color;}

我们以左旋为例讲解一下。左旋旋转的是自己和右子，往左旋把自己旋下去了，把右子旋上来了，右子占据了自己的位置，自己成了右子的左子。函数首先做的是交接parent，把右子先挂到parent上去，然后把右子的左子挂接到自己身上，接着让自己成为右子的左子，最后交换二者的颜色，这么做是为了保持两者的连接颜色不变。右旋的逻辑是类似的，这里就不再多讲解了。

4.3 插入操作的代码

代码如下，主要是两个函数，insert和insert_fix。

rbtree.c

int insert(struct rbtree *tree, int value){ struct rbnode *p = malloc(sizeof(*p)); if(!p) return -1;  p->value = value; p->color = RED; p->parent = NULL; p->left = NULL; p->right = NULL;  if(!tree->root){ tree->root = p; p->color = BLACK; tree->size++; tree->depth++; return 0; }  struct rbnode *i = tree->root, *parent; int flag; while(i){ parent = i; if(value < i->value){ i = i->left; flag = 1; } else if(value > i->value){ i = i->right; flag = 0; } else { free(p); return -1; } }  p->parent = parent; flag ? (parent->left = p) : (parent->right = p); insert_fix(tree, p); tree->size++; return 0; } void insert_fix(struct rbtree *tree, struct rbnode *node){ struct rbnode *x = node, *y, *tmp; while(x->parent){ y = x->parent;  if(x == y->left){ if(y->color == BLACK) return; rotate_right(tree, y->parent); color_flip_up(y); x = y; } else { if(y->left && y->left->color == RED){ color_flip_up(y); x = y; } else { rotate_left(tree, y); tmp = x, x = y, y = tmp; if(y->color == BLACK) return; rotate_right(tree, y->parent); color_flip_up(y); x = y; } } } if(tree->root->color == RED){ tree->root->color = BLACK; tree->depth++; }}

函数insert的逻辑很简单，就是创建新的节点，新节点的颜色设为红色，按照二叉搜索树的方式寻找要插入的位置，然后调用insert_fix,来保证整个树是一个符合定义的红黑树。insert_fix的实现主体是一个while循环，当x的parent存在时就一直循环，直到x是根节点为止，当然while内部有提前结束循环的地方。进入循环体内，首先我们要明白的就是，此时x的颜色是RED，这是因为第一次循环的时候x是RED的，后面循环再次进来的时候x也是RED的，如果不是的话就不会继续循环了。先分x是左子还是右子两种情况来讨论，当x是左子的时候，看parent是不是RED，如果是BLACK的话，直接return。如果是RED的话，此时x和y都是左斜的，y是左斜的是因为我们实现的是左斜红黑树，原有的红色节点只可能是左斜的。对于双红色左斜节点的处理，我把图片又放到下面了，大家可以再看一看。这种情况我们应当对y的parent进行右旋，右旋之后，y成了两个红色节点的父节点，由于旋转之前y是红色，所以y的parent不可能是红色，只能是黑色，所以旋转之后交换了颜色，所以此时y肯定是黑色。y是黑色，左子右子都是红色，正好可以翻色，翻色之后，左子右子都变成了黑色，y变成了红色，让x=y进行下一轮循环。当x是右子的时候，先看一下左兄弟是不是红色，如果是的话，父节点y肯定是黑色，正好可以翻色，对y进行翻色，让x=y，继续下一轮循环。如果x的左兄弟不是红色的，先左旋y，左旋之后x y的父子关系变了，交换一下它们的值，让x仍然是子，y仍然是父。判断y的颜色，如果是黑色直接return函数结束，如果是红色，x y又形成了双左斜红色的情况，和上面的处理方式是一样的，右旋y的parent，翻色y，让x=y，继续下一轮循环。函数最后判断根节点是否为红色，如果为红色的话，说明之前的根节点经历过分割，树的高度增加1，再把根节点重置为黑色。

4.4 删除操作的代码

删除操作主要有两个函数，delete 和 delete_fix，delete比insert稍微复杂一点，要处理被删除的点不是叶子节点的情况。对于非叶子节点的情况，其右子树一定存在，用右子树的最小值，也就是右子树的最左子节点的值覆盖自己，然后删除右子树的最左子节点就可以了。

rbtree.c

int delete(struct rbtree *tree, int value){ if(!tree->root) return -1;  struct rbnode *i = tree->root, *j; while(i){ if(value < i->value){ i = i->left; } else if(value > i->value){ i = i->right; } else { if(!i->left || !i->right){ delete_fix(tree, i); tree->size--; return 0; } j = i->right; while(j->left) j = j->left; i->value = j->value; delete_fix(tree, j); tree->size--; return 0; } } return -1;} void delete_fix(struct rbtree *tree, struct rbnode *node){ if(node->left && node->left->color == RED) rotate_right(tree, node); if(node->color == RED) goto delete;  struct rbnode *self = node, *parent, *brother, *nephew; int red_borrowed = 0; while(self->parent){ parent = self->parent; if(self == parent->left){ // left child brother = parent->right; nephew = brother->left; if(nephew && nephew->color == RED){ nephew->color = BLACK; rotate_right(tree, brother); rotate_left(tree, parent); self->color = RED; if(red_borrowed){ red_borrowed = 0; self->color = BLACK; } break; } else { int old_red_borrowed = red_borrowed; red_borrowed = 0; if(parent->color == BLACK) red_borrowed = 1; color_flip_down(parent); if(old_red_borrowed) self->color = BLACK; rotate_left(tree, parent); if(red_borrowed){ self = brother; continue; } else { break; } } // left child end } else { // right child  brother = parent->left; nephew = brother->left; if(brother && brother->color == RED){ if(brother->right && brother->right->left && brother->right->left->color == RED){ struct rbnode *n = brother->right->left; rotate_right(tree, parent); rotate_right(tree, parent); n->color = BLACK; self->color = RED; if(red_borrowed){ red_borrowed = 0; self->color = BLACK; } rotate_left(tree, brother); break; } else { rotate_right(tree, parent); color_flip_down(parent); if(red_borrowed){ red_borrowed = 0; self->color = BLACK; } break; } } else if(nephew && nephew->color == RED){ rotate_right(tree, parent); nephew->color = BLACK; self->color = RED; if(red_borrowed){ red_borrowed = 0; self->color = BLACK; } break; } else { int old_red_borrowed = red_borrowed; red_borrowed = 0; if(parent->color == BLACK) red_borrowed = 1; color_flip_down(parent); if(old_red_borrowed) self->color = BLACK; if(red_borrowed){ self = parent; continue; } else { break; } } // right child end } }  if(red_borrowed) tree->depth--;  struct rbnode *child; delete: child = node->left ? node->left : node->right; if(node->parent){ int flag = node == node->parent->left; flag ? (node->parent->left = child) : (node->parent->right = child); } else { tree->root = child; if(!tree->root) tree->depth--; } if(child) child->parent = node->parent; free(node);}

函数delete_fix首先考虑两种特殊情况，如果node是红色的，或者node的左子是红色的，直接右旋自己，把自己变成红色，然后直接goto delete。剩下的情况就是node不是红色的，也是说node是单元素节点，要想办法把自己变成红色的，也就是通过借元素变成双元素节点。进入循环的条件是当前元素的parent不为空，循环内部有一个变量red_borrowed控制着是否继续循环，如果为1则循环，如果为0则结束循环，也就是说循环至少会执行一次，然后x->parent和red_borrowed共同决定是否继续循环。循环体内分为两种情况，自己是左子和自己是右子的情况，自己是左子的情况又分两种，自己是右子的情况又分四种。下面通过画图给大家解析一下。字母与代码中对应的节点如下：
x:self
y:parent
z:brother
w:nephew(侄子)
注意在每次循环开始的时候x都是黑色的。由于我们是左斜红黑树，所以z不可能是红色的，可能的情况只有w是红色的或者是黑色的(下一种情况)，对于这种情况，我们通过其对应的2-3 B树可以看出来我们应该如何把红黑树调整成目标的样子。我们先把w的颜色置黑，因为它最终的颜色是黑色的，提前置黑能避免旋转时的颜色交换。然后通过右旋z、左旋y把红黑树调整成目标形态，然后把x的颜色置红，然后再根据red_borrowed把x置黑。此种情况我们帮x借到了红色，对应着2-3 B树中借到了元素，所以循环结束。

这种情况是兄弟节点没法借的情况，只有向父节点借，向父节点借有两种情况，一是父节点是红色，能借到，循环就结束了，二是父节点是黑色，借不到，只能强行借了，把red_borrowed设置为1。我们还要考虑上一轮的red_borrowed，如果为1，要把借来的红色还了，也就是说x刚借来红色就还了，x还是黑色的。如果red_borrowed为0的话说明是第一次循环，x是要被删除的元素，所以不存在违背红子不红的问题。如果这一轮的red_borrowed是1的话则继续循环，否则就结束循环。

这是一种比较复杂的情况，对应着2-3 B树的情况是父节点和兄弟节点都有两个元素的情况。看红黑树比较复杂，我们看2-3 B树是怎么操作的，通过B树的操作反推红黑树应该如何操作。第一步我们右旋y，得到了一个x y o n ，一个局部有红色节点的树。第二步，只考虑这个树，我们最后可以通过右旋y并调整颜色的方式把红色转移给x，这样我们就达到目的了。然后我们发现o的颜色是右斜的，对z左旋一下，把它调整为一个左斜红黑树。

这种情况对应的2-3 B树是父节点有两个元素，向父节点借一个元素并和兄弟节点合并，所以我们先右旋y，然后对y进行翻色，x就变为红色了。通过前面的分析我们知道，虽然x是红色右斜的，但是有两种情况，要么x是被借红的，所以还会变成黑色，要么x就是要被删除的节点，所以不需要把x旋转为左斜的。

这种情况是父节点只有一个元素兄弟节点有两个元素，直接向兄弟借元素，一个右旋y并调整颜色，就搞定了。

这种情况和左2是相同的，而且还比左2简单，由于z是左斜的，所以旋转的动作都省了。

五、总结回顾