node32(node32激活码)

数据结构-红黑树

像AVL树，红黑树是一个自我平衡的二叉查找树。黑树还解决了二叉查找树在某些情况下会退化为链表的问题。但是红黑树没有AVL树那么高度均衡，这使得在频繁插入和删除的情况下，红黑树比AVL树效率更高。但在插入和删除操作较少、搜索频繁的情况下，AVL树更好。实际上红黑树(linux/rbtree.h)是在linux内核中实现的。Linux内核使用红黑树来管理和调度进程。C++标准库的map也是用红黑树实现的，定时器在nginx中也是用红黑树实现的。我们来了解一下这种红黑树，这是很多牛X软件的底层数据结构。

红黑树的定义和特性

首先，红黑树是一个BST(二叉查找树)，但红黑树的每个节点都包含一个额外的域来存储颜色属性(每个节点不是红色就是黑色)。红黑树必须满足以下特性:

每一个节点都有颜色，或者为黑色或者为红色红黑树的根节点必须是黑色的叶子节点(叫做nil或者NULL节点)都是黑色的如果一个红色的节点有子节点，那么子节点必须是黑色的从任意一个节点出发沿着其子节点的所有路径到达叶子节点的黑色深度相同(这里的黑色深度指的是黑色节点的数量)。

下面的例子是一棵红色和黑色的树:

红黑树的每个节点至少包含以下属性:

颜色(color)键值(key)左孩子指针(lchild)右孩子指针(rchild)父节点指针(parent，根节点parent为空)

由于红黑树的五个属性的约束，红黑树的根节点到叶节点的任何路径都不可能超过其他根节点到叶节点路径的两倍，这就使得红黑树保持了一种平衡。

红黑树的基本操作

类似于AVL数，红黑树在调整平衡时需要旋转。

左旋

左手操作步骤如下:

1).初始状态:

2).如果Y有左子树，那么设X为Y的左子树β的父节点。

3).设X的右子树为β

4).如果X的父节点为空，则设置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为空，则设置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)

红黑树的插入

对于红黑树的插入操作，我们希望插入后尽可能少的违反红黑树的五个属性。基于此，我先把要插入的节点标记为红色。然后按照BST的插入方法插入节点。这里之所以把节点标为红色，是因为可以保证两点。插入节点后，如果插入位置是根节点，将违反属性#3。但是，这种情况非常容易处理，只需将颜色设置为黑色即可。如果插入位置不是根节点，那么它只违反了属性#4。只要针对属性#4进行调整，否则就违反了属性#5。调整属性#5比属性#4困难得多。

插入后，我对其进行了调整，以符合红黑树的本性。具体调整主要是做以下两件事:

1).调整节点的颜色。

2)旋转操作

下面是插入操作的具体步骤:

1).用红色标记要插入的节点。

2).首先安装BST插入方法，插入要插入的节点。不知道BST插入方法的同学可以参考我之前的文章:& gt。

3)调整插入的树(insert fix up ),使其仍然保持红黑树的性质。

这里我们关注插入修复算法:

假设插入的节点是X，P是X的父节点，Z是X的祖父节点，那么修正的步骤如下:

1).如果P的颜色是黑色，则不需要调整，修正结束。

2).如果P的颜色是红色，就违反了#4。进行以下调整:

3).如果P是Z的左子，那么分为以下三种情况:

案例1:

如果z的右孩子是红色，那么将z的左孩子和右孩子的节点设为黑色，并将z的颜色设为红色。将x(当前调整的节点)设为z

案例二:

否则如果当前调整节点x是p的右孩子，那么将x设为p对x进行左右(Left-Right)旋转。

案例三:

将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的父节点为空，那么将X设置为根节点

4).从树中删除Y节点

5).如果Z和Y不是同一个节点，那么将Z的键设置为Y的键。

6).如果Y的颜色是黑色，那么你需要调用delete-fix-up算法来调整它。

删除一个黑节点会违反红黑树属性#5，所以需要调整。但是，调整财产#5的违反是非常困难的。我们可以假设节点X(即在上面的删除步骤中替换了Y位置的节点)有一个额外的黑色，这样X要么变成两黑，要么变成一红一黑，这就违反了属性#4。但毕竟X本身只有一种颜色，我们硬生生的给它加了另一种颜色。所以这个新加的颜色还是要去掉的。满足以下三个条件后，新添加的颜色又被删除:

x是根节点如果x是红黑复合节点，那么这个时候将x节点设为黑色即可经过适当的旋转和颜色调整后

以下是删除-修复算法的步骤:

1).如果X不是根节点，并且X的颜色是黑色，则重复以下步骤:

2).如果X是其父节点的左子节点，则

将w设为x的兄弟节点如果x的父节点的右孩子是红色的：

案例1:

将x父节点的右孩子设为黑色将x父节点设为红色对x的父节点执行左旋操作将x父节点的右孩子赋给w如果w的左孩子和右孩子都是黑色：

案例二:

将w的颜色设为红色将x的父节点赋给x否则如果w的右孩子的颜色是黑色的：

案例三:

将w左孩子的颜色设为黑色将w设为红色对w执行右旋操作将x父节点的右孩子赋给w如果上面的所有情形都没有发生，那么执行下面Case 4：

案例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 <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: %u\n", __FILE__, __LINE__);\ fflush(stderr);\ abort();\ }\}while(0)#define RB_RED 0#define RB_BLACK 1typedef 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 10static 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\n", "nil", "black"); return; } rbtree_print_impl(tree, node->rchild, space); printf("\n"); for (int i = SPACE_COUNT; i < space; i++) { printf(" "); } printf("%ld:%s\n", 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;}