大家好，关于红黑树时间复杂度很多朋友都还不太明白，不过没关系，因为今天小编就来为大家分享关于红黑树算法的知识点，相信应该可以解决大家的一些困惑和问题，如果碰巧可以解决您的问题，还望关注下本站哦，希望对各位有所帮助！
本文目录
一、红黑树(Red-black tree)
树是一种抽象数据类型，或是实作这种抽象数据类型的数据结构，用来模拟具有树状结构 *** 质的数据 *** 。
红黑树是一种自平衡二叉查找树，典型的用途是实现关联数组，它是复杂的，但它的 *** 作有着良好的最坏情况运行时间,并且在实践中是高效的 O(log n)时间内做查找， *** 和删除，这里的 n是树中元素的数目。
一个由n个节点随机构成的二叉查找树的高度为(log n).证明如下：
而时间复杂度是以某个基础数据 *** 作的重复次数作为量度。红黑树的是二叉搜索树，左子树上所有节点的值均小于他的根节点的值，右子树上所有节点均大于根节点的值，左右子节树相对根节点按大小分布。如果把每次节点值的比较看成基础数据 *** 作，那么最差的查找情况是一直查找到高度更大的根节点，那么查找的时间复杂度即与高度成正比，可表示成 O(log n)。
简单了解了红黑树的字面定义，下面动手感受下红黑树的相关 *** 作。当你 *** 或者删除一个节点时，可能会 *** 红黑树的 *** 质，所以需要对树节点进行重新着色或者旋转，来保持红黑树的结构。首先看下二叉树的旋转。
假设pivot节点不为空，其右子树不为空，那么左旋即是：使pivot的右孩子Y为子树的根，pivot节点为子树根节点的左孩子，pivot左孩子、Y节点的右孩子不改变，Y节点左孩子变为pivot节点右孩子。
假设pivot节点不为空，其左子树不为空，那么右旋：使pivot的左孩子Y为子树的根，pivot节点为子树根节点的右孩子，pivot的右孩子、Y节点的左孩子不变，Y节点的右孩子变为pivot节点的左孩子。
实战演练之增加、删除节点时，如何保证红黑树的 *** 质不被 *** 。
往一个空的红黑树中，依次 *** 数据：12 1 9 2 0 11 7 19 4
节点为根节点，所以为黑色，两个null节点为黑色节点。
按照二叉搜索树的逻辑，9小于12、大于1，应该是1节点的右孩子。但，新增的两个NIL节点已经使得12，1，9，NI这条路径的黑色节点至少为两个，而12，NIL这条路径的黑色节点只有两个。所以要对1节点进行左旋，9节点变为12节点的左孩子，发现问题还是存在。继续，对12节点进行右旋，9节点为根节点，1、12分别为9节点的左右孩子。尝试着色，9节点必须为黑色，而1，12节点可以为红色，也可以为黑色。
0节点直接作为1节点的左孩子，保持跟2节点相同的颜色即可。左右子树依旧保持平衡。
从二叉查找树的 *** 质看，7节点作为2节点的右孩子即可。这时来分析着色问题，我们先看最短路径的黑色分布，9，12，NIL这条路径，有三个黑色节点，以此为参考，尝试改变9节点左子树的着色。目前最长的路径是9，1，2，7，NIL这条路径。保持三个黑色节点的话，9跟NIL已经为黑色节点，而红色节点又不能挨着，所以只能是1为红色节点，2为黑色节点，7为红色节点。那么9，1，0，NIIL这条路径，0就要为黑色节点。调整完毕。
19节点作为12节点的右孩子，与左孩子保持一样的红色即可。
4节点应该作为7节点的左子树，无论着什么颜色，以1节点为根节点的子树，都要 *** 红黑 *** 质。所以应该进行旋转。先以7为根节点进行一次右旋，再以2为根节点进行一次左旋。尝试着色即可。
类似 *** 节点的分析、总结，删除节点也可以针对每种场景找到固定的着色 *** ，就像玩一个游戏，有自己的推理跟玩法。我先做个PPT，这块稍后补充。
所有的 *** 、删除都是有限个情况，基于 *** 、删除的情况分析，即可编写算法生成红黑树，使其在固定的业务场景中发挥红黑树稳定 *** 作效率的特色了。
在计算机科学中， *** L树是更先发明的自平衡二叉查找树。在 *** L树中任何节点的两个子树的高度更大差别为一，所以它也被称为高度平衡树。查找、 *** 和删除在平均和最坏情况下都是 O（log n）。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。
节点的平衡因子是它的左子树的高度减去它的右子树的高度（有时相反）。带有平衡因子1、0或-1的节点被认为是平衡的。带有平衡因子-2或2的节点被认为是不平衡的，并需要重新平衡这个树。平衡因子可以直接存储在每个节点中，或从可能存储在节点中的子树高度计算出来。
不提问题的码农不是好程序员。自己写完了红黑树的简单剖析，感觉还是只懂皮毛，没有从触碰到算法的核心内容。所以，不妨留几个小问题，担心自己脑子生锈或者没事想玩 *** 的时候，再提笔研究下红黑树。
算法的时间复杂度和空间复杂度-总结
二、红黑树比起 *** L树具体更高效在什么地方呢
优化了我的 *** l实现， *** L *** 和删除并不像教科书上说的，需要回溯到根节点，两种情况下可以直接退出向上回溯：
*** 更新时：如果当前节点的高度没有改变，则停止向上回溯父节点。
删除更新时：如果当前节点的高度没有改变，且平衡值在[-1,1]区间则停止回溯。
最终结论，优化过的 *** l和linux的rbtree放在一起， *** l真的和rbtree差不多， *** l也并不总需要回溯到根节点，虽然旋转次数多于rbtree，但是rbtree保持平衡除了旋转外还有重新着色的 *** 作，即便不旋转也在拼命的重新着色，且层数较高，1百万个节点的rbtree层数和1千万个节点的 *** l相同。
所以查询，删除， *** 全部放在一起来看， *** l树和rbtree差不多。
说它不严格是因为它不是严格控制左、右子树高度或节点数之差小于等于1。
但红黑树高度依然是平均log(n)，且最坏情况高度不会超过2log(n)，这有数学证明。所以它算平衡树，只是不严格。不过严格与否并不影响数据结构的复杂度。
不用严格控制高度，使得 *** 效率更高。
显然， *** l树要比红黑树更平衡，因此 *** l树的查找效率更高。
不论是 *** l树还是红黑树，旋转的时间复杂度都是O(1)
对于 *** l树，旋转的时候，需要找到之一个不平衡节点，这就需要我们维护一个平衡因子，每一次 *** ，旋转，删除等 *** 作，都要更新从跟节点到被修改节点这个路径上的平衡因子。。。最差情况下，需要O(lo *** )的时间复杂度。。。
三、顺序查找的时间复杂度
（1）更好情况：要查找的之一个就是。时间复杂度为：O(1)
（2）最坏情况：最后一个是要查找的元素。时间复杂度未：O(n)
（3）平均情况下就是：（n+1）/2。
所以总的来说时间复杂度为：O(n)
2、二分查找：O(log2n)->log以2为底n的对数
3、 *** 值查找：O(log(2)(log(2)n))->log以2为底的（log以2为底的n的对数）的对数
4、斐波那契查找：O(log2n)->log以2为底n的对数
（1）二叉树：O(log2n)~O(n)之间
6、分块查找：O(log2n)~O(n)之间
四、红黑树和二叉树的区别
1、红黑树放弃了追求完全平衡，追求大致平衡，在与平衡二叉树的时间复杂度相差不大的情况下，保证每次 *** 最多只需要三次旋转就能达到平衡，实现起来也更为简单。
2、平衡二叉树追求绝对平衡，条件比较苛刻，实现起来比较麻烦，每次 *** 新节点之后需要旋转的次数不能预知。
五、【老实李】JDK1.8中HashMap的红黑树
上一篇文章 HashMap的底层原理探索我们分析了JDK1.7中Hash *** p的源码实现，但是在JDK1.8的时候HashMap的实现做了很大的变动和优化。1.7和1.7之前HashMap都是“数组+链表”实现的，1.8之后就是“数组+（链表或红黑树）”来实现的了。这里我特地将“链表或红黑树”用一对括号括在一起，因为HashMap底层依旧是一个数组，然后数组中的元素是链表或者红黑树来实现的。
HashMap的实现就先介绍到这，下面就先讲一下红黑树，然后才能理解为什么要用红黑树来优化HashMap，用红黑树有什么好处。
在介绍红黑树之前我们要先理解二叉查找树的数据结构。下面简单介绍一下。
上面这张图就是一个二叉查找树。二叉查找树有如下几条特 ***
（1）.左子树上所有结点的值均小于或等于它的根结点的值。
（2）.右子树上所有结点的值均大于或等于它的根结点的值。
（3）.左、右子树也分别为二叉排序树
那既然他名字中是有“查找”的，那么他是怎么查找的呢？比如我们要查找10这个元素，查找过程为：首先找到根节点，然后根据二叉查找树的之一二条特 *** ，我们知道要查找的10>9所以是在根节点的右边去查找，找到13，10<13,所以接着在13的左边找，找到11,10<11,继续在11的左边查找，这样就找到了10.这其实就是二分查找的思想。最后我们要查出结果所需的更大次数就是二叉树的高度！（二分查找的思想:找到数组的中间位置的元素v，将数组分成>v和<v两部分，然后将v和要查找的数据进行一个比较，如果大于v那么就在>v的部分再次进行二分查找，否则就在<v的部分进行二分查找，直到找到对应的元素。）
那既然要查出结果所需的更大次数就是二叉树的高度，那这个高度会不会有时候很长呢？
比如我们依次 *** 根节点为9如下五个节点：7,6,5,4,3。依照二叉查找树的特 *** ，结果会变成什么样呢？7,6,5,4,3一个比一个小，那么就会成一条直线，也就是成为了线 *** 的查询，时间复杂度变成了O（N）级别。为了解决这种情况，该红黑树出场了。
红黑树其实就是一种自平衡的二叉查找树。他这个自平衡的特 *** 就是对HashMap中链表可能会很长做出的优化。
红黑树是每个节点都带有颜色属 *** 的二叉查找树，颜色或红色或黑色。在二叉查找树强制一般要求以外，对于任何有效的红黑树我们增加了如下的额外要求:
*** 质3每个叶节点（NIL节点，空节点）是黑色的。
*** 质4每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
*** 质5.从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
下面这棵树就是一个典型的红黑树
红黑树那么多规则，那么在 *** 和删除元素会不会 *** 红黑树的规则呢？什么情况下会 *** ？什么情况下不会？
比如我们向原红黑树 *** 为14的新节点就不会 *** 规则
向原红黑树 *** 值为21的新节点就 *** 了规则
那么红黑树是怎么维护这个二叉查找树的自平衡 *** 的呢？
红黑树通过“变色”和“旋转”来维护红黑树的规则，变色就是让黑的变成红的，红的变成黑的，旋转又分为“左旋转”和“右旋转”。这个比较复杂，容易晕，我们就只要知道红黑树就是通过这种方式来实现它的自平衡 *** 就行了。
JDK1.7的时候是使用一个Entry数组来存储数据，用key的hashcode取模来决定key会被放到数组里的位置，如果hashcode相同，或者hashcode取模后的结果相同（hash collision），那么这些key会被 *** 到Entry数组的同一个格子里，这些key会形成一个链表。在hashcode特别差的情况下，比方说所有key的hashcode都相同，这个链表可能会很长，那么put/get *** 作都可能需要遍历这个链表。也就是说时间复杂度在最差情况下会退化到O(n)
红黑树我们大致了解了，他的好处就是他的自平衡 *** ，让他这棵树的更大高度为2log(n+1)，n是树的节点数。那么红黑树的复杂度就只有 O(log n)。
下面我们通过 *** JDK1.8 HashMap的put *** 的源码来理解
通过putVal *** 可以看到这里的数组和1.7不同，是使用了一个Node数组来存储数据。那这个Node和1.7里面的Entry的区别是什么呢？
HashMap中的红黑树节点采用的是TreeNode类
TreeNode和Entry都是Node的子类，也就说Node可能是链表结构，也可能是红黑树结构。
如果 *** 的key的hashcode相同，那么这些key也会被 *** 到Node数组的同一个格子里。如果同一个格子里的key不超过8个，使用链表结构存储。如果超过了8个，那么会调用treeifyBin函数，将链表转换为红黑树。
红黑树时间复杂度的介绍就聊到这里吧，感谢你花时间阅读本站内容，更多关于红黑树算法、红黑树时间复杂度的信息别忘了在本站进行查找哦。
