SGI STL的rb_tree淺析

rb_tree是一種特殊的平衡二叉搜尋樹，但是其對平衡的要求比avl_tree低，avl_tree要求左右子樹的高度差不能大于1，而rb_tree隻要求從一個節點至樹的尾端的任何路徑的黑節點的個數相等

rb_tree必須滿足的規則：

1.每個節點不是黑色就是紅色;

2.根節點必須為黑色；

3.若節點為紅色，則其子節點必須為黑色（紅不連）；

4.任意節點至樹尾端的任何路徑的黑色節點的個數必須相等；

總結一下，也就是——>一頭一腳黑，黑同紅不連

為何要用rb_tree, avl_tree：

rb_tree, avl_tree都可以實作平衡二叉搜尋樹，它們都比一般的（無法絕對維持平衡的）二叉搜尋樹複雜，是以其插入和删除節點的平均時間也比較長但是它們可以避免極難處理的高度不平衡情況，因為它們總是維持着某種平衡（即每插入一個節點就會判斷樹是否平衡，不平衡就調整），是以其元素的通路（搜尋）時間平均來說比較少.

rb_tree的節點設計—->rb_tree節點設計分兩層，node_base和node,node_base主要負責紅黑樹的連接配接部分 (parent,left,right)，而node負責紅黑樹的資料部分(value_filed節點值)

struct __rb_tree_node_base
{
    typedef __rb_tree_color_type color_type;     //節點顔色
    typedef __rb_tree_node_base* base_ptr;       //父節點指針

    //rb樹的父節點的成員
    color_type  color;   //顔色
    base_ptr    parent;   //父節點指針
    base_ptr    left;    //左樹
    base_ptr    right;   //右樹

    //最小節點
    static base_ptr minimum(base_ptr x)
    {
        while(x->left != ){
            x = x->left;
        }
        return x;
    }

    //最大節點
    static base_ptr maximum(base_ptr x)
    {
        while(x->right != ){
            x = x->right;
        }
        return x;
    }
};

//rb樹的節點
template<class Value>
struct __rb_tree_node : public __rb_tree_node_base
{
    typedef __rb_tree_node<Value>* link_type;   //rb樹的節點指針
    Value value_filed;    //rb樹的節點的值
};

rb_tree的疊代器設計—>rb_tree的疊代器也設計為兩層，base_iterator和iterator

//rb樹的疊代器

struct __rb_tree_base_iterator
{
    typedef __rb_tree_node_base::base_ptr base_ptr;
    typedef bidirectional_iterator_tag iterator_category;
    typedef ptrdiff_t difference_type;
    base_ptr node;

    //指向下一個節點（++操作）
    void increment()
    {
        if(node->right != ){   //若目前節點的右樹不空，則其直接前驅就在其右樹部分
            node = node->right;   //在node的右樹中找出最左的節點就是node的直接前驅
            while(node->left != ){
                node = node->left;
            }
        }else{    //node的右樹為空，則進行上溯查找node的父節點，直到找到node的直接前驅
            base_ptr y = node->parent;
            while(node == y->right){
                node = y;
                y = y->parent;
            }

            if(node->right != y){
                node = y;
            }
        }
    }

    //指向上一個節點（--操作）
    void decrement()
    {
        if(node->color == __rb_tree_red && node->parent->parent == node){  //node為header
            node = node->right;
        }else if(node->left != ){   //若node的左樹不為空，就在左樹中找到最右側的節點
            base_ptr y = node->left;
            while(y->right != ){
                y = y->right;
            }

            node = y;
        }else{    //node的左樹為空，則上溯，查找node的父節點，找到node的直接前驅
            base_ptr y = node->parent;
            while(node == y->left){
                node = y;
                y = y->parent;
            }

            node = y;
        }
    }
};

template<class Value, class Ref, class Ptr>
struct __rb_tree_iterator : public __rb_tree_base_iterator
{
    typedef Value value_type;
    typedef Ref reference;
    typedef Ptr pointer;
    typedef __rb_tree_iterator<Value, Value& , Value*>    iterator;
    typedef __rb_tree_iterator<Value, const Value&, const Value*> const_iterator;

    typedef __rb_tree_iterator<Value, Ref, Ptr>   self;
    typedef __rb_tree_node<Value>*   link_type;

    __rb_tree_iterator()
    {
    }
    __rb_tree_iterator(link_type x)
    {
        node = x;
    }
    __rb_tree_iterator(const iterator& it)
    {
        node = it.node;
    }

    reference operator*()const
    {
        return link_type(node)->value_filed;
    }
    pointer operator->()const
    {
        return &(operator*());
    }

    self& operator++()
    {
        increment();
        return *this;
    }
    self operator++(int)
    {
        self tmp = *this;
        increment();
        return tmp;
    }

    self& operator--()
    {
        decrement();
        return *this;
    }
    self operator--(int)
    {
        self tmp = *this;
        decrement();
        return tmp;
    }
};

rb_tree的無論是節點還是疊代器都是以struct定義的原因是： struct的所有成員都是public，是以其所有成員都可被外界自由取用

rb_tree的實作使用了一個技巧，那就是使用了header

rb_tree的資料結構

//rb樹
template<class Key, class Value, class KeyOfValue, class Compare, class Alloc = alloc>
class rb_tree{
protected:
    typedef void* void_pointer;
    typedef __rb_tree_node_base* base_ptr;   //rb樹的父節點指針
    typedef __rb_tree_node<Value> rb_tree_node;   //rb樹的節點
    typedef simple_alloc<rb_tree_node, Alloc> rb_tree_node_allocator;   //以節點的大小為配置機關
    typedef __rb_tree_color_type color_type;   //rb樹的節點的顔色

public:
    typedef Key key_type;
    typedef Value value_type;
    typedef value_type* pointer;
    typedef const value_type* const_pointer;
    typedef value_type& reference;
    typedef const value_type& const_reference;
    typedef rb_tree_node* link_type;    //rb樹的節點指針
    typedef size_t size_type;
    typedef ptrdiff_t difference_type;

protected:
    link_type get_node()
    {
        return rb_tree_node_allocator::allocate();
    }

    link_type create_node(const value_type& x)
    {
        link_type tmp = get_node();
        construct(&tmp->value_filed, x);
        return tmp;
    }

    link_type clone_node(link_type x)
    {
        link_type tmp = create_node(x->value_filed);
        tmp->color = x->color;
        tmp->left = ;
        tmp->right = ;

        return tmp;
    }

    void destroy_node(link_type p)
    {
        destroy(&p->value_filed);
        put_node(p);
    }

protected:
    size_type node_count;   //rb樹的節個數
    link_type header;       //rb樹的頭指針,相當于連結清單的第一個空節點
    Compare key_compare;    

protected:
    link_type& root()const
    {
        return (link_type&)header->parent;
    }
    link_type& leftmost()const
    {
        return (link_type&)header->left;
    }
    link_type& rightmost()const
    {
        return (link_type&)header->right;
    }


protected:
    static link_type& left(link_type x)
    {
        return (link_type&)(x->left);
    }
    static link_type& right(link_type x)
    {
        return (link_type&)(x->right);
    }
    static link_type& parent(link_type x)
    {
        return (link_type&)(x->parent);
    }
    static reference value(link_type x)
    {
        return x->value_filed;
    }
    static const Key& key(link_type x)
    {
        return KeyOfValue()(value(x));
    }
    static color_type& color(link_type x)
    {
        return (color_type&)(x->color);
    }


    static link_type& left(base_ptr x)
    {
        return (link_type&)(x->left);
    }
    static link_type& right(base_ptr x)
    {
        return (link_type&)(x->right);
    }
    static link_type& parent(base_ptr x)
    {
        return (link_type&)(x->parent);
    }
    static reference value(base_ptr x)
    {
        return ((link_type)x)->value_filed;
    }
    static const Key& key(base_ptr x)
    {
        return KeyOfValue()(value(link_type(x)));
    }
    static color_type& color(base_ptr x)
    {
        return (color_type&)(link_type(x)->color);
    }

    static link_type minimum(link_type x)
    {
        return (link_type) __rb_tree_node_base::minimum(x);
    }
    static link_type maximum(link_type x)
    {
        return (link_type) __rb_tree_node_base::maximum(x);
    }

public:
    typedef __rb_tree_iterator<value_type, reference, pointer> iterator;
    typedef __rb_tree_iterator<value_type, const_reference, const_pointer> const_iterator;

private:
    void init()
    {
        header = get_node();    //配置一個節點
        color(header) = __rb_tree_red;   //将header節點設為紅色

        root() = ; //将header的父節點賦空
        leftmost() = header;   //将header指向最左的節點
        rightmost() = header;  //将header指向最右的節點
    }

public:
    rb_tree(const Compare& comp = Compare()) : node_count(), key_compare(comp)
    {
        init();   //生成一個空節點header
    }

public:
    iterator begin()
    {
        return leftmost();
    }
    iterator end()
    {
        return header;
    }

public:
    pair<iterator, bool> insert_unique(const value_type& x);

protected:
    iterator __insert(base_ptr x_, base_ptr y_, const Value& v);
};

紅黑樹的插入：根據插入的節點的位置，以及其外圍節點（s伯父節點，GG曾祖父節點）的顔色，會出現以下四種狀況：

（先作以下假設：假設x為新插入的節點，p為其父節點，G為其祖父節點，S為其伯父節點，GG為其曾祖父節點）

狀況一：

S為黑色并且x為外側插入，此時要先對P, G作一次單旋轉，再更改P，G的顔色，就可滿足紅黑樹的規則。

SGI STL的rb_tree淺析
狀況二： S為黑色并且x為内側插入；要先對P，X作一次單旋轉，再更改G，X的顔色，最後将所得結果再對G作一次單旋轉，就可以滿足紅黑樹的規則。

SGI STL的rb_tree淺析

狀況三：S為紅色并且X為外側插入；先對P，G作一次單旋轉，再改變X

的顔色，若此時的GG為黑色，則樹是平衡的，若不是，則要繼續上溯，判斷樹的平衡性并調整。

SGI STL的rb_tree淺析
狀況四：S為紅色并且X為内側插入；先對P，G作一次單選裝，改變X的顔色，此時若GG為紅色，就要繼續往根的方向走，直到不在有父子節點連續為紅色的狀況。

SGI STL的rb_tree淺析

紅黑樹的插入操作：

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)
{
    link_type y = header;
    link_type x = root();   //從根開始
    bool comp = true;

    //從根開始查找，得到插入節點的位置
    while(x != ){
        y = x;
        comp = key_compare(KeyOfValue()(v), key(x));    //比較大小，若v小于x則comp為true
        x = comp ? left(x) : right(x);    //comp為true則x要插入左樹，fouze是右樹
    }
    //while結束，y就是要插入節點的父節點，此時y必為葉子節點

    iterator j = iterator(y);   //疊代器j指向插入節點的父節點
    if(comp){   //while結束，若comp為true，則在左側插入
        if(j == begin()){   //若插入點的父節點為最左側的節點
            //x為插入點，y為插入點的父節點，v要插入的值
            return pair<iterator, bool>(__insert(x, y, v), true);
        }else{   //插入點的父節點不為最左節點
            --j; //回溯判斷插入的新值是否符合該樹的目前節點沒有和其值一樣的，因Comp用的是判斷小于，是以有可能相等
        }
    }

    if(key_compare(key(j.node), KeyOfValue()(v))){   //若j所指的節點的值小于v，則在右側插入
        //x為插入點，y為插入點的父節點，v要插入的值
        return pair<iterator, bool>(__insert(x, y, v), true);   
    }

    //此時，說明新值x與樹中的健值重複，不進行插入
    return pair<iterator, bool>(j, false);
}




template<class Key, class Value, class KeyOfValue, class Compare, class Alloc>
typename rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::iterator
rb_tree<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;

    if(y == header || x !=  ||key_compare(KeyOfValue()(v), key(y))){
        z = create_node(v);   //配置一個新節點，z就成為要插入的節點
        left(y) = z;     //若y==header時，leftmost() = z
        if(y == header){   //若y為header空節點，則z就為根結點，也為最右節點
            root() = z;
            rightmost() = z;
        }else if(y == leftmost()){   //若y為最左節點，則新插入的節點就變成最左節點
            leftmost() = z;
        }
    }else{
        z = create_node(v);    //配置一個節點z
        right(y) = z;          //使z成為插入點x的父節點y的右節點
        if(y == rightmost()){   //若y為最右節點，則z就是新的最右節點
            rightmost() = z;
        }
    }

    //調整z的父節點和z的左右節點
    parent(z) = y;
    left(z) = ;
    right(z) = ;
    __rb_tree_rebalance(z, header->parent);  //調整z節點一直上溯到根結點的平衡
    ++node_count;     //節點數增加
    return iterator(z);   //傳回一個疊代器，指向新增節點
}

插入節點所需的調整平衡的函數

//x為新插入節點，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為x的叔伯節點
            if(y && y->color == __rb_tree_red){  //伯父節點存在，并且伯父節點為紅色
                x->parent->color = __rb_tree_black;    //将x的父節點變黑色
                y->color = __rb_tree_black;     //将x的伯父節點變為黑色
                x->parent->parent->color = __rb_tree_red;  //将x的祖父節點變為紅色，此時要上溯檢視其曾祖父節點的顔色，若為紅則不平衡要調整
                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為x的伯父節點
            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);
            }
        }
    }
    //将根結點的顔色置為黑色
    root->color = __rb_tree_black;
}


//左旋
inline void __rb_tree_rotate_left(__rb_tree_node_base* x, __rb_tree_node_base*& root)
{
    __rb_tree_node_base* y = x->right;   //y為旋轉點x的右節點
    x->right = y->left;     //左旋要将x的右節點的左樹挂接到y的右樹部分
    if(y->left != ){
        y->left->parent = x;  //改變y的左樹的父節點指向
    }
    y->parent = x->parent;   //改變y的父節點

    //對x和y作旋轉
    if(x == root){   //若新插入的節點為根結點，則讓x的右節點y作根結點
        root = y;
    }else if(x == x->parent->left){  //若x是其父節點的左節點，則讓x的右節點y作其父節點的左節點
        x->parent->left = y;
    }else{  //x是其父節點的右節點，則讓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)
{
    __rb_tree_node_base* y = x->left;   //y為x的左節點
    x->left = y->right;   //将x旋轉下來，y旋轉上去，将y的右節點給予x的左節點

    if(y->right != ){  //若y的右節點不空，更改其父節點指向
        y->right->parent = x;
    }
    y->parent = x->parent;   //更改y的父節點

    //對x和y進行旋轉
    if(x == root){
        root = y;
    }else if(x == x->parent->right){
        x->parent->right = y;
    }else{
        x->parent->left = y;
    }

    y->right = x;
    x->parent = y;
}

SGI STL的rb_tree淺析

繼續閱讀

GlobalMapper20把地形資料（tif）轉為可列印的STL格式模型一、為什麼要把地形轉為stl？二、轉換流程

HDU 5199 Gunner

gdb腳本 - 檢視stl變量

<Effectives STL>筆記之在STL容器中删除元素的方法選擇

C++ STL基本容器比較

STL--vector容器STL—vector容器

STL相關

【CF 125D】 Two progressions 劃分等差數列

STL六大元件以及互相關系

STL 六大元件概要

初識 STL

STL——deque 雙向隊列

c++中指針的指針和指針的引用的使用

pat（B）1009. 說反話（逆疊代器）

C++ heap學習

PAT (Top Level) Practise 1007 Red-black Tree (35)