算法实战：亲自写红黑树之四 插入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) 交换两个节点的颜色

四、算法解惑

        这个算法的原则其实很简单，不是双红不用处理，是双红则：

1. 如果上一层两个都是红，则g必然是黑（红黑树规则），于是就将上一层两个都变成黑、g变成红，于是下面符合规则了，但是g变成了红，可能造成新的双红，于是再对g做平衡。这个过程可能一直递归到顶。
2. u是黑，挪一个红过去。具体挪法分四种情形。听起来也不简单？

        其实吧，所谓“u是黑”，意思是u是空啊，u不是空的话g左右两边深度就不一样了，违反红黑树规则。所以双红其实就是g下面只有一个红节点，新的节点有挂在了这个红节点下面，也就是“g-红-红”，只需要重新布局，改成g下面一边一个就行了。

        而第一种情形的“u是红”呢，就是g下面两个都是红，新的节点又挂在其中一个下面，也就是“g-红红-红”，不可能再有别的黑色数据节点（不是空）存在。

        是不是豁然开朗？

（这里是结束）