如何搜名字搜到自己做的网站,电商网红排行榜,长春seo培训,域名备案时网站名字本文承接自#xff1a; 算法实战#xff1a;亲自写红黑树之一-CSDN博客 算法实战#xff1a;亲自写红黑树之二 完整代码-CSDN博客 算法实战#xff1a;亲自写红黑树之三 算法详解-CSDN博客 目录
一、入口
二、普通二叉树插入
三、插入后的平衡
四、算法解惑 一、入口 入… 本文承接自 算法实战亲自写红黑树之一-CSDN博客 算法实战亲自写红黑树之二 完整代码-CSDN博客 算法实战亲自写红黑树之三 算法详解-CSDN博客 目录
一、入口
二、普通二叉树插入
三、插入后的平衡
四、算法解惑 一、入口 入口点仿照stl //如果second为false则已经存在发生了覆盖用GetOldValue获得被覆盖的值pairiterator, bool insert(T_DATA const data){T_COMP comp;return insert(data, comp);}pairiterator, bool insert(T_DATA const data, T_COMP comp){m_OldValueSeted false;//清除被覆盖对象的有效标志pairiterator, 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;}//theloginsert ret ret.first.handle ret.secondendi;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-红红-红”不可能再有别的黑色数据节点不是空存在。 是不是豁然开朗 这里是结束
