STL源码剖析——红黑树RB-tree

红黑树与AVL树的比较：

• AVL树的时间复杂度虽然优于红黑树，但是对于现在的计算机，cpu太快，可以忽略性能差异
• 红黑树的插入删除比AVL树更便于控制操作
• 红黑树整体性能略优于AVL树（红黑树旋转情况少于AVL树）

外侧插入与内侧插入

• 1.插入节点位于X的左子节点的左子树——左左
• 2.插入节点位于X的左子节点的右子树——左右
• 3.插入节点位于X的右子节点的左子树——右左
• 4.插入节点位于X的右子节点的右子树——右右
  1、4彼此对称，称为外侧插入，可以采用单旋转操作调整解决
  2、3彼此对称，称为内侧插入，可以采用双旋转操作调整解决

RB-tree(红黑树)

红黑树是一棵二叉搜索树，它在每个节点增加了一个存储位记录节点的颜色，可以是RED,也可以是BLACK；
具体性质如下：

• 每个节点颜色不是黑色，就是红色
• 根节点是黑色的
• 如果一个节点是红色，那么它的两个子节点就是黑色的（没有连续的两红节点）
• 对于每个节点，从该节点到其后代叶节点的简单路径上，均包含相同数目的黑色节点（插入新节点必须为红，如果为黑调节成本太大了）

一颗红黑树的最长路径是红黑节点相间的路径；最短路径是只有黑节点的路径，红黑树又满足每个节点到其后叶子节点的路径上包含的黑节点数相同。顾红黑树保证最长路径不超过最短路径的二倍，因而近似平衡。

插入节点

• 如果插入节点的父亲为黑那么直接插入后返回不需要做任何调整
• 如果插入节点的父亲为红，那么就需要调整了.具体的调整过程可以分为三个情况：

情况一：cur红，parent红，pparent黑，uncle存在为红

• 先将parent和uncle节点变黑，pParent节点变为红（保证该子树中每条路径中黑色节点相同并且没有连续的红节点）
• 再让cur等于pParent节点继续往上继续调整

if (uncle&&uncle->_col == RED)
            {
                pparent->_col = RED;
                parent->_col = uncle->_col = BLACK;
                cur = pparent;
                parent = cur->_parent;
            }

情况二：cur红，parent红，pparent黑，uncle为黑/不存在

外侧插入

parent节点为pparent节点的左孩子，cur节点为parent节点的左孩子，进行右单旋，相反进行左单旋

内侧插入

parent节点为pparent节点的左孩子，cur为parent节点的右孩子，parent节点进行左单旋，相反，parent节点做右单旋

RB-tree结构

插入操作

• insert_unique()：插入节点的键值（key）在整棵树中必须独一无二
• insert_equal()：插入节点的键值（key）在整棵树可以重复

元素搜寻

rb_tree<key,Value,KeyOfValue,Compare,Alloc>::find(consst Key& k)

RB-tree迭代器

SGI将RB-tree迭代器分为两层，图5-16为双层节点结构和双层迭代器结构之间关系。
__rb_tree_node继承自__rb_tree_node_base，__rb_tree_iterator继承自__rb_tree_base_iterator

RB-tree属于双向迭代器，但不具有随机定位能力，其提领操作和成员访问操作与list十分相似，较为特殊是前进和后退操作

RB-tree迭代器的前进操作operator++()调用了基层迭代器的increment()
RB-tree迭代器的前进操作operator–()调用了基层迭代器的decrement()