和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 <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;
}
