算法实战：亲自写红黑树之四 插入insert的平衡
本文承接自：
算法实战：亲自写红黑树之一-CSDN博客
算法实战：亲自写红黑树之二 完整代码-CSDN博客
算法实战：亲自写红黑树之三 算法详解-CSDN博客
目录
一、入口
二、普通二叉树插入
三、插入后的平衡
四、算法解惑
一、入口
入口点仿照stl：
//如果second为false则已经存在，发生了覆盖，用GetOldValue获得被覆盖的值pair<iterator, bool> insert(T_DATA const& data){T_COMP comp;return insert(data, comp);}pair<iterator, bool> insert(T_DATA const& data, T_COMP& comp){m_OldValueSeted = false;//清除被覆盖对象的有效标志pair<iterator, bool> ret;ret.first = end();ret.second = false;if (tree_head->free_head < 0 && m_array.Capacity() <= m_array.Size()){thelog << "超出容量限制" << ende;return ret;}try{ret = _insert(data, comp);}catch (exception& e){thelog << e.what() << ende;}//thelog<<"insert ret "<<ret.first.handle<<" "<<ret.second<<endi;return ret;}//返回被覆盖的值，如果最近的操作没有发生覆盖则falsebool GetOldValue(T_DATA& ret)const{if (m_OldValueSeted){ret = m_OldValue;return true;}else{return false;}}
入口点首先处理了需要扩展容量的情形，这个扩展指的是树的删除链表为空，需要从底层数组申请空间的情形。
我的实际应用场景更复杂些，如果底层数组也满了，就会再申请一块共享内存，由于两块共享内存地址地址无法连续，我用了一个地址映射表，从索引到数据要经过查表转换，这就是为什么我必须把底层操作抽象出来的原因。
根据实际需要增加了GetOldValue函数，用来返回被覆盖掉的值。这个功能到底应不应该存在，见仁见智。
T_COMP不理解就无视它，知道默认就是用“<”就可以了。
二、普通二叉树插入
普通插入很简单，由一组“_insert()”函数实现，前导“_”数量不同，表示不同的调用级别。
普通插入后由_RB_insert_Balance(position)函数完成平衡。如果忽略这一句就是普通插入。
如果是覆盖，则只替换数据，树结构不变，不需要平衡。
三、插入后的平衡
代码是比较简单的：
void _RB_insert_Balance(T_SHM_SIZE x){T_SHM_SIZE p = TREE_NODE::at(x).hParent;if (!_isRed(p))return;//连续红，需要调整bool isLeft = (x == TREE_NODE::at(p).hLeft);T_SHM_SIZE g = TREE_NODE::at(p).hParent;bool isL = (p == TREE_NODE::at(g).hLeft);T_SHM_SIZE u = (isL ? TREE_NODE::at(g).hRight : TREE_NODE::at(g).hLeft);if (_isRed(u)){//u为红只需要染色，然后递归TREE_NODE::at(p).bColorRed = false;TREE_NODE::at(u).bColorRed = false;TREE_NODE::at(g).bColorRed = true;_RB_insert_Balance(g);}else{if (isL){if (isLeft){//LL_RRotate(g);_exchage_color(p, g);}else{//LR_LRotate(p);_RRotate(g);_exchage_color(x, g);}}else{if (isLeft){//RL_RRotate(p);_LRotate(g);_exchage_color(x, g);}else{//RR_LRotate(g);_exchage_color(p, g);}}}}
x 插入的新节点
p x的父节点
u x的叔叔，也就是p的兄弟
g x的祖父，也就是p和u的父节点
_isRed(h) 判断节点是不是红色
_LRotate(h) 左旋，只改变父子关系，颜色和数据不变
_RRotate(h) 右旋，只改变父子关系，颜色和数据不变
_exchage_color(h1,h2) 交换两个节点的颜色
四、算法解惑
这个算法的原则其实很简单，不是双红不用处理，是双红则：
- 如果上一层两个都是红，则g必然是黑（红黑树规则），于是就将上一层两个都变成黑、g变成红，于是下面符合规则了，但是g变成了红，可能造成新的双红，于是再对g做平衡。这个过程可能一直递归到顶。
- u是黑，挪一个红过去。具体挪法分四种情形。听起来也不简单？
其实吧，所谓“u是黑”，意思是u是空啊，u不是空的话g左右两边深度就不一样了，违反红黑树规则。所以双红其实就是g下面只有一个红节点，新的节点有挂在了这个红节点下面，也就是“g-红-红”，只需要重新布局，改成g下面一边一个就行了。
而第一种情形的“u是红”呢，就是g下面两个都是红，新的节点又挂在其中一个下面，也就是“g-红红-红”，不可能再有别的黑色数据节点（不是空）存在。
是不是豁然开朗？
（这里是结束）