中企动力网站价格,微信里的小程序怎么删除掉,线上引流线下推广方案,湛江建设厅网站红黑树数据结构剖析红黑树是计算机科学内比较常用的一种数据结构#xff0c;它使得对数据的搜索#xff0c;插入和删除操作都能保持在O(lgn)的时间复杂度。然而#xff0c;相比于一般的数据结构#xff0c;红黑树的实现的难度有所增加。网络上关于红黑树的实现资料汗牛充栋… 红黑树数据结构剖析 红黑树是计算机科学内比较常用的一种数据结构它使得对数据的搜索插入和删除操作都能保持在O(lgn)的时间复杂度。然而相比于一般的数据结构红黑树的实现的难度有所增加。网络上关于红黑树的实现资料汗牛充栋但是乏于系统介绍红黑树实现的资料。本文通过一个自己实现的红黑树数据结构以及必要的搜索插入和删除操作算法为大家更系统地剖析红黑树数据结构的实现。 对于大部分数据结构一般都会使用抽象数据类型的方式实现C提供的模板机制可以做到数据结构与具体数据类型无关就像STL实现的那样。不过本文并非去实现STL中的红黑树更重要的是透过红黑树的实现学习相关的算法和思想。当然我们还是会借鉴STL中关于红黑树实现部分有价值内容。 一、基本概念 在具体实现红黑树之前必须弄清它的基本含义。红黑树本质上是一颗二叉搜索树它满足二叉搜索树的基本性质——即树中的任何节点的值大于它的左子节点且小于它的右子节点。 图1 二叉搜索树 按照二叉搜索树组织数据使得对元素的查找非常快捷。比如图1中的二叉搜索树如果查询值为48的节点只需要遍历4个节点即可完成。理论上一颗平衡的二叉搜索树的任意节点平均查找效率为树的高度h即O(lgn)。但是如果二叉搜索树的失去平衡元素全在一侧搜索效率就退化为O(n)因此二叉搜索树的平衡是搜索效率的关键所在。为了维护树的平衡性数据结构内出现了各种各样的树比如AVL树通过维持任何节点的左右子树的高度差不大于1保持树的平衡而红黑树使用颜色的概念维持树的平衡使二叉搜索树的左右子树的高度差保持在固定的范围。相比于其他二叉搜索树树红黑树对二叉搜索树的平衡性维持有着自身的优势。 顾名思义红黑树的节点是有颜色概念的即非红即黑。通过颜色的约束红黑树维持着二叉搜索树的平衡性。一颗红黑树必须满足以下几点条件 规则1、根节点必须是黑色。 规则2、任意从根到叶子的路径不包含连续的红色节点。 规则3、任意从根到叶子的路径的黑色节点总数相同。 如图2所示为一颗合法的红黑树可以发现红黑树在维持二叉搜索树的基本性质的前提下并满足了红黑树的颜色条件整体上保持了二叉搜索树的平衡性。构造如下红黑树的数据序列为503578275690454048读者可以自行验证。 图2 红黑树 二、数据结构设计 和一般的数据结构设计类似我们用抽象数据类型表示红黑树的节点使用指针保存节点之间的相互关系。 作为红黑树节点其基本属性有节点的颜色、左子节点指针、右子节点指针、父节点指针、节点的值。 图3 红黑树节点基本属性 为了方便红黑树关键算法的实现还定义了一些简单的操作都是内联函数。 //红黑树节点templateclass Tclass rb_tree_node{ typedef rb_tree_node_color node_color; typedef rb_tree_nodeT node_type;public: node_color color;//颜色 node_type*parent;//父节点 node_type*left;//左子节点 node_type*right;//右子节点 T value;//值 rb_tree_node(Tv);//构造函数 inline node_type*brother();//获取兄弟节点 inline bool on_left();//自身是左子节点 inline bool on_right();//自身是右子节点 inline void set_left(node_type*node);//设置左子节点 inline void set_right(node_type*node);//设置左子节点}; 为了表示红黑树节点的颜色我们定义一个简单的枚举类型。 //红黑树节点颜色enum rb_tree_node_color{ redfalse, blacktrue}; 有了节点剩下的就是实现红黑树的构造、插入、搜索、删除等关键算法了。 //红黑树templateclass Tclass rb_tree{public: typedef rb_tree_nodeT node_type; rb_tree(); ~rb_tree(); void clear(); void insert(T v);//添加节点 bool insert_unique(T v);//添加唯一节点 node_type* find(T v);//查询节点 bool remove(T v);//删除节点 inline node_type* maximum();//最大值 inline node_type* minimum();//最小值 inline node_type* next(node_type*node);//下一个节点 inline node_type* prev(node_type*node);//上一个节点 void print();//输出 int height();//高度 unsigned count();//节点数 bool validate();//验证 unsigned get_rotate_times();//获取旋转次数private: node_type*root;//树根 unsigned rotate_times;//旋转的次数 unsigned node_count;//节点数 void __clear(node_type*sub_root);//清除函数 void __insert(node_type*sub_root,node_type*parent,node_type*node);//内部节点插入函数 node_type* __find(node_type*sub_root,T v);//查询 inline node_type* __maximum(node_type*sub_root);//最大值 inline node_type* __minimum(node_type*sub_root);//最小值 void __rebalance(node_type*node);//新插入节点调整平衡 void __fix(node_type*node,node_type*parent,bool direct);//删除节点调整平衡 void __rotate(node_type*node);//自动判断类型旋转 void __rotate_left(node_type*node);//左旋转 void __rotate_right(node_type*node);//右旋转 void __print(node_type*sub_root);//输出 int __height(node_type*sub_root);//高度 bool __validate(node_type*sub_root,int count);//验证红黑树的合法性}; 在红黑树类中定义了树根root和节点数count其中还记录红黑树在插入删除操作时执行的旋转次数rotate_times。其中核心操作有插入操作insert搜索操作find删除操作remove递减操作prev——寻找比当前节点较小的节点递增操作next——寻找比当前节点较大的节点最大值maximum和最小值minimum操作等。其中验证操作__ validate通过递归操作红黑树验证红黑树的三个基本颜色约束用于操纵红黑树后验证红黑树是否保持平衡。 由于插入和删除操作是红黑树的关键所在下边重点介绍这两个操作。其他的操作一般通过对树进行递归操作都可以轻松的完成这里不再赘述。 三、红黑树的插入操作 红黑树的插入操作和查询操作有些类似它按照二分搜索的方式递归寻找插入点。不过这里需要考虑边界条件——当树为空时需要特殊处理这里未采用STL对树根节点实现的特殊技巧。如果插入第一个节点我们直接用树根记录这个节点并设置为黑色否则作递归查找插入__insert操作。 默认插入的节点颜色都是红色因为插入黑色节点会破坏根路径上的黑色节点总数但即使如此也会出现连续红色节点的情况。因此在一般的插入操作之后出现红黑树约束条件不满足的情况称为失去平衡时就必须要根据当前的红黑树的情况做相应的调整__rebalance操作。和AVL树的平衡调整通过旋转操作的实现类似红黑树的调整操作一般都是通过旋转结合节点的变色操作来完成的。 红黑树插入节点操作产生的不平衡来源于当前插入点和父节点的颜色冲突导致的都是红色违反规则2。 图4 插入冲突 如图4所示由于节点插入之前红黑树是平衡的因此可以断定祖父节点g必存在规则1根节点必须是黑色且是黑色规则2不会有连续的红色节点而叔父节点u颜色不确定因此可以把问题分为两大类 1、叔父节点是黑色若是空节点则默认为黑色 这种情况下通过旋转和变色操作可以使红黑树恢复平衡。但是考虑当前节点n和父节点p的位置又分为四种情况 A、n是p左子节点p是g的左子节点。 B、n是p右子节点p是g的右子节点。 C、n是p左子节点p是g的右子节点。 D、n是p右子节点p是g的左子节点。 情况AB统一称为外侧插入CD统一称为内侧插入。之所以这样分类是因为同类的插入方式的解决方式是对称的可以通过镜像的方法相似完成。 首先考虑情况An是p左子节点p是g的左子节点。针对该情况可以通过一次右旋转操作并将p设为黑色g设为红色完成重新平衡。 图5 左外侧插入调整 右旋操作的步骤是将p挂接在g节点原来的位置如果g原是根节点需要考虑边界条件将p的右子树x挂到g的左子节点再把g挂在p的右子节点上完成右旋操作。这里将最终旋转结果的子树的根节点作为旋转轴p节点也就是说旋转轴在旋转结束后称为新子树的根节点这里需要强调一下和STL的旋转操作的区别STL的右旋操作的旋转轴视为旋转之前的子树根节点g节点不过这并不影响旋转操作的效果。 类比之下情况B则需要使用左单旋操作来解决平衡问题方法和情况A类似。 图6 右外侧插入 接下来考虑情况Cn是p左子节点p是g的右子节点。针对该情况通过一次左旋一次右旋操作旋转轴都是n注意不是p并将n设为黑色g设为红色完成重新平衡。 图7 左内侧插入 需要注意的是由于此时新插入的节点是n它的左右子树xy都是空节点但即使如此旋转操作的结果需要将xy新的位置设置正确如果不把p和g的对应分支设置为空节点的话就会破坏树的结构。在之后的其他操作中待旋转的节点n的左右子树可能就不是空节点了。 类比之下情况D则需要使用一次右单旋一次左单旋操作来解决平衡问题方法和情况C类似。 图8 右内侧插入 2、叔父节点是红色 当叔父节点是红色时则不能直接通过上述方式处理了把前边的所有情况的u节点看作红色会发现节点u和g是红色冲突的。但是我们可以交换g与pu节点的颜色完成当前冲突的解决。 图9 叔父节点为红的插入 但是仅仅这样做颜色交换是不够的因为祖父节点g的父节点记作gp如果也是红色的话仍然会有冲突g和gp是连续的红色违反规则2。为了解决这样的冲突我们需要从当前插入点n向根节点root回溯两次。 第一次回溯时处理所有拥有两个红色节点的节点并按照图9中的方式交换父节点g与子节点pu的颜色并暂时忽略gp和p的颜色冲突。如果根节点的两个子节点也是这种情况则在颜色交换完毕后重新将根节点设置为黑色。 第二次回溯专门处理连续的红色节点冲突。由于经过第一遍的处理在新插入点n的路径上一定不存在同为红色的兄弟节点了。而仍出现gp和p的红色冲突时gp的兄弟节点gu可以断定为黑色这样就回归前边讨论的叔父节点为黑色时的情况处理。 图10 消除连续红色节点 由于发生冲突的两个红色节点位置可能是任意的因此会出现上述的四种旋转情况。不过我们把靠近叶子的红色节点g看作新插入的节点这样面对AB情况则把p的父节点gp作为旋转轴旋转后gp会是新子树的根而面对CD情况时把p作为旋转轴即可旋转后p为新子树的根因此可以把四种旋转方式封装起来。 在第二次回溯时虽然每次遇到红色冲突旋转后都会提升g和gp节点的位置与根节点的距离减少但是无论g和gp谁是新子树的根都不会影响新插入节点n到根节点root路径的回溯而且一旦新子树的根到达根节点parent指针为空就可以停止回溯了。 通过以上的树重新平衡策略可以完美地解决红黑树插入节点的平衡问题。 四、红黑树的删除操作 相比于插入操作红黑树的删除操作显得更加复杂。很多资料都没有将红黑树的删除解释清楚清华的数据结构教材对红黑树删除的描述也十分混乱《STL源码剖析》中侯sir对红黑树的删除更是闭口不谈。这里参考了STL对红黑树删除操作的实现方式并做了适当的修改红黑树使用哨兵节点表示空节点而这里使用空指针的方式因此要杜绝空指针的引用问题。 由于红黑树就是二叉搜索树因此节点的删除方式和二叉搜索树相同。不过红黑树删除操作的难点不在于节点的删除而在于删除节点后的调整操作。因此红黑树的删除操作分为两步首先确定被删除节点的位置然后调整红黑树的平衡性。 先考虑删除节点的位置如果待删除节点拥有唯一子节点或没有子节点则将该节点删除并将其子节点或空节点代替自身的位置。如果待删除节点有两个子节点则不能将该节点直接删除。而是从其右子树中选取最小值节点或左子树的最大值节点作为删除节点该节点一定没有两个子节点了否则还能取更小的值。当然在删除被选取的节点之前需要将被选取的节点的数据拷贝到原本需要删除的节点中。选定删除节点位置的情况如图11所示这和二叉搜索树的节点删除完全相同。 图11 删除点的选定 图11中用红色标记的节点表示被选定的真正删除的节点节点y。其中绿色节点yold表示原本需要删除的节点而由于它有两个子节点因此删除y代替它并且删除y之前需要将y的值拷贝到yold注意这里如果是红黑树也不会改变yold的颜色通过上述的方式将所有的节点删除问题简化为独立后继或者无后继的节点删除问题。然后再考虑删除y后的红黑树平衡调整问题。由于删除y节点后y的后继节点n会作为y的父节点p的孩子。因此在进行红黑树平衡调整时n是p的子节点。 下边考虑平衡性调整问题首先考虑被删除节点y的颜色。如果y为红色删除y后不会影响红黑树的平衡性因此不需要做任何调整。如果y为黑色则y所在的路径上的黑色节点总数减少1红黑树失去平衡需要调整。 y为黑色时再考虑节点n的颜色。如果n为红色因为n是y的唯一后继如果把n的颜色设置为黑色那么就能恢复y之前所在路径的黑色节点的总数调整完成。如果n也是黑色则需要按照以下四个步骤来考虑。 设p是n的父节点w为n节点的兄弟节点。假定n是p的左子节点n是p的右子节点情况可以镜像对称考虑。 步骤1若w为红色则断定w的子节点如果存在的话或者为空节点和节点p必是黑色规则2。此时将w与p的颜色交换并以w为旋转轴进行左旋转操作最后将w设定为n的新兄弟节点原来w的左子树x。 通过这样的转换将原本红色的w节点情况转换为黑色w节点情况。若w原本就是黑色或者空节点则直接进入步骤2。 图12 节点删除情况1 步骤2无论步骤1是否得到处理步骤2处理的总是黑色的w节点此时再考虑w的两个子节点xy的颜色情况。如果xy都是黑色节点或者是空节点如果父节点w为空节点认为xy也都是空节点此时将w的颜色设置为红色并将n设定为n的父节点p。此时如果n为红色则直接设定n为黑色调整结束。否则再次回到步骤1做相似的处理。注意节点n发生变化后需要重新设定节点w和p。 考虑由于之前黑色节点删除导致n的路径上黑色节点数减1因此可以把节点n看作拥有双重黑色的节点。通过此步骤将n节点上移使得n与根节点距离减少更极端的情况是当n成为根节点时树就能恢复平衡了因为根节点不在乎多一重黑色。另外在n的上移过程中可能通过后续的转换已经让树恢复平衡了。 图13 节点删除情况2 步骤3如果步骤2中的w的子节点不是全黑色而是左红x红右黑y黑的话将x设置为黑色w设置为红色并以节点x为旋转轴右旋转最后将w设定为n的新兄弟原来的x节点。 通过这样的转换让原本w子节点左红右黑的情况转化为左黑右红的情况。若w的右子节点原本就是红色左子节点颜色可黑可红则直接进入步骤4。 图14 节点删除情况3 步骤4该步骤处理w右子节点y为红色的情况此时w的左子节点x可黑可红。这时将w的右子节点y设置为黑色并交换w与父节点p的颜色w原为黑色p颜色可黑可红再以w为旋转轴左旋转红黑树调整算法结束。 通过该步骤的转换可以彻底解决红黑树的平衡问题该步骤的实质是利用左旋恢复节点n上的黑色节点总数虽然p和w虽然交换了颜色但它们都是n的祖先因此n路径上的黑色节点数增加1。同时由于左旋使得y路径上的黑色节点数减1恰巧的是y的颜色为红将y设置为黑便能恢复y节点路径上黑色节点的总数。 图15 节点删除情况4 总结以上步骤对红黑树节点删除的平衡性调整归纳为如下流程。 图16 节点删除调整流程 通过上述的调整策略可以完美解决红黑树节点删除时平衡性问题。 五、随机测试 对数据结构准确性的测试主要考察以下操作插入删除查询遍历和验证。插入和删除操作前边做了充分的介绍由inset和remove实现查询操作在插入和删除操作时会间接调用由find实现遍历操作分为正序由minimum和next实现和逆序遍历由maximim和prev实现验证操作主要是验证插入和删除后红黑树的合法性规则1、2、3由validate实现。至于其他和红黑树统计特性相关的操作比如获取树高、节点数和累计的旋转次数等可以很容易实现。 我们使用随机数产生器随机产生一批数据插入到红黑树内然后再随机产生一批数据作为删除操作的参数。其中每次插入和删除时都会对树的合法性进行验证并且在插入后删除数据结束后以正序和逆序的方式输出红黑树的节点以及其他统计信息。测试代码如下 #includerb_tree.h#include time.h #include windows.hint main(){ srand((unsigned)GetCurrentTime()); int times10,len30; while(times--) { rb_treeint tree; for(int i0;ilen;i) { int numrand()%len; tree.insert_unique(num); if(!tree.validate())cout插入时失去平衡endl; } cout正序; for(rb_treeint::node_type*nodetree.minimum();node;nodetree.next(node)) { coutnode-value ; } cout\n旋转次数-黑高-节点数tree.get_rotate_times() tree.height() tree.count()endl; cout删除; for(int i0;ilen;i) { int numrand()%len; if(tree.remove(num))coutnum ; if(!tree.validate())cout删除时失去平衡endl; } coutendl; cout逆序; for(rb_treeint::node_type*nodetree.maximum();node;nodetree.prev(node)) { coutnode-value ; } cout\n旋转次数-黑高-节点数tree.get_rotate_times() tree.height() tree.count()endl; cout________________________________________________________________________________endl; } return 0;} 经过大量的循环随机测试可以验证红黑树数据结构的稳定性以及平衡性调整算法的正确性下边是测试结果的部分截图。 本文构造的红黑树数据结构源代码下载地址为https://github.com/fanzhidongyzby/RBTree。 读者感兴趣的话可以下载验证。 图17 测试结果 综上所述我们对红黑树数据结构有了更充分地了解尤其是复杂的红黑树的插入删除平衡性调整算法最后进行的测试验证了红黑树的核心算法的正确性。通过对红黑树数据结构的详尽剖析相信大家对数据结构在计算机学科的重要性有了更充分地认识希望本文对你有所帮助。 转载于:https://www.cnblogs.com/fanzhidongyzby/p/3187912.html
