红黑树的性质以及时间复杂度证明 很久就想写一篇红黑树的博客，一直没有倒出时间，今天想稍微的总结下红黑树，但是并不想介绍如何的进行插入删除，以及怎么进行旋转，变色，本编文章主要讲解红黑树的时间复杂度的证明，要想证明红黑树的时间复杂度，我们先得说说两件事，红黑树的性质和数学归纳法： 1.红黑树的性质有哪些，有了这些性质，我们才能后面进行证明 先来一张红黑树的图片，便于后期进行对红黑树进行分析： 
先说下红黑树的性质： Every node is either red or black.The root is black.Every leaf (null) is black.If a node is red, then both its children are black.For each node, all simple paths from the node to descendant leaves contain the same number of black nodes. 中文意思是： 每个节点要么是红色，要么是黑色；根节点永远是黑色的；所有的叶节点都是是黑色的（注意这里说叶子节点其实是上图中的 null 节点,而我们真正写代码的时候，是不会特意建立一个空结点的，而是将指针设置为空就ok 了）；每个红色节点的两个子节点一定都是黑色；（红色结点要不没有黑色孩子，要么就有两个黑色孩子，这里的孩子不包括null叶子结点）从任一节点到其子树中每个叶子节点的路径都包含相同数量的黑色节点； 这里稍微解释下，只要是满足这5个要求的就是，红黑树，所以理论上红黑树，可以全是黑色， 那么如果全是黑色，就应该是一个满二叉树，如下图所示： 
这里再强调下性质4和性质5的作用： 性质4:每个红色节点的两个子节点一定都是黑色 “不能连续出现红节点”规定了，红色节点数量至多是（黑色节点数量-1），如果不考虑叶子节点，那么任一路径上红色节点数量至多等于黑色节点数量。 性质5:从任一节点到其子树中每个叶子节点的路径都包含相同数量的黑色节点，（一般我们直接说成是跟根结点，因为根结点都相同了，那么任意一个结点肯定也相同了）规定了，单看黑色节点这个树是平衡的。 结合性质4和5:我们得出这样的结论： 红黑树中任一节点的左右子树的高差最多两倍关系。 如下图，我画了一颗红黑树，根结点的左子树是右子树高度的两倍（根的左子树高度为4，右子树高度为2，这里高度没有计算null结点或者这里叫叶子结点）。 图中为了看着方便，没有画出叶子结点： 
2.数学归纳法，说说数学归纳法的证明思路，后面要用到。 数学归纳法的过程分为两部分： （1）先证明n=1时命题成立，在实际操作中，把n=1代进去就行了，就像要你证明“当n=1时1+n=2成立” （2）假设n=k时命题成立，证明n=k+1时命题成立 你可以这样理解：第一部分证明n=1成立。绝大部分命题，n取任意非零自然数都成立，既然这样，先证最基本的n=1吧。 第二部分，既然当n=k成立时，n=k+1成立，那么，n=1已经证明成立了，n=1+1，也就是n=2时也会成立。n=2成立，按照惯例n=2+1，也就是n=3成立。按照惯例，n=3+1，n=4+1……都会成立，所以所有的自然数都能使命题成立。 你可以把第一部分当作一个坚实的基础，既然n取任意自然数成立（大部分命题是如此），那么n=1成立是理所当然的。第二部分是一个骨牌的过程，1证明2，2证明3，3证明4……证明所有非0自然数。 两部分我们都说完了，那么我们就言归正传，开始证明红黑树的时间复杂度： 证明红黑树的概念的时候，需要用到一些名词： 1、空结点，即值为NULL的结点， 2、内部结点，除了叶子结点的所有结点。 3、亲子结点，跟某一根结点，直接相连接的两个结点，称作亲子结点。 4、h(x)，即树的高度 5、bh(x) , 全称是Black Height(x) ，是指结点x所在的位置的黑树的高度。听起来，有点抽象，让我们来看一张图片。以结点10为例， x = 10时， BH(x) = BH(10) = 2。这个2是怎么来的呢？从结点10开始数起（不包含起始结点），到空结点为止。5是黑色结点，NIL也是黑色结点。所以，BH(10) = 2。同理，我们再举一个例子，结点9，当 x = 9时，BH(x) = BH(9) = 1(不包含起始结点)，NIL是黑色结点，所以，BH(9) = 1。现在，你应该清楚的了解了什么是BH（即黑树的高度）。 
首先我们要知道O(logn)中的n是指红黑树节点个数。 已知一条关于红黑树的定理：一棵有n个内部节点的红黑树高度h至多为2log(n+1)。（h <= 2log(n+1)） （这个就和二叉树性质4类似的道理：具有n个结点的完全二叉树的的高度h 为 [logn]+1） 只要证明这条定理成立，时间复杂度也就成立的（因为红黑树查询的时间复杂度其实就是从根节点开始往下查询，最大查询时间也就是到叶节点终止，即为树的高度），接下来就来证明这条定理。 h <= 2log(n+1)可推出n >= 2^(h/2)-1。得出定理的逆否命题是 “高度为h的红黑树，它包含的节点个数至少为 2^(h/2)-1个”。我们只需证明逆否命题为真，即证明了原命题为真。 从某个节点x出发（不包括该节点）到达一个叶节点的任意一条路径上，黑色节点的个数称为该节点的黑高度(x’s black height)，记为bh(x)。 根据性质五可知，从节点x出发到达所有的叶节点都具有相同数目的黑节点。这也就意味着，bh(x)的值是唯一的！ 根据性质四可知，从节点x出发到达叶节点”所经历的黑节点数目”>= “所经历的红节点的数目”（画个红黑树数数就理解了）。假设x是根节点，则可以得出结论”h/2 <= bh(x) < h” (h=黑高度+红高度）。 因此接下来只需证明”高度为h的红黑树，它包含的节点个数至少为 2^bh(x)-1个”。(n >= 2^bh(x)-1) 下面通过”数学归纳法”论证n >= 2^bh(x)-1: 当bh(x)=0时，节点数n(b) = 2^(0)-1 = 0，原命题成立； 当bh(x)=k时，假设该树至少有2^bh(x)-1 = 2^k-1个节点； 当bh(x)=k+1时，根节点的两棵子树的黑高度最小为bh(x)-1也就是也就是k+1-1=k，原因如下： 那么，结点x的左右子树两边的黑高，要么是bh(x)，要么是bh(x)-1。这取决于，结点x的亲子结点的颜色。如果亲子结点是红色，就是bh(x)。如果是黑色，即是bh(x)-1。因为如果是亲子结点是红色的，不计入黑高. 则两棵子树上的节点个数和至少为2*（2^bh(x)-1） = 2^(k+1)-2，那么该树共有2^(k+1)-2+1（加上根节点） = 2^(k+1)-1个节点，与右式相等，原命题成立。 所以数学归纳法证明结束： 本文参考的链接： 红黑树的时间复杂度为: O(lgn) – rcpalc – 博客园 红黑树时间复杂度为什么是O(logn)?_”PANDA的博客-CSDN博客_红黑树时间复杂度 红黑树的时间复杂度分析_岳锋的博客-CSDN博客_红黑树的时间复杂度 面试旧敌之红黑树（直白介绍深入理解） – 掘金
2024最新激活全家桶教程，稳定运行到2099年，请移步至置顶文章：https://sigusoft.com/99576.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处：https://sigusoft.com/45655.html
