STL关联式容器之RB-tree（红黑树）_中

一个由上而下的程序

    为了避免STL关联式容器之RB-tree（红黑树）_上-CSDN博客中情况4“父子节点皆为红色”的情况，持续向RB-tree的上层结构发展，形成处理时效上的瓶颈，我们可以施行一个由上而下的程序(top-down proceduce):假设新增节点为A，那么就沿着root往A的路径，只要看到有某个节点X的两个子节点皆为红色，就把X改为红色，并把两个子节点改为黑色，如下图所示：

从根节点到新增节点A的路径，如下图所示，使用淡蓝色标识箭头方向：

此时发现了节点50为X节点，将X变为红色，并将X的两个子节点变为黑色；如下图所示：

此时把X子树当做新插入的节点，沿着PG进行一次旋转，并修改PG颜色如下图所示：

经过转换后，新插入的节点35的父节点已经为黑色，不需要进行调整，只需直接插入即可。

RB-tree的节点设计

    RB-tree有红黑二色，并且拥有左右子节点，我们很容易就可以勾勒出其节点风貌。下面是SGI STL的实现源码。为了有更大的弹性，节点分为两层，稍后将显示节点双层结构和迭代器双层结构的关系。

    从以下的minimum()和maximum()函数可清楚看出，RB-tree作为一个二叉搜索树，其极值是很容易找到的。由于RB-tree的各种操作时常需要上溯其父节点，所以特别再数据结构中安排了一个parent指针。

typedef bool __rb_tree_color_type;
const __rb_tree_color_type _rb_tree_red = false;  //红色为0
const __rb_tree_color_type _rb_tree_black = true; //黑色为1

struct __rb_tree_node_base {
    typedef __rb_tree_color_type color_type;
    typedef __rb_tree_node_base* base_ptr;

    color_type color;
    base_ptr parent;
    base_ptr left;
    base_ptr right;
};

static base_ptr minimum(base_ptr x) {
    while(x->left !=0) x = x->left;
    return x;
}

static base_ptr maximum(base_ptr x) {
    while(x->right !=0) x = x->right;
    return x;
}

template <class Value>
struct __rb_tree_node : public __rb_tree_node_base {
    typedef __rb_tree_node<Value>* link_type;
    Value value_field;    
};

下面是RB-tree节点是以图，value_field填17

RB-tree的迭代器

    要成功地将RB-tree实现为一个泛型容器，迭代器的设计是一个关键。首先要考虑它的类别(category),然后要考虑它的前进(increment),后退（decrement）,提领(dereference),成员访问(member access)等操作。

    为了更大的弹性，SGI将RB-tree迭代器实现为两层，这种设计理念和STL序列式容器之slist-CSDN博客 中的slist类似。下图所示便是双层节点结构和双层迭代器结构之间的关系，其中主要意义是:__rb_tree_node继承自__rb_tree_node_base,__rb_tree_iterator继承自__rb_tree_base_iterator.

    RB-tree迭代器属于双向迭代器，但不具备随机定位能力，其提领操作和成员访问与list十分相近似，较为特殊的是前进和后退操作。注意，TB-tree迭代器的前进操作operator++()调用了基层迭代器的increment(),RB-tree迭代器的后退操作operator--()则调用了基层迭代器的decrement().前进或后退的举止行为完全依据二叉搜索树的节点摆列法则，再加上实现上的特殊技巧。我加注这两个函数内的说明，适足以说明其操作原则。至于实现上的特殊技巧(针对根节点)，稍后另有说明。

//基层迭代器
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;  // 它用来与容器之间产生一个连结关系
    
    // 以下起始课实现与operator++内，因为再无他处会调用此函数
    void increment() {
        if (node->right != 0) {        // 如果有右子节点。状况1
            node = node->right;        // 往右走   
            while (node->left != 0)    // 然后一直往左子树走到底
                node = node->left      // 即是解答
        }
        else {                         // 没有右子节点，状况2
            base_ptr y = node->parent; // 找出父节点
            while (node == y->right) {
                node = y;
                y = y->parent;
            }

            if (node->right != y) 
                node = y                // 状况4，特殊情况后续会说明什么时候会满足
        }

    }

    // 以下起始课实现与operator--内，因为再无他处会调用此函数了
    void decrement() {
        if （node->color == rb_tree_red &&    // 如果是红节点
            node->parent->parent == node) {    // 父节点的父节点等于自己（状况1不知什么时候能满足）
        node = node->right;
        }
        else if (node->left != 0) {
            base_ptr y = node->left;            // 指向左节点后
            while(y->right != 0)                // 一直朝右走 
                y = y.right;
            node = y;
        }  else {
           base_ptr y = node->parent;
           while (node == y->left) {
               node = y;
               y = y->parent;
            }
            node = y;
        
        }

    }
};

RB-tree的迭代器

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_field;}
    #ifndef __SGI_STL_NO_ARROW_OPERATOR
    pointer operator->() const {return &(operator*());}
    #endif

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

在increment()及decrement()两函数中，较令人费解的是前者的状况4和后者的状况1，它们发生如下图所示。

图中带空心箭头的方向表示父节点。

对于end()节点，它的left是树的最左边的节点，亦即begin(),同事end()的颜色为红色，同时end()的parent为根节点，同时根节点的parent为end(); 所以才会出现node->parent->parent==node的情况出现；对于end()节点++，还是end()节点，所以才会有increment()中，node->right!=y的判断。对于end()--则认为需要回到begin(),正好是decrement函数中的条件1。