红黑树的使用场景非常广泛，比如nginx中用来管理timer、epoll中用红黑树管理事件块（文件描述符）、Linux进程调度Completely Fair Scheduler用红黑树管理进程控制块、C++STL中map,set的底层实现全是用的红黑树。掌握红黑树的原理以及使用场景，对于我们面试和工作、以及理解开源代码都是非常有帮助。
二叉树介绍
在关注红黑树之前，首先复习一下二叉树的概念。在数据结构中，二叉树有如下定义：
二叉树是一种由节点和层组成的结构
每一层有若干个节点
第一层只能有一个根节点
每个节点可以拥有两颗支树，分别被称为左子树(left subtree)和右子树(right subtree)
对于一个节点，左子树所有的元素都比这个节点存储的元素小，右子树所有的节点都比这个节点存储的元素大
它的结构类似如下的截图：
那么二叉树被定义为以上的规则，到底有什么用呢？跟传统的链表存储相比，到底有什么优势呢？对于上述的二叉树，如果使用链表存储则表示如下：
当我们从这个链表中的头部107开始查找元素的时候，对于它的7个成员查找需要的次数如下：
通过如上表格我们发现，链表中元素的比较次数跟元素在链表中存储的位置正相关，所有元素的最终的平均比较次数等于(1 + 2 + 3 + 4 + 5 + 6 + 7) / 7 = 4
对于二叉树来说，由于二叉树被定义为左子树所有的元素都比这个节点存储的元素小，右子树所有的节点都比这个节点存储的元素大，对于完全二叉树来说，每次比较我们都可以排除掉一半的元素。
比如对于上述二叉树中的元素45来说，第一次跟60比较，小于60，直接排除掉右子树所有的元素(100,67,107)，第二次跟55比较，小于55，排除掉55右子树所有的元素(57)，最后定位到45，这里只比较了3次。在二叉树中七个成员查找需要的次数如下：
所有元素的最终的平均比较次数等于(1 + 2 + 2 + 3 + 3 + 3 + 3) / 7 ≈ 2.4，很直观的发现，二叉树的平均比较次数比链表少。即链表的平均复杂度为O(n)，而二叉树的平均复杂度为O(logn)。可以说，二叉树是一种比链表更高效查找的数据结构。
二叉树的弊端
上面已经说过，二叉树是比链表查找更高效的数据结构，但是二叉树的时间复杂度一定比链表低吗？还是争对上述的二叉树中的元素举例，即按45->55->57->60->67->100->107的顺序，把元素插入二叉树当中，插入过程如下图所示：
我们发现，当按顺序插入的时候，二叉树变成了一个”瘸子“，这样的只有个一个支数的二叉树，实际上就是一个链表。也就是说，二叉树最坏的情况下，查找的时间复杂度等于链表O(n)，这完全失去了二叉树的意义。那么如何避免这种情况，让二叉树能尽可能的“平衡”一点呢？
红黑树的定义
为了让插入的时候，二叉树尽可能的平衡，1972年鲁道夫·贝尔提出红黑树的概念，对于红黑树的定义如下：
- 节点是红色或黑色
- 根是黑色
- 所有叶子都是黑色（叶子是NIL节点）
- 每个红色节点必须有两个黑色的子节点（从每个叶子到根的所有路径上不能有两个连续的红色节点）
- 从任一节点到其每个叶子(NIL)的所有简单路径都包含相同数目的黑色节点
遵循如上规则的二叉树被称为红黑树，但是为什么要定义成如上规则呢？事实上，如上所有的规则都只想做一件事，让二叉树尽可能的平衡。
对于定义4，即代表了红黑树中不可能出现两个连续的红色节点，也就是说支树上最多是红黑交替的情况(可以出现连续的黑节点)。
对于定义5，结合定义4，即代表红黑树中最长路径最多是最短路径的两倍。
争对上述的1，2举例：
上图是一个符合红黑树定义的二叉树，叶子(NIL)节点就是一个空节点，表示节点在此位置上没有元素了。在实际的算法实现中NIL不需要考虑，填上NIL节点只是为了判断到此路径终点的NIL节点上，经过多少黑节点。
此红黑树中，根节点到NIL节点，最短路径为55到45（2个黑色节点），最长路径为55到107（2个黑色节点，2个红色节点），最长路径是最短路径的节点数的两倍。如果在往107后面添加一个黑色节点，则不符合定义5，因为多了一个黑色节点。所以红黑树保证了最坏情况和最好情况不会差太多，做到一个相对来说的平衡。
左旋和右旋
对于一个节点N来说，它有一个左节点L，右节点R，如下图所示：
根据二叉树定义，N > L，N < R，且N为L和R的父节点。那么如果L当儿子当够了，现在L想当N的爸爸（父节点），二叉树该怎么调整？
因为L < N，根据二叉树定义，把N放入L的右节点处
N的左节点指向节点2
上述的过程称为对节点N的右旋，对应的动态图为：
同理，如果R想做N的父节点呢？
因为R > N，根据二叉树定义，把N放入R的左节点处
N的右节点节点指向节点3
上述的过程称为对节点N的左旋，对应的动态图为：
其实所谓的左旋右旋，可以理解为节点的子节点想”篡位“，原来的子节点变为现在节点的父节点。
红黑树的插入
复习一下二叉树的插入规则：
定位到需要插入的位置
插入元素
二叉树的插入如下图所示：
而红黑树比二叉树多了一个规则，插入后重新平衡二叉树，让它符合红黑树的定义。规定新插入的节点一定是红色的，因为如果插入的是黑色的，原来经过插入之前的节点的元素就会多一个黑色节点，调整起来比较麻烦。
下面介绍插入完成之后如何平衡二叉树：
假设刚插入的节点为X，它的父节点为N，祖父节点为P，N的兄弟节点为U，下图列举了一种可能的情况：
说明：红底的代表红节点，黑底的代表黑节点，白底的代表颜色未知的节点（即可黑可红）。
现在需要以X节点的父节点N的颜色作为一个切入点开始讨论：
N为黑***r>这种情况是最简单的，不需要做任何调整，因为新插入的节点X为红色，并不会影响经过X的支路的黑节点数量，之前是多少，现在就是多少。
N为红色此时出现了X和N为两个连续的红节点，需要调整树，让它符合红黑树的特征。对于X,N,P节点的关系，现在这里有四种情况：
第一种：N为P的左节点，X为N的左节点
第二种：N为P的左节点，X为N的右节点
第三种：N为P的右节点，X为N的右节点
第四种：N为P的右节点，X为N的左节点
观察后不难发现，其实前面两种和后面两种是成镜像的，也就是说分析前两种，后面两种的操作可以效仿前两种。现在我们可以对节点做一下左旋，右旋，节点颜色修改等操作，让树重新符合红黑树特征（由于N为红色，根据红黑树的特征4，P节点一定为黑。）。
N为P的左节点，X为N的左节点
这种情况我们就需要分析U节点的颜***r>① U节点为红***r>直接把N和U全部设置为黑色，把P设置为红色即可
设到达P节点之前，有a个黑色节点。在改变之前，在到达X,1,2,3这四个节点的时候，经过黑色节点的数量如下：
X节点：a + 1
1节点：a + 2
2节点：a + 2
3节点：a + 2
改变之后
X节点：a + 1
1节点：a + 2
2节点：a + 2
3节点：a + 2
可以发现改变之后还是符合红黑树的特征5。上述给了一种分析经过路径的黑节点的数量的一种手段。
② U节点为黑***r>首先对P节点进行右旋，然后交换N和P节点的颜***r>
设到达P节点之前，有a个黑色节点。在改变之前，在到达X,1,2,3这四个节点的时候，经过黑色节点的数量如下 (因为2，3节点的颜色未知，所以用d2,d3代表。比如说如果2为黑，d2则为1，否则为0)：
X节点：a + 1
1节点：a + 2
2节点：a + 2 + d2
3节点：a + 2 + d3
改变之后
X节点：a + 1
1节点：a + 2
2节点：a + 2 + d2
3节点：a + 2 + d3
可以发现改变之后还是符合红黑树的特征5。
N为P的左节点，X为N的右节点
首先左旋N节点
设到达P节点之前，有a个黑色节点。在改变之前，在到达1,2,3,4,5这五个节点的时候，经过黑色节点的数量如下 (因为2，3节点的颜色未知，所以用d2,d3代表。比如说如果2为黑，d2则为1，否则为0)：
1节点：a + 2
2节点：a + 2 + d2
3节点：a + 2 + d3
4节点：a + 2
5节点：a + 2
改变之后
1节点：a + 2
2节点：a + 2 + d2
3节点：a + 2 + d3
4节点：a + 2
5节点：a + 2
可以看出，并没有改变支路上黑节点的数量。但是N,X还是两个连续的红节点，还要继续操作。观察到上图被红色方框圈出来的东西发现，它就是之前N为P的左节点，X为N的左节点的那种情况，所以可以转到对应的步骤处理。
N为P的右节点，X为N的右节点
对应N为P的左节点，X为N的左节点，把右旋换成左旋，其他步骤一样。
N为P的右节点，X为N的左节点
对应N为P的左节点，X为N的右节点，把右旋换成左旋，其他步骤一样。
红黑树的删除
跟插入一样，红黑树的删除就比二叉树多了一个步骤：删除完成之后重新调整树，让它再次符合二叉树的定义。那么二叉树是如何进行删除的呢？下面是出二叉树的删除步骤：
定位到二叉树需要删除的节点
如果节点没有支树了，直接删除节点
如果节点只有一个子支树，直接把这个子支树跟需要删除的节点的父节点相连
如果节点有两个支树，找到节点的左支树的最大值，或者右支树的最小值，然后把这个值（这里我们使用左支树的最大值）赋值给需要删除的节点（注意：当前需要被删除的节点不会被删掉了，只是被赋予了新值）。然后我们再删除掉拥有左支树的最大值的这个节点，因为这个节点是左边最大的了，那么它的右分支肯定为空，也就是说最多只可能有一个支树。这时候我们可以转换为情况2,3处理了。
需要理解的是，我们常说的删除一颗树中的一个节点，表示只要这颗树中不存在这个节点所存储的值，就表明删除了，并不一定要真正的抹掉这个节点！
下面争对上面的第四种举一个例子：
经过上面的介绍，相信大家对二叉树的删除都有一点了解。红黑树的删除也会经过上面的步骤，不同的是，删除之后会调整红黑树，让它重新符合红黑树的特征，下面分析删除完成之后的情况。
这里假设一个节点P，删除了它的一个子节点X，删除完成之后，N节点顶替掉了X节点，成为P的子节点。X节点的兄弟节点为S，S的左右节点为SL，SR。
对于上述举出的删除的例子来说，这个P节点就是10，X节点就是11，N节点是NULL，S节点为13，SL为NULL，SR为NULL。注意，虽然上述删除的是12，但是我们讨论的X确并不是12。这是因为我们把删除节点12这个问题转换为了删除节点11。最终树中确实少了12，但是它的值只是被新值覆盖，节点被没有删除。而我们讨论的是被抹掉的节点。
所以有了上面的前提，我们分析问题的切入点就只有两个，被删除的节点有0个支树，被删除的的节点有1个支树。为什么没有被删除的节点有两个支树的情况呢？因为如果有两个，通过上面介绍的二叉树的删除步骤4，我们可以把删除具有两个子树的节点的情况转变为删除具有一个子树或者具有0颗子树的情况。
比如对于上面的例子，我们把删除12(这个节点有两个子树)，转变为删除11(具有0颗子树)的情况。下面从被删除节点的支树数量的个数开始分析：
被删除的X节点没有分支
这种情况直接删除节点就完事了，不需要做任何调整。我们常说调整红黑树，是因为不符合红黑树的特征4和特征5。而删除一个没有分支的节点，用屁股随便想一下就知道不会影响这两条。
被删除的X节点有一个分支这个时候的切入点就是被删除节点的颜***r>被删除的X节点为红***r>这种也是我们最喜欢的情况，不需要调整啊。因为根据红黑树的特征4，此时X的父节点P必为黑色，所以N节点为红还是黑都不会影响特征4。而X节点又为红，也就是说，经过原来X的那条支路只是少了一个红节点，也不会影响特征5。
被删除的节点是黑***r>这又要分为很多种情况了，这里你可以一条一条分析N，U和P节点的颜色。我们分析的切入点是，顶替X节点的N节点的颜色。
说明：红底的代表红节点，黑底的代表黑节点，白底的代表颜色未知的节点（即可黑可红）。
(1) N节点为红
这种情况也很简单，直接把N染成黑***r>
经过上面的操作，不仅N不会和P产生两个连续红节点的情况，而且经过N节点的路径多了一个黑节点，正好替代被删除的黑节点X。
(2) N节点为黑
然后从S节点的颜色开始分析
①S节点为红***r>因为S为红色，根据红黑树的定义，P，SL，SR肯定都是黑色，如下图：
这里我们把P节点进行左旋，然后交换S和P节点的颜***r>
上面的S节点为P节点的右节点，所以左旋P节点。如果S节点为P节点的左节点，则是右旋P节点。
分析N，SL，SR节点在操作前和操作后的路径经过的黑色节点数量，发现都没有改变。但是我们把N节点的兄弟节点为红色的转换为黑色的情况。为黑色的处理情况如下处理。
②S节点为黑色，SR节点为红的情况。如下图所示：
由于原来P的左边有一个黑节点X，现在被删除了，所以左边路径上少了一个黑节点。
这种情况，直接左旋P节点，然后交换P,S的颜色，并且把SR换成黑色。
上面的S节点为P节点的右节点，所以取了SR来举例子。如果S为P节点的左节点，那么就应该去SL。然后把左旋改成右旋。
通过如上操作，不难发现，经过N节点的路径的黑色节点数量多了一个，而经过SL,SR节点的路径的黑色节点并没有变少，符合红黑树定义4，5。
③ S节点为黑色，SR节点为黑
这种情况下只剩下P节点和SL节点的颜色没有确定，这两个节点的组合，总共可能有四种情况：
P为黑，SL为黑***r>P为白，SL为黑
P为黑，SL为白
P为白，SL为白
对于第一种和第二种情况，都是转换成如下的情况：
第一种是直接把S变成红色。然后P的左右支树的节点数量一样（P的左子树少了个黑色节点X）。
但是对于经过P节点的支路上来说，全部都少了一个黑节点（比如经过SL和SR节点的支路）。
所以可以把P节点看成N节点，进行递归，分析P节点的父节点，兄弟节点。如果中途一直没有解决，则会递归到根节点。如果根节点此时为红色，则变回黑色。、
第二种直接把P和S节点的颜色对调，就不需要再调整了。因为对于经过N节点的支路多了一个黑节点，对于SL，SR来说没有变，正好符合情况。
第三种和第四种其实都是对S节点进行右旋，然后交换SL和S的颜色最后转化成S节点为黑色，SR节点为红的情况。
这里准备了2020一线大厂的一套面试题合集
需要的小伙伴记得扫码获取 备注暗号“668”
红黑树的代码实现
引用linux红黑树的经典实现
红黑树的实现文件(rbtree.h)
/*
Red Black Trees
(C) 1999 Andrea Arcangeli <andrea@suse.de>
This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2 of the License, or
(at your option) any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
linux/include/linux/rbtree.h
To use rbtrees you'll have to implement your own insert and search cores.
This will avoid us to use callbacks and to drop drammatically performances.
I know it's not the cleaner way, but in C (not in C++) to get
performances and genericity...
Some example of insert and search follows here. The search is a plain
normal search over an ordered tree. The insert instead must be implemented
in two steps: First, the code must insert the element in order as a red leaf
in the tree, and then the support library function rb_insert_color() must
be called. Such function will do the not trivial work to rebalance the
rbtree, if necessary.
-----------------------------------------------------------------------
static inline struct page * rb_search_page_cache(struct inode * inode,
unsigned long offset)
{
struct rb_node * n = inode->i_rb_page_cache.rb_node;
struct page * page;
while (n)
{
page = rb_entry(n, struct page, rb_page_cache);
if (offset < page->offset)
n = n->rb_left;
else if (offset > page->offset)
n = n->rb_right;
else
return page;
}
return NULL;
}
static inline struct page * __rb_insert_page_cache(struct inode * inode,
unsigned long offset,
struct rb_node * node)
{
struct rb_node ** p = &inode->i_rb_page_cache.rb_node;
struct rb_node * parent = NULL;
struct page * page;
while (*p)
{
parent = *p;
page = rb_entry(parent, struct page, rb_page_cache);
if (offset < page->offset)
p = &(*p)->rb_left;
else if (offset > page->offset)
p = &(*p)->rb_right;
else
return page;
}
rb_link_node(node, parent, p);
return NULL;
}
static inline struct page * rb_insert_page_cache(struct inode * inode,
unsigned long offset,
struct rb_node * node)
{
struct page * ret;
if ((ret = __rb_insert_page_cache(inode, offset, node)))
goto out;
rb_insert_color(node, &inode->i_rb_page_cache);
out:
return ret;
}
-----------------------------------------------------------------------
*/
#ifndef _SLINUX_RBTREE_H
#define _SLINUX_RBTREE_H
#include <stdio.h>
//#include <linux/kernel.h>
//#include <linux/stddef.h>
struct rb_node
{
unsigned long rb_parent_color;
#define RB_RED 0
#define RB_BLACK 1
struct rb_node *rb_right;
struct rb_node *rb_left;
} /* __attribute__((aligned(sizeof(long))))*/;
/* The alignment might seem pointless, but allegedly CRIS needs it */
struct rb_root
{
struct rb_node *rb_node;
};
#define rb_parent(r) ((struct rb_node *)((r)->rb_parent_color & ~3))
#define rb_color(r) ((r)->rb_parent_color & 1)
#define rb_is_red(r) (!rb_color(r))
#define rb_is_black(r) rb_color(r)
#define rb_set_red(r) do { (r)->rb_parent_color &= ~1; } while (0)
#define rb_set_black(r) do { (r)->rb_parent_color |= 1; } while (0)
static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p)
{
rb->rb_parent_color = (rb->rb_parent_color & 3) | (unsigned long)p;
}
static inline void rb_set_color(struct rb_node *rb, int color)
{
rb->rb_parent_color = (rb->rb_parent_color & ~1) | color;
}
#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
#define container_of(ptr, type, member) ({ \
const typeof( ((type *)0)->member ) *__mptr = (ptr); \
(type *)( (char *)__mptr - offsetof(type,member) );})
#define RB_ROOT (struct rb_root) { NULL, }
#define rb_entry(ptr, type, member) container_of(ptr, type, member)
#define RB_EMPTY_ROOT(root) ((root)->rb_node == NULL)
#define RB_EMPTY_NODE(node) (rb_parent(node) == node)
#define RB_CLEAR_NODE(node) (rb_set_parent(node, node))
static inline void rb_init_node(struct rb_node *rb)
{
rb->rb_parent_color = 0;
rb->rb_right = NULL;
rb->rb_left = NULL;
RB_CLEAR_NODE(rb);
}
extern void rb_insert_color(struct rb_node *, struct rb_root *);
extern void rb_erase(struct rb_node *, struct rb_root *);
typedef void (*rb_augment_f)(struct rb_node *node, void *data);
extern void rb_augment_insert(struct rb_node *node,
rb_augment_f func, void *data);
extern struct rb_node *rb_augment_erase_begin(struct rb_node *node);
extern void rb_augment_erase_end(struct rb_node *node,
rb_augment_f func, void *data);
/* Find logical next and previous nodes in a tree */
extern struct rb_node *rb_next(const struct rb_node *);
extern struct rb_node *rb_prev(const struct rb_node *);
extern struct rb_node *rb_first(const struct rb_root *);
extern struct rb_node *rb_last(const struct rb_root *);
/* Fast replacement of a single node without remove/rebalance/add/rebalance */
extern void rb_replace_node(struct rb_node *victim, struct rb_node *new,
struct rb_root *root);
static inline void rb_link_node(struct rb_node * node, struct rb_node * parent,
struct rb_node ** rb_link)
{
node->rb_parent_color = (unsigned long )parent;
node->rb_left = node->rb_right = NULL;
*rb_link = node;
}
#endif /* _LINUX_RBTREE_H */红黑树的实现文件(rbtree.c)
/*
Red Black Trees
(C) 1999 Andrea Arcangeli <andrea@suse.de>
(C) 2002 David Woodhouse <dwmw2@infradead.org>
This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2 of the License, or
(at your option) any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
linux/lib/rbtree.c
*/
#include "rbtree.h"
static void __rb_rotate_left(struct rb_node *node, struct rb_root *root)
{
struct rb_node *right = node->rb_right;
struct rb_node *parent = rb_parent(node);
if ((node->rb_right = right->rb_left))
rb_set_parent(right->rb_left, node);
right->rb_left = node;
rb_set_parent(right, parent);
if (parent)
{
if (node == parent->rb_left)
parent->rb_left = right;
else
parent->rb_right = right;
}
else
root->rb_node = right;
rb_set_parent(node, right);
}
static void __rb_rotate_right(struct rb_node *node, struct rb_root *root)
{
struct rb_node *left = node->rb_left;
struct rb_node *parent = rb_parent(node);
if ((node->rb_left = left->rb_right))
rb_set_parent(left->rb_right, node);
left->rb_right = node;
rb_set_parent(left, parent);
if (parent)
{
if (node == parent->rb_right)
parent->rb_right = left;
else
parent->rb_left = left;
}
else
root->rb_node = left;
rb_set_parent(node, left);
}
void rb_insert_color(struct rb_node *node, struct rb_root *root)
{
struct rb_node *parent, *gparent;
while ((parent = rb_parent(node)) && rb_is_red(parent))
{
gparent = rb_parent(parent);
if (parent == gparent->rb_left)
{
{
register struct rb_node *uncle = gparent->rb_right;
if (uncle && rb_is_red(uncle))
{
rb_set_black(uncle);
rb_set_black(parent);
rb_set_red(gparent);
node = gparent;
continue;
}
}
if (parent->rb_right == node)
{
register struct rb_node *tmp;
__rb_rotate_left(parent, root);
tmp = parent;
parent = node;
node = tmp;
}
rb_set_black(parent);
rb_set_red(gparent);
__rb_rotate_right(gparent, root);
} else {
{
register struct rb_node *uncle = gparent->rb_left;
if (uncle && rb_is_red(uncle))
{
rb_set_black(uncle);
rb_set_black(parent);
rb_set_red(gparent);
node = gparent;
continue;
}
}
if (parent->rb_left == node)
{
register struct rb_node *tmp;
__rb_rotate_right(parent, root);
tmp = parent;
parent = node;
node = tmp;
}
rb_set_black(parent);
rb_set_red(gparent);
__rb_rotate_left(gparent, root);
}
}
rb_set_black(root->rb_node);
}
static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
struct rb_root *root)
{
struct rb_node *other;
while ((!node || rb_is_black(node)) && node != root->rb_node)
{
if (parent->rb_left == node)
{
other = parent->rb_right;
if (rb_is_red(other))
{
rb_set_black(other);
rb_set_red(parent);
__rb_rotate_left(parent, root);
other = parent->rb_right;
}
if ((!other->rb_left || rb_is_black(other->rb_left)) &&
(!other->rb_right || rb_is_black(other->rb_right)))
{
rb_set_red(other);
node = parent;
parent = rb_parent(node);
}
else
{
if (!other->rb_right || rb_is_black(other->rb_right))
{
rb_set_black(other->rb_left);
rb_set_red(other);
__rb_rotate_right(other, root);
other = parent->rb_right;
}
rb_set_color(other, rb_color(parent));
rb_set_black(parent);
rb_set_black(other->rb_right);
__rb_rotate_left(parent, root);
node = root->rb_node;
break;
}
}
else
{
other = parent->rb_left;
if (rb_is_red(other))
{
rb_set_black(other);
rb_set_red(parent);
__rb_rotate_right(parent, root);
other = parent->rb_left;
}
if ((!other->rb_left || rb_is_black(other->rb_left)) &&
(!other->rb_right || rb_is_black(other->rb_right)))
{
rb_set_red(other);
node = parent;
parent = rb_parent(node);
}
else
{
if (!other->rb_left || rb_is_black(other->rb_left))
{
rb_set_black(other->rb_right);
rb_set_red(other);
__rb_rotate_left(other, root);
other = parent->rb_left;
}
rb_set_color(other, rb_color(parent));
rb_set_black(parent);
rb_set_black(other->rb_left);
__rb_rotate_right(parent, root);
node = root->rb_node;
break;
}
}
}
if (node)
rb_set_black(node);
}
void rb_erase(struct rb_node *node, struct rb_root *root)
{
struct rb_node *child, *parent;
int color;
if (!node->rb_left)
child = node->rb_right;
else if (!node->rb_right)
child = node->rb_left;
else
{
struct rb_node *old = node, *left;
node = node->rb_right;
while ((left = node->rb_left) != NULL)
node = left;
if (rb_parent(old)) {
if (rb_parent(old)->rb_left == old)
rb_parent(old)->rb_left = node;
else
rb_parent(old)->rb_right = node;
} else
root->rb_node = node;
child = node->rb_right;
parent = rb_parent(node);
color = rb_color(node);
if (parent == old) {
parent = node;
} else {
if (child)
rb_set_parent(child, parent);
parent->rb_left = child;
node->rb_right = old->rb_right;
rb_set_parent(old->rb_right, node);
}
node->rb_parent_color = old->rb_parent_color;
node->rb_left = old->rb_left;
rb_set_parent(old->rb_left, node);
goto color;
}
parent = rb_parent(node);
color = rb_color(node);
if (child)
rb_set_parent(child, parent);
if (parent)
{
if (parent->rb_left == node)
parent->rb_left = child;
else
parent->rb_right = child;
}
else
root->rb_node = child;
color:
if (color == RB_BLACK)
__rb_erase_color(child, parent, root);
}
static void rb_augment_path(struct rb_node *node, rb_augment_f func, void *data)
{
struct rb_node *parent;
up:
func(node, data);
parent = rb_parent(node);
if (!parent)
return;
if (node == parent->rb_left && parent->rb_right)
func(parent->rb_right, data);
else if (parent->rb_left)
func(parent->rb_left, data);
node = parent;
goto up;
}
/*
* after inserting @node into the tree, update the tree to account for
* both the new entry and any damage done by rebalance
*/
void rb_augment_insert(struct rb_node *node, rb_augment_f func, void *data)
{
if (node->rb_left)
node = node->rb_left;
else if (node->rb_right)
node = node->rb_right;
rb_augment_path(node, func, data);
}
/*
* before removing the node, find the deepest node on the rebalance path
* that will still be there after @node gets removed
*/
struct rb_node *rb_augment_erase_begin(struct rb_node *node)
{
struct rb_node *deepest;
if (!node->rb_right && !node->rb_left)
deepest = rb_parent(node);
else if (!node->rb_right)
deepest = node->rb_left;
else if (!node->rb_left)
deepest = node->rb_right;
else {
deepest = rb_next(node);
if (deepest->rb_right)
deepest = deepest->rb_right;
else if (rb_parent(deepest) != node)
deepest = rb_parent(deepest);
}
return deepest;
}
/*
* after removal, update the tree to account for the removed entry
* and any rebalance damage.
*/
void rb_augment_erase_end(struct rb_node *node, rb_augment_f func, void *data)
{
if (node)
rb_augment_path(node, func, data);
}
/*
* This function returns the first node (in sort order) of the tree.
*/
struct rb_node *rb_first(const struct rb_root *root)
{
struct rb_node *n;
n = root->rb_node;
if (!n)
return NULL;
while (n->rb_left)
n = n->rb_left;
return n;
}
struct rb_node *rb_last(const struct rb_root *root)
{
struct rb_node *n;
n = root->rb_node;
if (!n)
return NULL;
while (n->rb_right)
n = n->rb_right;
return n;
}
struct rb_node *rb_next(const struct rb_node *node)
{
struct rb_node *parent;
if (rb_parent(node) == node)
return NULL;
/* If we have a right-hand child, go down and then left as far
as we can. */
if (node->rb_right) {
node = node->rb_right;
while (node->rb_left)
node=node->rb_left;
return (struct rb_node *)node;
}
/* No right-hand children. Everything down and left is
smaller than us, so any 'next' node must be in the general
direction of our parent. Go up the tree; any time the
ancestor is a right-hand child of its parent, keep going
up. First time it's a left-hand child of its parent, said
parent is our 'next' node. */
while ((parent = rb_parent(node)) && node == parent->rb_right)
node = parent;
return parent;
}
struct rb_node *rb_prev(const struct rb_node *node)
{
struct rb_node *parent;
if (rb_parent(node) == node)
return NULL;
/* If we have a left-hand child, go down and then right as far
as we can. */
if (node->rb_left) {
node = node->rb_left;
while (node->rb_right)
node=node->rb_right;
return (struct rb_node *)node;
}
/* No left-hand children. Go up till we find an ancestor which
is a right-hand child of its parent */
while ((parent = rb_parent(node)) && node == parent->rb_left)
node = parent;
return parent;
}
void rb_replace_node(struct rb_node *victim, struct rb_node *new,
struct rb_root *root)
{
struct rb_node *parent = rb_parent(victim);
/* Set the surrounding nodes to point to the replacement */
if (parent) {
if (victim == parent->rb_left)
parent->rb_left = new;
else
parent->rb_right = new;
} else {
root->rb_node = new;
}
if (victim->rb_left)
rb_set_parent(victim->rb_left, new);
if (victim->rb_right)
rb_set_parent(victim->rb_right, new);
/* Copy the pointers/colour from the victim to the replacement */
*new = *victim;
}红黑树的测试文件(test.c)
/**
* 根据Linux Kernel定义的红黑树(Red Black Tree)
*
*/
#include <stdio.h>
#include <stdlib.h>
#include "rbtree.h"
#define CHECK_INSERT 0 // "插入"动作的检测开关(0，关闭；1，打开)
#define CHECK_DELETE 0 // "删除"动作的检测开关(0，关闭；1，打开)
#define LENGTH(a) ( (sizeof(a)) / (sizeof(a[0])) )
typedef int Type;
struct my_node {
struct rb_node rb_node; // 红黑树节点
Type key; // 键值
// ... 用户自定义的数据
};
/*
* 查找"红黑树"中键值为key的节点。没找到的话，返回NULL。
*/
struct my_node *my_search(struct rb_root *root, Type key)
{
struct rb_node *rbnode = root->rb_node;
while (rbnode!=NULL)
{
struct my_node *mynode = container_of(rbnode, struct my_node, rb_node);
if (key < mynode->key)
rbnode = rbnode->rb_left;
else if (key > mynode->key)
rbnode = rbnode->rb_right;
else
return mynode;
}
return NULL;
}
/*
* 将key插入到红黑树中。插入成功，返回0；失败返回-1。
*/
int my_insert(struct rb_root *root, Type key)
{
struct my_node *mynode; // 新建结点
struct rb_node **tmp = &(root->rb_node), *parent = NULL;
/* Figure out where to put new node */
while (*tmp)
{
struct my_node *my = container_of(*tmp, struct my_node, rb_node);
parent = *tmp;
if (key < my->key)
tmp = &((*tmp)->rb_left);
else if (key > my->key)
tmp = &((*tmp)->rb_right);
else
return -1;
}
// 如果新建结点失败，则返回。
if ((mynode=malloc(sizeof(struct my_node))) == NULL)
return -1;
mynode->key = key;
/* Add new node and rebalance tree. */
rb_link_node(&mynode->rb_node, parent, tmp);
rb_insert_color(&mynode->rb_node, root);
return 0;
}
/*
* 删除键值为key的结点
*/
void my_delete(struct rb_root *root, Type key)
{
struct my_node *mynode;
// 在红黑树中查找key对应的节点mynode
if ((mynode = my_search(root, key)) == NULL)
return ;
// 从红黑树中删除节点mynode
rb_erase(&mynode->rb_node, root);
free(mynode);
}
/*
* 打印"红黑树"
*/
static void print_rbtree(struct rb_node *tree, Type key, int direction)
{
if(tree != NULL)
{
if(direction==0) // tree是根节点
printf("%2d(B) is root\n", key);
else // tree是分支节点
printf("%2d(%s) is %2d's %6s child\n", key, rb_is_black(tree)?"B":"R", key, direction==1?"right" : "left");
if (tree->rb_left)
print_rbtree(tree->rb_left, rb_entry(tree->rb_left, struct my_node, rb_node)->key, -1);
if (tree->rb_right)
print_rbtree(tree->rb_right,rb_entry(tree->rb_right, struct my_node, rb_node)->key, 1);
}
}
void my_print(struct rb_root *root)
{
if (root!=NULL && root->rb_node!=NULL)
print_rbtree(root->rb_node, rb_entry(root->rb_node, struct my_node, rb_node)->key, 0);
}
void main()
{
int a[] = {10, 40, 30, 60, 90, 70, 20, 50, 80};
int i, ilen=LENGTH(a);
struct rb_root mytree = RB_ROOT;
printf("== 原始数据: ");
for(i=0; i<ilen; i++)
printf("%d ", a[i]);
printf("\n");
for (i=0; i < ilen; i++)
{
my_insert(&mytree, a[i]);
#if CHECK_INSERT
printf("== 添加节点: %d\n", a[i]);
printf("== 树的详细信息: \n");
my_print(&mytree);
printf("\n");
#endif
}
#if CHECK_DELETE
for (i=0; i<ilen; i++) {
my_delete(&mytree, a[i]);
printf("== 删除节点: %d\n", a[i]);
printf("== 树的详细信息: \n");
my_print(&mytree);
printf("\n");
}
#endif
}
京公网安备 11010502036488号