数据结构

　　数据结构 --- 红黑树
　　和AVL树一样，红黑树也是自平衡二叉搜索树。红黑树同样解决了在特定情况下二叉搜索树会退化成链表的问题。但是红黑树又不像AVL树那样高度平衡，这就让红黑树在插入删除频繁的场合效率优于AVL树。但是在插入和删除操作较少，而查找频繁的场合AVL树则更胜一筹。实际上linux内核中实现了红黑树(linux/rbtree.h)。linux内核使用红黑树来管理和调度进程。 C++标准库的map也是用红黑树来实现的，而nginx中也使用红黑树来实现了定时器。下面我们就来学习一下这个作为很多牛X软件的底层数据结构红黑树(red-black tree)。红黑树的定义和特性
　　首先红黑树是一颗BST(二分查找树)，但是红黑树每一个节点包含一个额外的域用来存储颜色属性(每一个节点要么为红色，要么为黑色)。一棵红黑树必须满足下面的性质：每一个节点都有颜色，或者为黑色或者为红色红黑树的根节点必须是黑色的叶子节点(叫做nil或者NULL节点)都是黑色的如果一个红色的节点有子节点，那么子节点必须是黑色的从任意一个节点出发沿着其子节点的所有路径到达叶子节点的黑色深度相同(这里的黑色深度指的是黑色节点的数量)。
　　如下图所示的例子就是一颗红黑树：
　　对于红黑树的每一个节点都至少包含下面列出的属性：颜色(color)键值(key)左孩子指针(lchild)右孩子指针(rchild)父节点指针(parent，根节点parent为空)
　　正是由于红黑树(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
　　左右(Left-Right)旋转和右左(Right-Left)旋转
　　在左右旋转时，我们先进行左旋，然后再进行右旋，如下步骤：
　　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：如果z的右孩子是红色，那么将z的左孩子和右孩子的节点设为黑色，并将z的颜色设为红色。将x(当前调整的节点)设为z
　　Case 2：否则如果当前调整节点x是p的右孩子，那么将x设为p对x进行左右(Left-Right)旋转。
　　Case 3：将p的颜色设置为黑色，同时将z的颜色设置为红色对z进行右旋
　　4). 否则，做如下调整：如果x的祖父节点z的左孩子是红色的， 那么将z的左孩子和右孩子设为黑色，同时将z设为红色将当前调整节点设为z否则如果当前调整节点x是其父节点p的左孩子，那么将p设为当前调整节点x，并且对x做右旋操作。将x的父节点p设为黑色，祖父节点z设为红色对z进行左旋操作。
　　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本身只有一种颜色，我们硬生生给它增加了另一种颜色，所以，这个新增加的颜色还是需要去除的，在满足下面三个条件后，新增加的颜色和去掉：x是根节点如果x是红黑复合节点，那么这个时候将x节点设为黑色即可经过适当的旋转和颜色调整后
　　下面是delete-fix-up算法的步骤：
　　1). 如果x不是根节点并且x的颜色是黑色的，那么重复下面的步骤：
　　2). 如果x是它的父节点的左孩子那么将w设为x的兄弟节点如果x的父节点的右孩子是红色的：
　　Case 1:将x父节点的右孩子设为黑色将x父节点设为红色对x的父节点执行左旋操作将x父节点的右孩子赋给w如果w的左孩子和右孩子都是黑色：
　　Case 2：将w的颜色设为红色将x的父节点赋给x否则如果w的右孩子的颜色是黑色的：
　　Case 3：将w左孩子的颜色设为黑色将w设为红色对w执行右旋操作将x父节点的右孩子赋给w如果上面的所有情形都没有发生，那么执行下面Case 4：
　　Case 4:将w的颜色设为x父节点的颜色将x父节点的颜色设为黑色将w右孩子的颜色设为黑色对x执行左旋操作将x设为树的根节点
　　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  #include  #include  #include   #define ASSERT(condition)  do{     if (condition){         NULL;     }else{         fflush(stdout); 		fprintf(stderr, ＂ASSERT failed: %s, line: %u ＂, __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  #include  #include  #include  #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:%s ＂, ＂nil＂, ＂black＂); 		return; 	}  	rbtree_print_impl(tree, node->rchild, space);  	printf(＂ ＂); 	for (int i = SPACE_COUNT; i < space; i++) { 		printf(＂ ＂); 	} 	printf(＂%ld:%s ＂, 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; }