和AVL树一样，红黑树也是自平衡二叉搜索树。红黑树同样解决了在特定情况下二叉搜索树会退化成链表的问题。但是红黑树又不像AVL树那样高度平衡，这就让红黑树在插入删除频繁的场合效率优于AVL树。但是在插入和删除操作较少，而查找频繁的场合AVL树则更胜一筹。实际上linux内核中实现了红黑树(linux/rbtree.h)。linux内核使用红黑树来管理和调度进程。 C++标准库的map也是用红黑树来实现的，而Nginx中也使用红黑树来实现了定时器。下面我们就来学习一下这个作为很多牛X软件的底层数据结构红黑树(red-black tree)。
首先红黑树是一颗BST(二分查找树)，但是红黑树每一个节点包含一个额外的域用来存储颜色属性(每一个节点要么为红色，要么为黑色)。一棵红黑树必须满足下面的性质：
如下图所示的例子就是一颗红黑树：
对于红黑树的每一个节点都至少包含下面列出的属性：
正是由于红黑树(red-black tree)的五条性质的约束，这使得红黑树从根节点出发到叶子节点的任何一条路径都不可能超过其他从根节点出发到叶子节点路径的两倍，这使得红黑树可以维持平衡。
和AVL数类似，红黑树在调整平衡时也需要旋转操作。
左旋操作步骤如下：
1). 初始状态：
2). 如果y有左子树，那么将x设为y的左子树β的父节点
3). 将x的右子树设为β
4). 如果x的父节点为NULL，那么将y设为根节点
5). 否则，如果x是其父节点p的左孩子，那么将p的左孩子设为y
6). 否则，将p的右孩子设为y
7). 将y的父节点设为p
7). 将x的父节点设为y
8). 将y的左子树设为x
右旋的操作步骤如下：
1). 初始状态
2). 如果x有右子树，将y设为x右子树β的父节点
3). 将y的左子树设为β
4). 如果y的父节点p是NULL，那么将x设为父节点
5). 否则，如果y是其父节点p的右孩子，那么将x设为p的右孩子
6). 否则，将x设为p的左孩子
7). 将x的父节点设为p
8). 将y的父节点设为x
9). 将x的右子树设为y
在左右旋转时，我们先进行左旋，然后再进行右旋，如下步骤：
1). 先左旋(如下图，对x-y进行左旋)
2). 再进行右旋(再对y-z进行右旋)
而我们在进行右左旋转时，是先进行右旋，然后再进行左旋，如下步骤：
1). 先右旋(如下图，对x-y进行右旋)
2). 再进行左旋(如下图，对z-y进行左旋)
对红黑树的插入操作，我们希望插入后对红黑树的5条性质违反越少越好，基于此，我将待插入的节点先标记为红色。然后按照BST的插入方法插入该节点。这里之所以将节点标为红色，是因为这样做可以保证两点，该节点插入后，如果插入位置是根节点，那么违反性质#3,但是这种情况非常容易处理，直接将颜色设为黑色即可。如果插入位置不是根节点，那么它只违反性质#4。只要针对性质#4进行调整即可, 反之标为黑色就会违背#5，对性质#5的调整要比性质#4困难得多。
插入完成后，我进行调整使其满足红黑树的性质。具体的调整主要是做下面两件事:
1). 对节点进行颜色调整
2). 旋转操作
下面是插入操作的具体步骤：
1). 将待插入节点标为红色
2). 首先安装BST插入方法将待插入节点插入, 不清楚BST插入方法的同学可以参考我之前的文章<<数据结构-二叉搜索树>>。
3). 对插入后的树进行调整(insert fix up)使其仍然保持红黑树的性质。
我们这里重点来看看insert -fix-up算法：
我们假设插入的节点为x，p是x的父节点，z是x的祖父节点，那么fix-up的步骤如下：
1). 如果p的颜色为黑色，那么不需要调整，fix-up结束。
2). 如果p的颜色为红色，那么违反了#4, 做如下调整：
3). 如果p是z的左孩子，那么又分为下面三种情况：
Case 1：
Case 2：
Case 3：
4). 否则，做如下调整：
5). 将根节点设为黑色。
在红黑树中删除一个节点后，我们依然要保持其红黑树的性质。删除操作要比插入操作更为复杂一些。删除操作步骤如下：
1). 如果待删除节点z的左孩子和右孩子节点其中一个不是nil节点，那么将y设为待删除节点z的后继节点，否则将y设为z。(y临时保存待删除节点)
2). 如果y的左孩子不是nil节点，那么将y的左孩子赋给临时节点x，否则将y的右孩子赋给临时节点x。
3). 如果y的父节点为NULL，那么将x设为root节点
4). 将y节点从树上移除
5). 如果z跟y不是同一个节点，那么将z的key设为y的key
6). 如果y的颜色是黑色，那么需要调用delete-fix-up算法进行调整。
一个黑色节点的删除会违反红黑树性质#5，因此需要调整，但是违反性质#5调整起来非常困难，我们可以假想节点x(就是在上面删除步骤中替代了y位置的节点)多出来一个黑色，这样的话x就变成要么两个黑色，要么一红一黑，这就是违反了性质#4了。但是毕竟x本身只有一种颜色，我们硬生生给它增加了另一种颜色，所以，这个新增加的颜色还是需要去除的，在满足下面三个条件后，新增加的颜色和去掉：
下面是delete-fix-up算法的步骤：
1). 如果x不是根节点并且x的颜色是黑色的，那么重复下面的步骤：
2). 如果x是它的父节点的左孩子那么
Case 1:
Case 2：
Case 3：
Case 4:
3). 如果x是它的父节点右孩子，那么操作步骤与2)中描述相同，只是将其中的左孩子改为右孩子，将其中的右孩子改为左孩子即可。
4). 将x的颜色设为黑色。
上面介绍了红黑树的插入和删除操作。对于红黑树的遍历与二叉搜索树相同，这里不再介绍。对于上面提到的后继节点的求法，文中没有介绍，其实也比较简单，可以看我下面用C语言实现的红黑树的源码。希望本文对大家理解红黑树有所帮助。
/*
** rbtree header file
** rbtree.h
** author: 程序驱动世界
** reversion: 1.0
** 2021/06/08
**/
#ifndef __RB_TREE_H__
#define __RB_TREE_H__
#ifdef __cplusplus
extern "C" {
#endif
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <stdarg.h>
#define ASSERT(condition)
do{
if (condition){
NULL;
}else{
fflush(stdout);
fprintf(stderr, "ASSERT fAIled: %s, line: %un", __FILE__, __LINE__);
fflush(stderr);
abort();
}
}while(0)
#define RB_RED 0
#define RB_BLACK 1
typedef uint32_t keytype;
struct _rbtree_iterator{
keytype key;
};
typedef struct _rbtree_iterator* rbtree_iterator_t;
typedef struct rbnode rbnode_t;
typedef struct rbtree retree_t;
struct rbtree * rbtree_create();
void rbtree_preorder_traversal(struct rbtree * tree);
void rbtree_inorder_traversal(struct rbtree * tree);
void rbtree_postorder_traversal(struct rbtree * tree);
void rbtree_print(struct rbtree * tree);
int32_t rbtree_exist(struct rbtree * tree, keytype key);
rbtree_iterator_t rbtree_insert(struct rbtree * tree, keytype key);
int32_t rbtree_delete(struct rbtree * tree, keytype key);
void rbtree_destory(struct rbtree * tree);
uint32_t rbtree_node_count(struct rbtree * tree);
rbtree_iterator_t rbtree_begin(struct rbtree * tree);
rbtree_iterator_t rbtree_end(struct rbtree * tree);
rbtree_iterator_t rbtree_next(struct rbtree * tree, struct _rbtree_iterator * iter);
#ifdef __cplusplus
}
#endif
#endif // __RB_TREE_H__
/*
** rbtree c file
** rbtree.c
** author: 程序驱动世界
** reversion: 1.0
** 2021/06/08
**/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include "rbtree.h"
struct rbnode{
struct rbnode * parent;
struct rbnode * lchild;
struct rbnode * rchild;
uint8_t color;
struct _rbtree_iterator rbiter;
};
struct rbtree{
uint32_t node_count;
struct rbnode * root;
struct rbnode * nil;
};
/**
* | |
* x y
* / ----> /
* a y x c
* / /
* b c a b
**/
static void rbtree_left_rotate(struct rbtree * tree, struct rbnode *x){
struct rbnode * y = x->rchild; // set y to the x right child
x->rchild = y->lchild; // set the right child of x to the left child of y
y->lchild->parent = x; // set the parent of left child of y to x
y->parent = x->parent; // set the parent of y to the parent of x
if (!x->parent){ // if the parent of x is NULL, set the y as tree node
tree->root = y;
}else if (x == x->parent->lchild){ // if x is the left child of its parent
x->parent->lchild = y; // set the left child of x's parent to y
}else{ // if x is the right child of its parent
x->parent->rchild = y; // set the right child of x's parent to y
}
y->lchild = x; // set the left child of y to x
x->parent = y; // set the parent of x to y
}
/**
* | |
* y x
* / <---- /
* a x y c
* / /
* b c a b
**/
static void rbtree_right_rotate(struct rbtree * tree, struct rbnode *x){
struct rbnode * y = x->lchild; // set y to x left child
x->lchild = y->rchild; // set the left child of x to the right child of y
y->rchild->parent = x; // set the parent of y's right child to x
y->parent= x->parent; // set the parent of y to the parent of x
if(!x->parent){ // if the parent of x is NULL, set y as tree bode
tree->root = y;
}else if(x == x->parent->rchild){ // if x is the right child of its parent
x->parent->rchild = y; // set y as the right child of x's parent
}else{ // if x is the left child of its parent
x->parent->lchild = y; // set the left child of x's parent to y
}
y->rchild = x; // set the right child of y to x
x->parent = y; // set the parent of x to y
}
static void rbtree_insert_fixup(struct rbtree * tree, struct rbnode * z){
//Case 2: the color of the parent of the current node is BLACK
if(z->parent->color == RB_BLACK){
return; // Do not need to fixup
}
//Case 3: the color of the parent of the current node is RED
struct rbnode * y = tree->nil;
while(z->parent && z->parent->color == RB_RED){
if (z->parent == z->parent->parent->lchild){ // node's parent is node's grandparent's left child
y = z->parent->parent->rchild;
if (y && y->color == RB_RED){ //Case 3.1 the color of the uncle node of the current node is RED
z->parent->color = RB_BLACK; // set the color of current node's parent to BLACK
y->color = RB_BLACK; // set the uncle's color to BLACK
z->parent->parent->color = RB_RED; // set the color of grandparent to RED
z = z->parent->parent; // set the current node to grandparent
continue;
}else if(z == z->parent->rchild){ //Case3.2 the color of the uncle node is BLACK and the current node is the right child of its parent
z = z->parent; //set the current node to its parent
rbtree_left_rotate(tree, z); // left rotate
}
z->parent->color = RB_BLACK; //Case3.3 the color of the uncle node is BLACK, and the current node is the left child of its parent
z->parent->parent->color = RB_RED; // set the grandparent's color to RED
rbtree_right_rotate(tree, z->parent->parent); // right rotate with grandparent as the pivot
}else{
y = z->parent->parent->lchild;
if (y && y->color == RB_RED){ //Case 3.1 the color of the uncle node of the current node is RED
z->parent->color = RB_BLACK; // set the color of current node's parent to BLACK
y->color = RB_BLACK; // set the uncle's color to BLACK
z->parent->parent->color = RB_RED; // set the color of grandparent to RED
z = z->parent->parent; // set the current node to grandparent
continue;
}else if(z == z->parent->lchild){ //Case3.2 the color of the uncle node is BLACK and the current node is the left child of its parent
z = z->parent; //set the current node to its parent
rbtree_right_rotate(tree, z); // left rotate
}
z->parent->color = RB_BLACK; //Case3.3 the color of the uncle node is BLACK, and the current node is the left child of its parent
z->parent->parent->color = RB_RED; // set the grandparent's color to RED
rbtree_left_rotate(tree, z->parent->parent); // right rotate with grandparent as the pivot
}
}
tree->root->color = RB_BLACK;
}
static void rbtree_insert_impl(struct rbtree * tree, struct rbnode * z){
ASSERT(tree != NULL && z !=NULL);
//Case 1: The tree node is nil, just set the tree node to node
// And marked its color to black.
if(tree->root == tree->nil){
tree->root = z;
tree->root->color = RB_BLACK;
tree->node_count += 1;
return;
}
struct rbnode * x = tree->root;
struct rbnode * y = tree->nil;
while (x != tree->nil){
y = x;
if (z->rbiter.key < x->rbiter.key){
x = x->lchild;
}else{
x = x->rchild;
}
}
z->parent = y;
if(z->rbiter.key < y->rbiter.key){
y->lchild = z;
}else{
y->rchild = z;
}
z->lchild = tree->nil;
z->rchild = tree->nil;
z->color = RB_RED;
rbtree_insert_fixup(tree, z);
tree->node_count += 1;
}
static struct rbnode * rbtree_minimum(struct rbtree * tree, struct rbnode * x){
ASSERT(tree!=NULL);
struct rbnode * node = x;
if (!node){
return tree->nil;
}
while (node->lchild != tree->nil) {
node = node->lchild;
}
return node;
}
static struct rbnode * rbtree_maximum(struct rbtree * tree, struct rbnode * x){
ASSERT(tree!=NULL);
struct rbnode * node = x;
if(!node){
return tree->nil;
}
while (node->rchild != tree->nil) {
node = node->rchild;
}
return node;
}
static struct rbnode * rbtree_successor(struct rbtree * tree, struct rbnode * x) {
ASSERT(tree != NULL && x != NULL);
if (x->rchild != tree->nil){
return rbtree_minimum(tree, x->rchild);
}
struct rbnode * y = x->parent;
while (y && y != tree->nil && x == y->rchild) {
x = y;
y = y ->parent;
}
if(!y){
return tree->nil;
}
return y;
}
static struct rbnode * rbtree_predecessor(struct rbtree * tree, struct rbnode * x){
ASSERT(tree != NULL && x != NULL);
if(x->lchild != tree->nil){
return rbtree_maximum(tree, x->lchild);
}
struct rbnode * y = x->parent;
while(y && y != tree->nil && x == y->rchild){
x = y;
y = y->parent;
}
if(!y){
return tree->nil;
}
return y;
}
static void rbtree_delete_fixup(struct rbtree * tree, struct rbnode * x){
struct rbnode * w = tree->nil;
while (x != tree->root && x->color == RB_BLACK){ // x's color is BLACK and x is not the root of the tree
if (x == x->parent->lchild){
w = x->parent->rchild; // if x is the left child of its parent, set the w as x's sibling child
if (w->color == RB_RED){ // Case 1: x's sibling color is RED, so x'sparent and w's childs are all BLACK
w->color = RB_BLACK; // 1), set x's sibling node to BLACK
x->parent->color = RB_RED; // 2), set x's parent color to RED
rbtree_left_rotate(tree, x->parent); // 3), do the left rotation with x's parent as pivot
w = x->parent->rchild; // 4), reset the x's sibling node after the rotation
}else if(w->lchild->color == RB_BLACK &&
w->rchild->color == RB_BLACK){ // Case 2: x's sibling color is BLACK, and the children of x's sibling are all BLACK
w->color = RB_RED; // 1), set the sibling node color to RED
x = x->parent; // 2), set the x equal to its parent
}else {
if(w->rchild->color == RB_BLACK){ // Case 3: x's sibling color is BLACK, and the right child of w is BLACK while its left child is RED
w->lchild->color = RB_BLACK; // 1), set the left child of w to BLACK
w->color = RB_RED; // 2), set the w's colot to RED
rbtree_right_rotate(tree, w); // 3), do the rotation with w as pivot
w = x->parent->rchild; // 4), reset the sibling node after rotation
}
w->color = x->parent->color; // Case 4: x's sibling color is BLACK, the right child of w is RED, 1), set the parent color to w
x->parent->color = RB_BLACK; // 2), set x'parent color to BLACK
w->rchild->color = RB_BLACK; // 3), set the color of right child of sibling node to BLACK
rbtree_left_rotate(tree, x->parent); // 4), do the rotation with x'parent as pivot
x = tree->root; // 5), set x as root node of the tree
}
}else{
w = x->parent->lchild; // if x is the right child of its parent, set the w as x's sibling child
if (w->color == RB_RED){ // Case 1: x's sibling color is RED, so x'sparent and w's childs are all BLACK
w->color = RB_BLACK; // 1), set x's sibling node to BLACK
x->parent->color = RB_RED; // 2), set x's parent color to RED
rbtree_right_rotate(tree, x->parent); // 3), do the right rotation with x's parent as pivot
w = x->parent->lchild; // 4), reset the x's sibling node after the rotation
}else if(w->rchild->color == RB_BLACK &&
w->lchild->color == RB_BLACK){ // Case 2: x's sibling color is BLACK, and the children of x's sibling are all BLACK
w->color = RB_RED; // 1), set the sibling node color to RED
x = x->parent; // 2), set the x equal to its parent
}else { // Case 3: x's sibling color is BLACK, and the left child of w is BLACK while its right child is RED
if(w->lchild->color == RB_BLACK){
w->rchild->color = RB_BLACK; // 1), set the right child of w to BLACK
w->color = RB_RED; // 2), set the w's colot to RED
rbtree_left_rotate(tree, w); // 3), do the rotation with w as pivot
w = x->parent->lchild; // 4), reset the sibling node after rotation
}
w->color = x->parent->color; // Case 4: x's sibling color is BLACK, the left child of w is RED, 1), set the parent color to w
x->parent->color = RB_BLACK; // 2), set x'parent color to BLACK
w->lchild->color = RB_BLACK; // 3), set the color of left child of sibling node to BLACK
rbtree_right_rotate(tree, x->parent); // 4), do the rotation with x'parent as pivot
x = tree->root; // 5), set x as root node of the tree
}
}
}
x->color = RB_BLACK; // set the color of x to BLACK
}
static struct rbnode * rbtree_delete_impl(struct rbtree * tree, struct rbnode * z){
ASSERT(tree != NULL && z !=NULL);
struct rbnode * y = tree->nil;
struct rbnode * x = tree->nil;
if(z->lchild == tree->nil && z->rchild == tree->nil){ // the left and right child of the z is nil, leaf node
y = z; // set y to z
}else{
y = rbtree_successor(tree, z); // set y to the z's successor node
}
if (y->lchild != tree->nil){ // if the left child of y is not nil then set x equal to y's left child
x = y->lchild;
}else{
x = y->rchild; // otherwise set the right child of y to x
}
x->parent = y->parent; // set the parent of y to the parent of x
if (y->parent == NULL){ // the parent of y is NULL, so set x as tree node
tree->root = x;
}else if (y == y->parent->lchild){ // if y is its parent's left child, set x as the left child of y's parent
y->parent->lchild = x;
}else{
y->parent->rchild = x; // set x as the right child of y's parent
}
if (y != z){ // if y is not equal to z
z->rbiter.key = y->rbiter.key; // copy the key of y to the key of z, here we won't change the color
}
if (y->color == RB_BLACK){
rbtree_delete_fixup(tree, x); // if the color of y is BLACK, then need to fixup x
}
tree->node_count -= 1;
return y;
}
static void rbtree_preorder_traversal_impl(struct rbtree * tree, struct rbnode * node){
ASSERT(node != NULL);
if (node != tree->nil){
printf("%ld ", node->rbiter.key);
rbtree_preorder_traversal_impl(tree, node->lchild);
rbtree_preorder_traversal_impl(tree, node->rchild);
}
}
static void rbtree_inorder_traversal_impl(struct rbtree * tree, struct rbnode * node){
ASSERT(node != NULL);
if (node != tree->nil){
rbtree_inorder_traversal_impl(tree, node->lchild);
printf("%ld ", node->rbiter.key);
rbtree_inorder_traversal_impl(tree, node->rchild);
}
}
static void rbtree_postorder_traversal_impl(struct rbtree * tree, struct rbnode * node){
ASSERT(tree!=NULL && node != NULL);
if (node != tree->nil){
rbtree_postorder_traversal_impl(tree, node->lchild);
rbtree_postorder_traversal_impl(tree, node->rchild);
printf("%ld ", node->rbiter.key);
}
}
#define SPACE_COUNT 10
static void rbtree_print_impl(struct rbtree * tree, struct rbnode * node, int space){
if (tree == NULL) {
return;
}
space += SPACE_COUNT;
if (node == tree->nil) {
for (int i = SPACE_COUNT; i < space; i++) {
printf(" ");
}
printf("%s:%sn", "nil", "black");
return;
}
rbtree_print_impl(tree, node->rchild, space);
printf("n");
for (int i = SPACE_COUNT; i < space; i++) {
printf(" ");
}
printf("%ld:%sn", node->rbiter.key, node->color == RB_RED ? "red" : "black");
rbtree_print_impl(tree, node->lchild, space);
}
static struct rbnode * rbtree_search(struct rbtree *tree, keytype key){
struct rbnode * node = tree->root;
while(node != tree->nil && node->rbiter.key != key){
if (key < node->rbiter.key){
node = node->lchild;
}else{
node = node->rchild;
}
}
return node;
}
static struct rbnode * rbtree_create_node(struct rbtree * tree, keytype key){
struct rbnode * node = (struct rbnode *)malloc(sizeof(struct rbnode));
if(!node){
return tree->nil;
}
node->rbiter.key = key;
node->lchild = tree->nil;
node->rchild = tree->nil;
node->parent = NULL;
node->color = RB_BLACK;
return node;
}
static void rbtree_destroy_impl(struct rbtree * tree, struct rbnode * node){
if (node == tree->nil){
return;
}
if (node->lchild != tree->nil){
rbtree_destroy_impl(tree, node->lchild);
}
if (node->rchild != tree->nil){
rbtree_destroy_impl(tree, node->rchild);
}
free(node);
}
struct rbtree * rbtree_create(){
struct rbtree * tree = (struct rbtree * )malloc(sizeof(struct rbtree));
ASSERT(tree != NULL);
tree->nil = (struct rbnode *)malloc(sizeof(struct rbnode));
ASSERT(tree->nil != NULL);
tree->nil->lchild = NULL;
tree->nil->rchild = NULL;
tree->nil->parent = NULL;
tree->nil->color = RB_BLACK;
tree->root = tree->nil;
tree->node_count = 0;
return tree;
}
void rbtree_preorder_traversal(struct rbtree * tree){
rbtree_preorder_traversal_impl(tree, tree->root);
}
void rbtree_inorder_traversal(struct rbtree * tree){
rbtree_inorder_traversal_impl(tree, tree->root);
}
void rbtree_postorder_traversal(struct rbtree * tree){
rbtree_postorder_traversal_impl(tree, tree->root);
}
void rbtree_print(struct rbtree *tree){
ASSERT(tree!=NULL);
rbtree_print_impl(tree, tree->root, 0);
}
int32_t rbtree_exist(struct rbtree * tree, keytype key){
ASSERT(tree != NULL);
if (tree->root != tree->nil){
return rbtree_search(tree, key) ? 0 : -1;
}
return -1;
}
rbtree_iterator_t rbtree_insert(struct rbtree * tree, keytype key){
ASSERT(tree != NULL);
struct rbnode * fnode = rbtree_search(tree, key);
if(rbtree_search(tree, key) != tree->nil){ // key already exist.
return &fnode->rbiter;
}
struct rbnode * node = rbtree_create_node(tree, key);
if (node != tree->nil){
rbtree_insert_impl(tree, node);
return &node->rbiter;
}
return 0; // error occurred
}
int32_t rbtree_delete(struct rbtree * tree, keytype key){
ASSERT(tree != NULL);
struct rbnode * node = rbtree_search(tree, key);
if( node == tree->nil){
return -1; // does not exist
}
node = rbtree_delete_impl(tree, node);
free(node);
return 0;
}
void rbtree_destory(struct rbtree * tree){
ASSERT(tree != NULL);
struct rbnode *node = tree->root;
rbtree_destroy_impl(tree, tree->root);
free(tree->nil);
free(tree);
}
uint32_t rbtree_node_count(struct rbtree * tree){
ASSERT(tree != NULL);
return tree->node_count;
}
rbtree_iterator_t rbtree_begin(struct rbtree * tree){
ASSERT(tree != NULL);
struct rbnode * node = rbtree_minimum(tree, tree->root);
if (node == tree->nil){
return NULL;
}
return &node->rbiter;
}
rbtree_iterator_t rbtree_end(struct rbtree * tree){
return NULL;
}
rbtree_iterator_t rbtree_next(struct rbtree * tree, struct _rbtree_iterator * iter){
ASSERT(tree !=NULL);
if (!iter){
return NULL;
}
struct rbnode * x = (struct rbnode *)(((char *)iter) - ((size_t)&(((struct rbnode *)0)->rbiter)));
struct rbnode * node = rbtree_successor(tree, x);
if (node == tree->nil){
return NULL;
}
return &node->rbiter;
}
京公网安备 11010802035086号