您当前的位置:首页 > 电脑百科 > 程序开发 > 算法

数据结构 --- 红黑树

时间:2022-06-16 10:49:15  来源:  作者:程序驱动世界

和AVL树一样,红黑树也是自平衡二叉搜索树。红黑树同样解决了在特定情况下二叉搜索树会退化成链表的问题。但是红黑树又不像AVL树那样高度平衡,这就让红黑树在插入删除频繁的场合效率优于AVL树。但是在插入和删除操作较少,而查找频繁的场合AVL树则更胜一筹。实际上linux内核中实现了红黑树(linux/rbtree.h)。linux内核使用红黑树来管理和调度进程。 C++标准库的map也是用红黑树来实现的,而Nginx中也使用红黑树来实现了定时器。下面我们就来学习一下这个作为很多牛X软件的底层数据结构红黑树(red-black tree)。

  1. 红黑树的定义和特性

首先红黑树是一颗BST(二分查找树),但是红黑树每一个节点包含一个额外的域用来存储颜色属性(每一个节点要么为红色,要么为黑色)。一棵红黑树必须满足下面的性质:

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

如下图所示的例子就是一颗红黑树:

数据结构 --- 红黑树

 

对于红黑树的每一个节点都至少包含下面列出的属性:

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

正是由于红黑树(red-black tree)的五条性质的约束,这使得红黑树从根节点出发到叶子节点的任何一条路径都不可能超过其他从根节点出发到叶子节点路径的两倍,这使得红黑树可以维持平衡。

  1. 红黑树的基本操作

和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进行左旋)

数据结构 --- 红黑树

 

  1. 红黑树的插入

对红黑树的插入操作,我们希望插入后对红黑树的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:

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

Case 2:

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

Case 3:

  1. 将p的颜色设置为黑色,同时将z的颜色设置为红色
  2. 对z进行右旋

4). 否则,做如下调整:

  1. 如果x的祖父节点z的左孩子是红色的, 那么将z的左孩子和右孩子设为黑色,同时将z设为红色
  2. 将当前调整节点设为z
  3. 否则如果当前调整节点x是其父节点p的左孩子,那么将p设为当前调整节点x,并且对x做右旋操作。
  4. 将x的父节点p设为黑色,祖父节点z设为红色
  5. 对z进行左旋操作。

5). 将根节点设为黑色。

  1. 红黑树的删除

在红黑树中删除一个节点后,我们依然要保持其红黑树的性质。删除操作要比插入操作更为复杂一些。删除操作步骤如下:

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是它的父节点的左孩子那么

  1. 将w设为x的兄弟节点
  2. 如果x的父节点的右孩子是红色的:

Case 1:

  1. 将x父节点的右孩子设为黑色
  2. 将x父节点设为红色
  3. 对x的父节点执行左旋操作
  4. 将x父节点的右孩子赋给w
  5. 如果w的左孩子和右孩子都是黑色:

Case 2:

  1. 将w的颜色设为红色
  2. 将x的父节点赋给x
  3. 否则如果w的右孩子的颜色是黑色的:

Case 3:

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

Case 4:

  1. 将w的颜色设为x父节点的颜色
  2. 将x父节点的颜色设为黑色
  3. 将w右孩子的颜色设为黑色
  4. 对x执行左旋操作
  5. 将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;
}


Tags:红黑树   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,如有任何标注错误或版权侵犯请与我们联系(Email:2595517585@qq.com),我们将及时更正、删除,谢谢。
▌相关推荐
和AVL树一样,红黑树也是自平衡二叉搜索树。红黑树同样解决了在特定情况下二叉搜索树会退化成链表的问题。但是红黑树又不像AVL树那样高度平衡,这就让红黑树在插入删除频繁的场...【详细内容】
2022-06-16  Tags: 红黑树  点击:(21)  评论:(0)  加入收藏
1. 红黑树1.1 红黑树概述红黑树和我们以前学过的AVL树类似,都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡,从而获得较高的查找性能。不过自从红黑树出来后,AVL...【详细内容】
2021-06-24  Tags: 红黑树  点击:(193)  评论:(0)  加入收藏
前言本文咱们了解一下红黑树的设计,相比 jdk1.7 的 HashMap 而言,jdk1.8 最重要的就是引入了红黑树的设计,当冲突的链表长度超过 8 个的时候,链表结构就会转为红黑树结构。01、...【详细内容】
2021-01-18  Tags: 红黑树  点击:(210)  评论:(0)  加入收藏
絮叨学校短学期刚结束了,离学校开学还有很多天,一直呆在寝室玩游戏岂不是浪费了大好时光,于是心血来潮想看看HashMap的源码。虽然我没有经历过面试,但是java程序员都知道,HashMap...【详细内容】
2020-09-27  Tags: 红黑树  点击:(101)  评论:(0)  加入收藏
本文将通过图文的方式讲解红黑树的知识点,并且不会涉及到任何代码,相信我,在懂得红黑树实现原理前,看代码会一头雾水的,当原理懂了,代码也就按部就班写而已,没任何难度。 阅读本文...【详细内容】
2020-03-18  Tags: 红黑树  点击:(56)  评论:(0)  加入收藏
红黑树是二叉搜索树的增强版,我们知道优化二叉搜索树的核心是优化二叉搜索树的高度,也就是使树尽可能地平衡,红黑树就是解决这个问题的,它能够尽可能地平衡二叉搜索树的高度,保证...【详细内容】
2020-01-03  Tags: 红黑树  点击:(98)  评论:(0)  加入收藏
整篇文章的思路是这样的,红黑树其实就是一种数据结构,设计它的目的就是为了高效地进行增删改查,所以我们文章的顺序也会按照这个思路来进行。我们先从二叉查找树逐渐引入到红黑...【详细内容】
2019-09-23  Tags: 红黑树  点击:(199)  评论:(0)  加入收藏
▌简易百科推荐
背景对抗是反作弊永恒的主旋律,面对对抗我们需要做到快速响应、见招拆招、在变化中发现不变的本质。在反作弊场景中,黑产必须通过文本进行信息传递或触达受害者,而文本由于其生...【详细内容】
2022-07-14  字节跳动技术团队    Tags:算法   点击:(4)  评论:(0)  加入收藏
请实现一个函数用来匹配包含&#39;. &#39;和&#39;*&#39;的正则表达式。模式中的字符&#39;.&#39;表示任意一个字符,而&#39;*&#39;表示它前面的字符可以出现任意次(含0次)。在本题...【详细内容】
2022-07-13  做架构师不做框架师    Tags:正则表达式   点击:(6)  评论:(0)  加入收藏
高手:滑动窗口是一种比较常用的数据统计算法。简单来说,就是在一个大的数组上,定义一个固定长度的滑动窗口,然后这个窗口在数组上进行滑动。在窗口滑动的过程中,左边会出一个元素...【详细内容】
2022-07-13  跟着Mic学架构    Tags:算法   点击:(8)  评论:(0)  加入收藏
一、希尔排序介绍希尔排序这个名字,来源于它的发明者希尔,也称作“缩小增量排序”,是插入排序的一种更高效的改进版本。希尔排序是基于插入排序的以下两点性质而提出改进方法的...【详细内容】
2022-07-08  程序猿星球    Tags:希尔排序   点击:(14)  评论:(0)  加入收藏
描述为了保证第三方应用与API服务器之间通信的安全性,防止Secret Key盗用、数据篡改等恶意攻击行为,开放平台API 服务器使用签名机制,应用在调用开放平台API,需要计算出一个签...【详细内容】
2022-07-08  零一间    Tags:算法   点击:(9)  评论:(0)  加入收藏
6. 蒙特卡洛算法6.1 计算&pi;" role="presentation" style="display: inline; font-style: normal; font-weight: normal; text-indent: 0px; text-align: left; text-trans...【详细内容】
2022-07-08  海椰人  博客园  Tags:算法   点击:(17)  评论:(0)  加入收藏
数学统计在我们的程序当中特别是数据分析当中是必不可少的一部分,本文就来介绍一下 NumPy 常见的统计函数。最大值与最小值numpy.amin()用于计算数组中的元素沿指定轴的最小...【详细内容】
2022-07-07  VT漫步    Tags:统计函数   点击:(15)  评论:(0)  加入收藏
一、基础概念1、Sorted(单调递增or单调递减)2、Bounded(存在上下界)3、Accessible by index(能够通过索引访问,数组适合,but链表不适合)二分查找是一种在每次比较之后将查找空间一...【详细内容】
2022-07-04  程序猿星球    Tags:算法   点击:(14)  评论:(0)  加入收藏
分布式系统的模型为了更容易理解分布式系统,我们先来构建一个模型。 武当派因为人口增长变成 11 个办事处分散在地图各地; 办事处之间的通信只能依靠信鸽; 一只信鸽可能无法完...【详细内容】
2022-07-01  算法的秘密    Tags:共识算法   点击:(20)  评论:(0)  加入收藏
在本课程中, 您将 详细、逐步地解释经典的精选 LeetCode 问题 ,您将了解解决技术编码面试问题的最佳方法。 这是我在准备面试时希望参加的课程。课程英文名:LeetCode in Java A...【详细内容】
2022-06-30  IT教程精选    Tags:LeetCode   点击:(19)  评论:(0)  加入收藏
站内最新
站内热门
站内头条