怎样做好外贸网站推广,网络营销推广哪家比较好,创意营销新点子,如何搭建微商城红黑树#xff0c;对很多童鞋来说#xff0c;是既熟悉又陌生。熟悉是因为在校学习期间#xff0c;准备面试时#xff0c;这是重点。然后经过多年的荒废#xff0c;如今已经忘记的差不多了。如果正在看文章的你#xff0c;马上快要毕业#xff0c;面临着找工作的压力对很多童鞋来说是既熟悉又陌生。熟悉是因为在校学习期间准备面试时这是重点。然后经过多年的荒废如今已经忘记的差不多了。如果正在看文章的你马上快要毕业面临着找工作的压力又或者你觉得需要将这块知识重新复习一遍又或者只是看看那么恭喜你赚到了。那么我将带领大家重新认识下红黑树用简单的语言搞懂红黑树。在学习红黑树之前咱们需要先来理解下二叉查找树BST。要想了解二叉查找树我们首先看下二叉查找树有哪些特性呢1 左子树上所有的节点的值均小于或等于他的根节点的值2 右子数上所有的节点的值均大于或等于他的根节点的值3 左右子树也一定分别为二叉排序树我们来看下图的这棵树他就是典型的二叉查找树那问题来了为什么一定要这种结构呢换句话说这样的结构有什么好处呢我们就来查找下值为10的节点。它怎么一步步的找到这个节点的步骤是怎样的接着往下看。1 查找到根节点9看下图2 由于10大于9的所以查找到右孩子13看下图3 又因为10是小与13的所以查找到左孩子11看下图4 这一步相比不用说了大家也都知道了找到了左孩子然后发现正好是10 。恰好是正要寻找的值。可能又有童鞋会问这不是二分查找的思想吗确实查找所需的最大次数等同于二叉查找树的高度。当然在插入节点的时候也是这种思想一层一层的找到合适的位置插入。但是二叉查找树有个比较大的缺陷而且这个缺陷会影响到他的性能。我们先来看下有一种情况的插入操作如果初始的二叉查找树只有三个节点如下图我们依次插入5个节点76,5,4,3,。看下图插入之后的图看出来了吗有没有觉得很别扭如果根节点足够大那是不是“左腿”会变的特别长也就是说查找的性能大打折扣几乎就是线性查找了。那有没有好的办法解决这个问题呢解决这种多次插入新节点而导致的不平衡这个时候红黑树就登场了。红黑树就是一种平衡的二叉查找树说他平衡的意思是他不会变成“瘸子”左腿特别长或者右腿特别长。除了符合二叉查找树的特性之外还具体下列的特性1. 节点是红色或者黑色2. 根节点是黑色3. 每个叶子的节点都是黑色的空节点NULL4. 每个红色节点的两个子节点都是黑色的。5. 从任意节点到其每个叶子的所有路径都包含相同的黑色节点。看下图就是一个典型的红黑树很多童鞋又会惊讶了天啊这个条条框框也太多了吧。没错正式因为这些规则才能保证红黑树的自平衡。最长路径不超过最短路径的2倍。当插入和删除节点就会对平衡造成破坏这时候需要对树进行调整从而重新达到平衡。那什么情况下会破坏红黑树的规则呢1我们看下图向原来的红黑树插入值为14的新节点由于父节点15是黑色节点所以这种情况没有破坏结构不需要做任何的改变。2向原树插入21呢看下图由于父节点22是红色节点因此这种情况打破了红黑树的规则4必须作出调整。那么究竟该怎么调整呢有两种方式【变色】和【旋转】分为【左旋转】和【右旋转】。【变色】为了符合红黑树的规则会把节点红变黑或者黑变红。下图展示的是红黑树的部分需要注意节点25并非根节点。因为21和22链接出现红色不符合规则4所以把22红变黑但这样还是不符合规则5所以需要把25黑变红看下图你以为现在结束了天真因为25和27又是两个连续的红色节点(规则4)所以需要将27红变黑。终于结束了都满足规则了舒服多了。【左旋转】也就是逆时针旋转两个节点使父节点被自己的右孩子取代而自己成为自己的左孩子听起来吓死人直接看图吧【右旋转】顺时针旋转两个节点使得自己的父节点被左孩子取代而自己成为自己的右孩子看不懂直接看图吧看起来这么复杂到底怎么用呢确实很复杂我们讲下典型的例子大家参考下以刚才插入21节点的例子首先我们需要做的是变色把节点25以及下方的节点变色由于17和25是连续的两个红色节点那么吧节点17变黑吗这样是不行的你想这样一来不就打破了规则4了吗而且根据规则2也不可能吧13变成红色。变色已经无法解决问题了所以只能进行旋转了。13当成X17当成Y左旋转试试看由于根节点必须是黑色所以需要变色结果如下图继续其中有两条路径17-8-6-NULL的黑色节点个数不是3是4不符合规则。这个时候需要把13当做X8当做Y进行右旋转最后根据规则变色这样一来我们终于结束了经过调整之后符合规则。那我们费这么大力气这么复杂这东西用在哪里有哪些应用呢其实STL中的map就是用的红黑树。转自www.360doc.com总结红黑色的大体思想就是上面描述的那样里面还有很多情况要考虑本文只是简单的讲述思想大家有兴趣可以去百度上看各种情况的考虑。谢谢大家的支持扫码或长按关注回复「 加群 」进入技术群聊
