<返回更多

红黑树底层原理及Linux内核红黑树算法深度研究

2021-06-24    Linux天神
加入收藏

1. 红黑树

1.1 红黑树概述

红黑树和我们以前学过的AVL树类似,都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡,从而获得较高的查找性能。不过自从红黑树出来后,AVL树就被放到了博物馆里,据说是红黑树有更好的效率,更高的统计性能。这一点在我们了解了红黑树的实现原理后,就会有更加深切的体会。

红黑树和AVL树的区别在于它使用颜色来标识结点的高度,它所追求的是局部平衡而不是AVL树中的非常严格的平衡。学过数据结构的人应该都已经领教过AVL树的复杂,但AVL树的复杂比起红黑树来说简直是小巫见大巫,红黑树才是真正的变态级数据结构。

由于STL中的关联式容器默认的底层实现都是红黑树,因此红黑树对于后续学习STL源码还是很重要的,有必要掌握红黑树的实现原理和源码实现。

红黑树是AVL树的变种,红黑树通过一些着色法则确保没有一条路径会比其它路径长出两倍,因而达到接近平衡的目的。所谓红黑树,不仅是一个二叉搜索树,而且必须满足一下规则:

上面的这些约束保证了这个树大致上是平衡的,这也决定了红黑树的插入、删除、查询等操作是比较快速的。 根据规则4,新增节点必须为红色;根据规则3,新增节点之父节点必须为黑色。当新增节点根据二叉搜索树的规则到达其插入点时,却未能符合上述条件时,就必须调整颜色并旋转树形,如下图:

红黑树底层原理及Linux内核红黑树算法深度研究

 

假设我们为上图分别插入节点3、8、35、75,根据二叉搜索树的规则,插入这四个节点后,我们会发现它们都破坏了红黑树的规则,因此我们必须调整树形,也就是旋转树形并改变节点的颜色。

1.2 红黑树上结点的插入

在讨论红黑树的插入操作之前必须要明白,任何一个即将插入的新结点的初始颜色都为红色。这一点很容易理解,因为插入黑点会增加某条路径上黑结点的数目,从而导致整棵树黑高度的不平衡。但如果新结点的父结点为红色时(如下图所示),将会违反红黑树的性质:一条路径上不能出现相邻的两个红色结点。这时就需要通过一系列操作来使红黑树保持平衡。

红黑树底层原理及Linux内核红黑树算法深度研究

 

为了清楚地表示插入操作以下在结点中使用“新”字表示一个新插入的结点;使用“父”字表示新插入点的父结点;使用“叔”字表示“父”结点的兄弟结点;使用“祖”字表示“父”结点的父结点。插入操作分为以下几种情况:

1.2.1 黑父

如下图所示,如果新节点的父结点为黑色结点,那么插入一个红点将不会影响红黑树的平衡,此时插入操作完成。红黑树比AVL树优秀的地方之一在于黑父的情况比较常见,从而使红黑树需要旋转的几率相对AVL树来说会少一些。

红黑树底层原理及Linux内核红黑树算法深度研究

 

1.2.2 红父

如果新节点的父结点为红色,这时就需要进行一系列操作以保证整棵树红黑性质。如下图所示,由于父结点为红色,此时可以判定,祖父结点必定为黑色。这时需要根据叔父结点的颜色来决定做什么样的操作。青色结点表示颜色未知。由于有可能需要根结点到新点的路径上进行多次旋转操作,而每次进行不平衡判断的起始点(我们可将其视为新点)都不一样。所以我们在此使用一个蓝色箭头指向这个起始点,并称之为判定点。

红黑树底层原理及Linux内核红黑树算法深度研究

 

1.2.2.1 红叔

当叔父结点为红色时,如下图所示,无需进行旋转操作,只要将父和叔结点变为黑色,将祖父结点变为红色即可。但由于祖父结点的父结点有可能为红色,从而违反红黑树性质。此时必须将祖父结点作为新的判定点继续向上(迭代)进行平衡操作。

红黑树底层原理及Linux内核红黑树算法深度研究

 

需要注意的是,无论“父节点”在“叔节点”的左边还是右边,无论“新节点”是“父节点”的左孩子还是右孩子,它们的操作都是完全一样的(其实这种情况包括4种,只需调整颜色,不需要旋转树形)。

1.2.2.2 黑叔

当叔父结点为黑色时,需要进行旋转,以下图示了所有的旋转可能:

Case 1:

红黑树底层原理及Linux内核红黑树算法深度研究

 

Case 2:

红黑树底层原理及Linux内核红黑树算法深度研究

 

Case 3:

红黑树底层原理及Linux内核红黑树算法深度研究

 

Case 4:

红黑树底层原理及Linux内核红黑树算法深度研究

 

可以观察到,当旋转完成后,新的旋转根全部为黑色,此时不需要再向上回溯进行平衡操作,插入操作完成。需要注意,上面四张图的“叔”、“1”、“2”、“3”结点有可能为黑哨兵结点。

其实红黑树的插入操作不是很难,甚至比AVL树的插入操作还更简单些。红黑树的插入操作源代码如下:

// 元素插入操作  insert_unique()
// 插入新值:节点键值不允许重复,若重复则插入无效
// 注意,返回值是个pair,第一个元素是个红黑树迭代器,指向新增节点
// 第二个元素表示插入成功与否
template<class Key , class Value , class KeyOfValue , class Compare , class Alloc>
pair<typename rb_tree<Key , Value , KeyOfValue , Compare , Alloc>::iterator , bool>
rb_tree<Key , Value , KeyOfValue , Compare , Alloc>::insert_unique(const Value &v)
{
    rb_tree_node* y = header;    // 根节点root的父节点
    rb_tree_node* x = root();    // 从根节点开始
    bool comp = true;
    while(x != 0)
    {
        y = x;
        comp = key_compare(KeyOfValue()(v) , key(x));    // v键值小于目前节点之键值?
        x = comp ? left(x) : right(x);   // 遇“大”则往左,遇“小于或等于”则往右
    }
    // 离开while循环之后,y所指即插入点之父节点(此时的它必为叶节点)
    iterator j = iterator(y);     // 令迭代器j指向插入点之父节点y
    if(comp)     // 如果离开while循环时comp为真(表示遇“大”,将插入于左侧)
    {
        if(j == begin())    // 如果插入点之父节点为最左节点
            return pair<iterator , bool>(_insert(x , y , z) , true);
        else     // 否则(插入点之父节点不为最左节点)
            --j;   // 调整j,回头准备测试
    }
    if(key_compare(key(j.node) , KeyOfValue()(v) ))
        // 新键值不与既有节点之键值重复,于是以下执行安插操作
        return pair<iterator , bool>(_insert(x , y , z) , true);
    // 以上,x为新值插入点,y为插入点之父节点,v为新值
 
    // 进行至此,表示新值一定与树中键值重复,那么就不应该插入新值
    return pair<iterator , bool>(j , false);
}
 
// 真正地插入执行程序 _insert()
template<class Key , class Value , class KeyOfValue , class Compare , class Alloc>
typename<Key , Value , KeyOfValue , Compare , Alloc>::_insert(base_ptr x_ , base_ptr y_ , const Value &v)
{
    // 参数x_ 为新值插入点,参数y_为插入点之父节点,参数v为新值
    link_type x = (link_type) x_;
    link_type y = (link_type) y_;
    link_type z;
 
    // key_compare 是键值大小比较准则。应该会是个function object
    if(y == header || x != 0 || key_compare(KeyOfValue()(v) , key(y) ))
    {
        z = create_node(v);    // 产生一个新节点
        left(y) = z;           // 这使得当y即为header时,leftmost() = z
        if(y == header)
        {
            root() = z;
            rightmost() = z;
        }
        else if(y == leftmost())     // 如果y为最左节点
            leftmost() = z;          // 维护leftmost(),使它永远指向最左节点
    }
    else
    {
        z = create_node(v);        // 产生一个新节点
        right(y) = z;              // 令新节点成为插入点之父节点y的右子节点
        if(y == rightmost())
            rightmost() = z;       // 维护rightmost(),使它永远指向最右节点
    }
    parent(z) = y;      // 设定新节点的父节点
    left(z) = 0;        // 设定新节点的左子节点
    right(z) = 0;       // 设定新节点的右子节点
    // 新节点的颜色将在_rb_tree_rebalance()设定(并调整)
    _rb_tree_rebalance(z , header->parent);      // 参数一为新增节点,参数二为根节点root
    ++node_count;       // 节点数累加
    return iterator(z);  // 返回一个迭代器,指向新增节点
}
 
 
// 全局函数
// 重新令树形平衡(改变颜色及旋转树形)
// 参数一为新增节点,参数二为根节点root
inline void _rb_tree_rebalance(_rb_tree_node_base* x , _rb_tree_node_base*& root)
{
    x->color = _rb_tree_red;    //新节点必为红
    while(x != root && x->parent->color == _rb_tree_red)    // 父节点为红
    {
        if(x->parent == x->parent->parent->left)      // 父节点为祖父节点之左子节点
        {
            _rb_tree_node_base* y = x->parent->parent->right;    // 令y为伯父节点
            if(y && y->color == _rb_tree_red)    // 伯父节点存在,且为红
            {
                x->parent->color = _rb_tree_black;           // 更改父节点为黑色
                y->color = _rb_tree_black;                   // 更改伯父节点为黑色
                x->parent->parent->color = _rb_tree_red;     // 更改祖父节点为红色
                x = x->parent->parent;
            }
            else    // 无伯父节点,或伯父节点为黑色
            {
                if(x == x->parent->right)   // 如果新节点为父节点之右子节点
                {
                    x = x->parent;
                    _rb_tree_rotate_left(x , root);    // 第一个参数为左旋点
                }
                x->parent->color = _rb_tree_black;     // 改变颜色
                x->parent->parent->color = _rb_tree_red;
                _rb_tree_rotate_right(x->parent->parent , root);    // 第一个参数为右旋点
            }
        }
        else          // 父节点为祖父节点之右子节点
        {
            _rb_tree_node_base* y = x->parent->parent->left;    // 令y为伯父节点
            if(y && y->color == _rb_tree_red)    // 有伯父节点,且为红
            {
                x->parent->color = _rb_tree_black;           // 更改父节点为黑色
                y->color = _rb_tree_black;                   // 更改伯父节点为黑色
                x->parent->parent->color = _rb_tree_red;     // 更改祖父节点为红色
                x = x->parent->parent;          // 准备继续往上层检查
            }
            else    // 无伯父节点,或伯父节点为黑色
            {
                if(x == x->parent->left)        // 如果新节点为父节点之左子节点
                {
                    x = x->parent;
                    _rb_tree_rotate_right(x , root);    // 第一个参数为右旋点
                }
                x->parent->color = _rb_tree_black;     // 改变颜色
                x->parent->parent->color = _rb_tree_red;
                _rb_tree_rotate_left(x->parent->parent , root);    // 第一个参数为左旋点
            }
        }
    }//while
    root->color = _rb_tree_black;    // 根节点永远为黑色
}
 
 
// 左旋函数
inline void _rb_tree_rotate_left(_rb_tree_node_base* x , _rb_tree_node_base*& root)
{
    // x 为旋转点
    _rb_tree_node_base* y = x->right;          // 令y为旋转点的右子节点
    x->right = y->left;
    if(y->left != 0)
        y->left->parent = x;           // 别忘了回马枪设定父节点
    y->parent = x->parent;
 
    // 令y完全顶替x的地位(必须将x对其父节点的关系完全接收过来)
    if(x == root)    // x为根节点
        root = y;
    else if(x == x->parent->left)         // x为其父节点的左子节点
        x->parent->left = y;
    else                                  // x为其父节点的右子节点
        x->parent->right = y;
    y->left = x;
    x->parent = y;
}
 
 
// 右旋函数
inline void _rb_tree_rotate_right(_rb_tree_node_base* x , _rb_tree_node_base*& root)
{
    // x 为旋转点
    _rb_tree_node_base* y = x->left;          // 令y为旋转点的左子节点
    x->left = y->right;
    if(y->right != 0)
        y->right->parent = x;           // 别忘了回马枪设定父节点
    y->parent = x->parent;
 
    // 令y完全顶替x的地位(必须将x对其父节点的关系完全接收过来)
    if(x == root)
        root = y;
    else if(x == x->parent->right)         // x为其父节点的右子节点
        x->parent->right = y;
    else                                  // x为其父节点的左子节点
        x->parent->left = y;
    y->right = x;
    x->parent = y;
}

 

2. 红黑树

linux内核红黑树的算法都定义在


linux-2.6.38.8/include/linux/rbtree.h和linux-2.6.38.8/lib/rbtree.c两个文件中。

2.1 结构体

红黑树和我们以

struct rb_node
{
    unsigned long  rb_parent_color;
#define RB_RED      0
#define RB_BLACK    1
    struct rb_node *rb_right;
    struct rb_node *rb_left;
} __attribute__((aligned(sizeof(long))));

这里的巧妙之处是使用成员rb_parent_color同时存储两种数据,一是其双亲结点的地址,另一是此结点的着色。__attribute__((aligned(sizeof(long))))属性保证了红黑树中的每个结点的首地址都是32位对齐的(在32位机上),也就是说每个结点首地址的bit[1]和bit[0]都是0,因此就可以使用bit[0]来存储结点的颜色属性而不干扰到其双亲结点首地址的存储。

操作rb_parent_color的函数:

#define rb_parent(r)   ((struct rb_node *)((r)->rb_parent_color & ~3))  //获得其双亲结点的首地址
#define rb_color(r)   ((r)->rb_parent_color & 1) //获得颜色属性
#define rb_is_red(r)   (!rb_color(r))   //判断颜色属性是否为红
#define rb_is_black(r) rb_color(r) //判断颜色属性是否为黑
#define rb_set_red(r)  do { (r)->rb_parent_color &= ~1; } while (0)  //设置红色属性
#define rb_set_black(r)  do { (r)->rb_parent_color |= 1; } while (0) //设置黑色属性
 
static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p)  //设置其双亲结点首地址的函数
{
    rb->rb_parent_color = (rb->rb_parent_color & 3) | (unsigned long)p;
}
static inline void rb_set_color(struct rb_node *rb, int color) //设置结点颜色属性的函数
{
    rb->rb_parent_color = (rb->rb_parent_color & ~1) | color;
}
 

初始化新结点:

static inline void rb_link_node(struct rb_node * node, struct rb_node * parent,
                struct rb_node ** rb_link)
{
    node->rb_parent_color = (unsigned long )parent;   //设置其双亲结点的首地址(根结点的双亲结点为NULL),且颜色属性设为黑色
    node->rb_left = node->rb_right = NULL;   //初始化新结点的左右子树
 
    *rb_link = node;  //指向新结点
}
 

指向红黑树根结点的指针:

struct rb_root
{
    struct rb_node *rb_node;
};
 
 
#define RB_ROOT (struct rb_root) { NULL, }  //初始化指向红黑树根结点的指针
#define rb_entry(ptr, type, member) container_of(ptr, type, member) //用来获得包含struct rb_node的结构体的首地址
 
#define RB_EMPTY_ROOT(root) ((root)->rb_node == NULL) //判断树是否为空
#define RB_EMPTY_NODE(node) (rb_parent(node) == node)  //判断node的双亲结点是否为自身
#define RB_CLEAR_NODE(node) (rb_set_parent(node, node)) //设置双亲结点为自身

2.2 插入

首先像二叉查找树一样插入一个新结点,然后根据情况作出相应的调整,以使其满足红黑树的颜色属性(其实质是维持红黑树的平衡)。

函数rb_insert_color使用while循环不断地判断双亲结点是否存在,且颜色属性为红色。

若判断条件为真,则分成两部分执行后续的操作:

(1)、当双亲结点是祖父结点左子树的根时,则:

a、存在叔父结点,且颜色属性为红色。

红黑树底层原理及Linux内核红黑树算法深度研究

 

b、当node是其双亲结点右子树的根时,则左旋,然后执行第c步。

红黑树底层原理及Linux内核红黑树算法深度研究

 

c、当node是其双亲结点左子树的根时。

红黑树底层原理及Linux内核红黑树算法深度研究

 

(2)当双亲结点是祖父结点右子树的根时的操作与第(1)步大致相同,这里略过不谈。

若为假,则始终设置根结点的颜色属性为黑色。

void rb_insert_color(struct rb_node *node, struct rb_root *root)
{
    struct rb_node *parent, *gparent;
 
    while ((parent = rb_parent(node)) && rb_is_red(parent)) //双亲结点不为NULL,且颜色属性为红色
    {
        gparent = rb_parent(parent); //获得祖父结点
 
        if (parent == gparent->rb_left) //双亲结点是祖父结点左子树的根
        {
            {
                register struct rb_node *uncle = gparent->rb_right; //获得叔父结点
                if (uncle && rb_is_red(uncle)) //叔父结点存在,且颜色属性为红色
                {
                    rb_set_black(uncle); //设置叔父结点为黑色
                    rb_set_black(parent); //设置双亲结点为黑色
                    rb_set_red(gparent); //设置祖父结点为红色
                    node = gparent;  //node指向祖父结点 
                    continue; //继续下一个while循环
                }
            }
 
            if (parent->rb_right == node)  //当node是其双亲结点右子树的根时
            {
                register struct rb_node *tmp;
                __rb_rotate_left(parent, root); //左旋
                tmp = parent;  //调整parent和node指针的指向
                parent = node;
                node = tmp;
            }
 
            rb_set_black(parent); //设置双亲结点为黑色
            rb_set_red(gparent); //设置祖父结点为红色
            __rb_rotate_right(gparent, root); //右旋
        } else { // !(parent == gparent->rb_left)
            {
                register struct rb_node *uncle = gparent->rb_left;
                if (uncle && rb_is_red(uncle))
                {
                    rb_set_black(uncle);
                    rb_set_black(parent);
                    rb_set_red(gparent);
                    node = gparent;
                    continue;
                }
            }
 
            if (parent->rb_left == node)
            {
                register struct rb_node *tmp;
                __rb_rotate_right(parent, root);
                tmp = parent;
                parent = node;
                node = tmp;
            }
 
            rb_set_black(parent);
            rb_set_red(gparent);
            __rb_rotate_left(gparent, root);
        } //end if (parent == gparent->rb_left)
    } //end while ((parent = rb_parent(node)) && rb_is_red(parent))
 
    rb_set_black(root->rb_node);
}

 

2.3 删除

像二叉查找树的删除操作一样,首先需要找到所需删除的结点,然后根据该结点左右子树的有无分为三种情形:

红黑树底层原理及Linux内核红黑树算法深度研究

 

若node结点的颜色属性为黑色,则需要调用__rb_erase_color函数来进行调整。

void rb_erase(struct rb_node *node, struct rb_root *root)
{
    struct rb_node *child, *parent;
    int color;
 
    if (!node->rb_left) //删除结点无左子树
        child = node->rb_right;
    else if (!node->rb_right) //删除结点无右子树
        child = node->rb_left;
    else //左右子树都有
    {
        struct rb_node *old = node, *left;
 
        node = node->rb_right;
        while ((left = node->rb_left) != NULL)
            node = left;
 
        if (rb_parent(old)) {
            if (rb_parent(old)->rb_left == old)
                rb_parent(old)->rb_left = node;
            else
                rb_parent(old)->rb_right = node;
        } else
            root->rb_node = node;
 
        child = node->rb_right;
        parent = rb_parent(node);
        color = rb_color(node);
 
        if (parent == old) {
            parent = node;
        } else {
            if (child)
                rb_set_parent(child, parent);
            parent->rb_left = child;
 
            node->rb_right = old->rb_right;
            rb_set_parent(old->rb_right, node);
        }
 
        node->rb_parent_color = old->rb_parent_color;
        node->rb_left = old->rb_left;
        rb_set_parent(old->rb_left, node);
 
        goto color;
    }  //end else
 
    parent = rb_parent(node); //获得删除结点的双亲结点
    color = rb_color(node); //获取删除结点的颜色属性
 
    if (child)
        rb_set_parent(child, parent);
    if (parent)
    {
        if (parent->rb_left == node)
            parent->rb_left = child;
        else
            parent->rb_right = child;
    }
    else
        root->rb_node = child;
 
 color:
    if (color == RB_BLACK) //如果删除结点的颜色属性为黑色,则需调用__rb_erase_color函数来进行调整
        __rb_erase_color(child, parent, root);
}

2.4 遍历

rb_first和rb_next函数可组成中序遍历,即以升序遍历红黑树中的所有结点。

struct rb_node *rb_first(const struct rb_root *root)
{
    struct rb_node  *n;
 
    n = root->rb_node;
    if (!n)
        return NULL;
    while (n->rb_left)
        n = n->rb_left;
    return n;
}
 
struct rb_node *rb_next(const struct rb_node *node)
{
    struct rb_node *parent;
 
    if (rb_parent(node) == node)
        return NULL;
 
    /* If we have a right-hand child, go down and then left as far
       as we can. */
    if (node->rb_right) {
        node = node->rb_right; 
        while (node->rb_left)
            node=node->rb_left;
        return (struct rb_node *)node;
    }
 
    /* No right-hand children.  Everything down and left is
       smaller than us, so any 'next' node must be in the general
       direction of our parent. Go up the tree; any time the
       ancestor is a right-hand child of its parent, keep going
       up. First time it's a left-hand child of its parent, said
       parent is our 'next' node. */
    while ((parent = rb_parent(node)) && node == parent->rb_right)
        node = parent;
 
    return parent;
}
 
声明:本站部分内容来自互联网,如有版权侵犯或其他问题请与我们联系,我们将立即删除或处理。
▍相关推荐
更多资讯 >>>