江苏龙网

  1. 主页 > 生活百科 > >

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

红黑树

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


推荐阅读


上一篇：槐角治痔疮,治痔疮的根治办法

下一篇：菊花什么品种泡茶好,菊花品种十大排行榜