江苏龙网

  1. 主页 > 生活百科 > >

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

红黑树


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

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

文章插图
 
【红黑树底层原理及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);  // 返回一个迭代器，指向新增节点}  // 全局函数// 重新令树形平衡（改变颜色及旋转树形）// 参数一为新增节点，参数二为根节点rootinline 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;}


推荐阅读


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

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