二叉排序树查找节点的时间复杂度_二叉排序树查找节点的时间复杂度

讲透学烂二叉树(五)：分支平衡—AVL树与红黑树伸展树自平衡 　　简叙二叉树 　　二叉树的最大优点的就是查找效率高，在二叉排序树中查找一个结点的平均时间复杂度是O(log₂N)； 　　在《讲透学烂二叉树(二)：树与二叉/搜索/平衡等树的概念与特征》提到 　　二叉排序树是为了实现动态查找而设计的数据结构，它是面向查找操作的。对于目标节点的查找过程类似与有序数组的二分查找，在二叉排序树中查找一个结点的平均时间复杂度是O(log n)； 　　设节点数目为n，树的深度为h，假设树的每层都被塞满(第L层有2^L个节点，层数从1开始)，则根据等比数列公式可得h=log（n+1）。即最好的情况下，二叉查找树的查找效率为O(log n)。当二叉查找树退化为单链表时，比如，只有右子树的情况,如下图所示，此时查找效率为O(n)。 　　

　　总之，二叉查找树越是“矮胖”，也就是每层尽可能地被“塞满”（每个父节点均有两个子节点）时，查找效率越高。每层都被塞满时，查找效率最高，最高为O(log n)。当二叉查找树退化为单链表时，查找效率最低，最低为O(n)。 　　为了解决二叉查找树退化为单链表时查找效率低下的问题，引入了平衡二叉树(AVL)。 　　平衡二叉树的基本操作 　　插入：插入节点，让树平衡删除：删除节点，让树平衡旋转：旋转操作，它可以使得某一个结点提升到他父亲的位置而不破坏平衡二叉树的性质。伸展：就是把当前节点，移动至树根，或者说，把当前节点变成根节点。 　　更多了解旋转与伸展相关内容，推荐阅读《伸展树（Splay Tree）进阶 – 从原理到实现 》，这里我们首先将二叉树 　　平衡二叉树 　　平衡二叉树（Balanced Binary Tree）又被称为AVL树（有别于AVL算法） 　　在AVL中任何节点的两个儿子子树的高度最大差别为1，所以它也被称为高度平衡树，n个结点的AVL树最大深度约1.44log2n。查找、插入和删除在平均和最坏情况下都是O(logn)。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。这个方案很好的解决了二叉查找树退化成链表的问题，把插入，查找，删除的时间复杂度最好情况和最坏情况都维持在O(logN)。但是频繁旋转会使插入和删除牺牲掉O(logN)左右的时间，不过相对二叉查找树来说，时间上稳定了很多。 　　平衡二叉树的常用算法有红黑树、AVL树等。在平衡二叉搜索树中，我们可以看到，其高度一般都良好地维持在O(log2n)，大大降低了操作的时间复杂度。 　　最小二叉平衡树的节点的公式如下： 　　F(n)=F(n-1)+F(n-2)+1 　　这个类似于一个递归的数列，可以参考Fibonacci数列，1是根节点，F(n-1)是左子树的节点数量，F(n-2)是右子树的节点数量。 　　平衡因子 　　某结点的左子树与右子树的高度或深度差即为该结点的平衡因子（BF,Balance Factor），平衡二叉树（AVL树）上所有结点的平衡因子只可能是 -1，0 或 1 　　下图中就标注了所有节点的平衡因子 　　

　　（平衡因子计算时左子树 – 右子树 或 右子树 – 左子树 都可以，因为判断树是否平衡的条件是：每个结点的左右子树的高度之差的绝对值不超过1，只不过判断失衡以后还要判断是哪一种失衡，这就需要根据情况来选择是左-右还是右-左了） 　　平衡二叉树查找节点 　　在 AVL树 中查找与在 二叉查找树 中查找完全一样，因为AVL树总是保持平衡的，树的结构不会由于查询而改变，这里就不再赘述了 　　平衡二叉树插入节点 　　先梳理一下步骤 　　

　　先来实现搜索最低失衡节点，搜索最低失衡节点是从新插入的节点（也就是叶子节点） 　　往上搜索（也可以说成从新增结点开始向根部回溯），搜索到的第一个平衡因子>1（|左子树高度-右子树高度|>1）的节点，作为最低失衡节点，因为是从新插入的节点往上搜索，二叉树的搜索是单向的（结构体成员中只有左右子树），单独使用一个函数来实现逆向搜索实现起来并不方便，这里就把搜索最低失衡节点的操作放到递归实现的插入操作中 　　搞清楚了各个节点的高度，平衡因子的计算也比较方便了，下面就是AVL树的核心操作“旋转”，不同的失衡情况有不同的旋转方式，一共有四种节点失衡情况，如下图 　　

　　二叉树不平衡的四种情况 　　不同失衡情况下的示例二叉树，如下图（读者可能会发现“最低失衡节点的左子树的左子树还有非空节点”这个判断依据，对第二组图适用，但对于第一组图不太合适） 　　

　　

　　AVL树单旋转和双旋转 　　单旋转 　　单旋转是针对于左左和右右这两种情况的解决方案，这两种情况是对称的，只要解决了左左这种情况，右右就很好办了。图3是左左情况的解决方案，节点k2不满足平衡特性，因为它的左子树k1比右子树Z深2层，而且k1子树中，更深的一层的是k1的左子树X子树，所以属于左左情况。 　　为使树恢复平衡，我们把k2变成这棵树的根节点，因为k2大于k1，把k2置于k1的右子树上，而原本在k1右子树的Y大于k1，小于k2，就把Y置于k2的左子树上，这样既满足了二叉查找树的性质，又满足了平衡二叉树的性质。 　　这样的操作只需要一部分指针改变，结果我们得到另外一颗二叉查找树，它是一棵AVL树，因为X向上一移动了一层，Y还停留在原来的层面上，Z向下移动了一层。整棵树的新高度和之前没有在左子树上插入的高度相同，插入操作使得X高度长高了。因此，由于这颗子树高度没有变化，所以通往根节点的路径就不需要继续旋转了。 　　双旋转 　　对于左右和右左这两种情况，单旋转不能使它达到一个平衡状态，要经过两次旋转。双旋转是针对于这两种情况的解决方案，同样的，这样两种情况也是对称的，只要解决了左右这种情况，右左就很好办了。图4是左右情况的解决方案，节点k3不满足平衡特性，因为它的左子树k1比右子树Z深2层，而且k1子树中，更深的一层的是k1的右子树k2子树，所以属于左右情况。 　　为使树恢复平衡，我们需要进行两步，第一步，把k1作为根，进行一次右右旋转，旋转之后就变成了左左情况，所以第二步再进行一次左左旋转，最后得到了一棵以k2为根的平衡二叉树。 　　首先要确定中心结点，即最小失衡结点A，其平衡因子的绝对值为2，主要有四种不平衡的情况： 　　（1）在A的左儿子B的左子树插入，又称为LL—右旋转； 　　（2）在A的左儿子C的右子树插入P，又称为LR—左右旋转； 　　（3）在A的右儿子C的左子树插入P，又称为RL—右左旋转； 　　（4）在A的右儿子B的右子树插入，又称为RR—左旋转。 　　要记住两个重要节点，一个是失衡结点，另一个是失衡结点的儿子，该儿子在失衡路径上，旋转操作则是依据失衡结点的儿子为中心，对失衡结点进行下移动。在这四种失衡情况中（1）和（4）两种情况是对称的，这两种情况的旋转算法是一致的，只需要经过一次旋转就可以达到目标，我们称之为单旋转，（2）和（3）两种情况也是对称的，这两种情况的旋转算法也是一致的，需要进行两次旋转，我们称之为双旋转。 　　二叉树左右旋转讲解 　　在进行旋转操作时，首先要找到最小失衡结点，判断失衡的类型，然后选择旋转的类型，如何判断呢？根据上面的图片中的结点A，BF为2确定为左儿子左边L，根据左儿子的BF为-1，则确定为R，此时属于不平衡情况（2），使用双旋转，下面详细介绍单旋转和双旋转的四种旋转方式。 　　1、LL右旋转 　　

　　P下移，占据C的右儿子空穴，C的右儿子称为P的左儿子 　　2、RR左旋转 　　

　　P下移，占据C的左儿子空穴，C的左儿子作为P的右儿子。 　　3、LR左右旋转 　　双旋转分为两步：左旋转，以P的儿子C作为失衡结点，Q的右儿子q，Q下移，占据q的左儿子，q的左儿子左儿子作为Q的右儿子，q作为P的左儿子。 　　右旋转，P下移，作为p的右儿子，q的右儿子作为P的左儿子。 　　4、RL右左旋转 　　

　　右旋转，P的右儿子C作为新的失衡结点Q，Q的左儿子q，Q下移，作为q的右儿子，q的右儿子作为Q的左儿子，q作为P的右儿子。 　　左旋转，P下移，占据q的左儿子，q的左儿子作为P的右儿子。 　　先梳理一下步骤 　　平衡树，旋转代码实现 　　JavaScript代码，暂未实现 　　平衡二叉搜索树的分类 　　平衡的二叉搜索树一般分为两类： 　　严格维护平衡的，树的高度控制在log2n，使得每次操作都能使得时间复杂度控制在O(logn)，例如AVL树，红黑树； 　　非严格维护平衡的，不能保证每次操作都控制在O(logn)，但是每次操作均摊时间复杂度为O(logn)，例如伸展树。 　　平衡二叉树之红黑树 　　红黑树是一种自平衡二叉查找树，又称之为”对称二叉B树”。设平衡二叉树的深度为N，则N%2=0结点为黑色，N%2=1结点为红色。这些约束确保了红黑树的关键特性: 从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这个树大致上是平衡的。因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例，这个在高度上的理论上限允许红黑树在最坏情况下都是高效的，而不同于普通的二叉查找树。 　　

　　红黑树的自平衡操作： 　　因为每一个红黑树也是一个特化的二叉查找树，因此红黑树上的只读操作与普通二叉查找树上的只读操作相同。然而，在红黑树上进行插入操作和删除操作会导致不再符合红黑树的性质。恢复红黑树的性质需要少量(O(logn))的颜色变更(实际是非常快速的)和不超过三次树旋转(对于插入操作是两次)。虽然插入和删除很复杂，但操作时间仍可以保持为O(logn) 次。 　　我们首先以二叉查找树的方法增加节点并标记它为红色。如果设为黑色，就会导致根到叶子的路径上有一条路上，多一个额外的黑节点，这个是很难调整的（违背性质5）。但是设为红色节点后，可能会导致出现两个连续红色节点的冲突，那么可以通过颜色调换（color flips）和树旋转来调整。下面要进行什么操作取决于其他临近节点的颜色。同人类的家族树中一样，我们将使用术语叔父节点来指一个节点的父节点的兄弟节点。注意: 　　性质1和性质3总是保持着。 　　性质4只在增加红色节点、重绘黑色节点为红色，或做旋转时受到威胁。 　　性质5只在增加黑色节点、重绘红色节点为黑色，或做旋转时受到威胁。 　　红黑树的插入操作： 　　假设，将要插入的节点标为N，N的父节点标为P，N的祖父节点标为G，N的叔父节点标为U。在图中展示的任何颜色要么是由它所处情形这些所作的假定，要么是假定所暗含的。情形1: 该树为空树，直接插入根结点的位置，违反性质1，把节点颜色有红改为黑即可。情形2: 插入节点N的父节点P为黑色，不违反任何性质，无需做任何修改。在这种情形下，树仍是有效的。性质5也未受到威胁，尽管新节点N有两个黑色叶子子节点；但由于新节点N是红色，通过它的每个子节点的路径就都有同通过它所取代的黑色的叶子的路径同样数目的黑色节点，所以依然满足这个性质。注： 情形1很简单，情形2中P为黑色，一切安然无事，但P为红就不一样了，下边是P为红的各种情况，也是真正难懂的地方。情形3: 如果父节点P和叔父节点U二者都是红色，(此时新插入节点N做为P的左子节点或右子节点都属于情形3,这里右图仅显示N做为P左子的情形)则我们可以将它们两个重绘为黑色并重绘祖父节点G为红色(用来保持性质4)。现在我们的新节点N有了一个黑色的父节点P。因为通过父节点P或叔父节点U的任何路径都必定通过祖父节点G，在这些路径上的黑节点数目没有改变。但是，红色的祖父节点G的父节点也有可能是红色的，这就违反了性质4。为了解决这个问题，我们在祖父节点G上递归地进行上述情形的整个过程（把G当成是新加入的节点进行各种情形的检查）。比如，G为根节点，那我们就直接将G变为黑色（情形1）；如果G不是根节点，而它的父节点为黑色，那符合所有的性质，直接插入即可（情形2）；如果G不是根节点，而它的父节点为红色，则递归上述过程（情形3）。 　　情形4: 父节点P是红色而叔父节点U是黑色或缺少，新节点N是其父节点的左子节点，而父节点P又是其父节点G的左子节点。在这种情形下，我们进行针对祖父节点G的一次右旋转; 在旋转产生的树中，以前的父节点P现在是新节点N和以前的祖父节点G的父节点。我们知道以前的祖父节点G是黑色，否则父节点P就不可能是红色(如果P和G都是红色就违反了性质4，所以G必须是黑色)。我们切换以前的父节点P和祖父节点G的颜色，结果的树满足性质4。性质5也仍然保持满足，因为通过这三个节点中任何一个的所有路径以前都通过祖父节点G，现在它们都通过以前的父节点P。在各自的情形下，这都是三个节点中唯一的黑色节点。 　　情形5: 父节点P是红色而叔父节点U是黑色或缺少，并且新节点N是其父节点P的右子节点而父节点P又是其父节点的左子节点。在这种情形下，我们进行一次左旋转调换新节点和其父节点的角色; 接着，我们按情形4处理以前的父节点P以解决仍然失效的性质4。注意这个改变会导致某些路径通过它们以前不通过的新节点N（比如图中1号叶子节点）或不通过节点P（比如图中3号叶子节点），但由于这两个节点都是红色的，所以性质5仍有效。

　　注: 插入实际上是原地算法，因为上述所有调用都使用了尾部递归。 　　红黑树的删除操作： 　　如果需要删除的节点有两个儿子，那么问题可以被转化成删除另一个只有一个儿子的节点的问题。对于二叉查找树，在删除带有两个非叶子儿子的节点的时候，我们找到要么在它的左子树中的最大素、要么在它的右子树中的最小素，并把它的值转移到要删除的节点中。我们接着删除我们从中复制出值的那个节点，它必定有少于两个非叶子的儿子。因为只是复制了一个值，不违反任何性质，这就把问题简化为如何删除最多有一个儿子的节点的问题。它不关心这个节点是最初要删除的节点还是我们从中复制出值的那个节点。 　　我们只需要讨论删除只有一个儿子的节点(如果它两个儿子都为空，即均为叶子，我们任意将其中一个看作它的儿子)。如果我们删除一个红色节点（此时该节点的儿子将都为叶子节点），它的父亲和儿子一定是黑色的。所以我们可以简单的用它的黑色儿子替换它，并不会破坏性质3和性质4。通过被删除节点的所有路径只是少了一个红色节点，这样可以继续保证性质5。另一种简单情况是在被删除节点是黑色而它的儿子是红色的时候。如果只是去除这个黑色节点，用它的红色儿子顶替上来的话，会破坏性质5，但是如果我们重绘它的儿子为黑色，则曾经通过它的所有路径将通过它的黑色儿子，这样可以继续保持性质5。 　　需要进一步讨论的是在要删除的节点和它的儿子二者都是黑色的时候，这是一种复杂的情况。我们首先把要删除的节点替换为它的儿子。出于方便，称呼这个儿子为N(在新的位置上)，称呼它的兄弟(它父亲的另一个儿子)为S。在下面的示意图中，我们还是使用P称呼N的父亲，SL称呼S的左儿子，SR称呼S的右儿子。 　　如果N和它初始的父亲是黑色，则删除它的父亲导致通过N的路径都比不通过它的路径少了一个黑色节点。因为这违反了性质5，树需要被重新平衡。有几种情形需要考虑: 　　情形1: N是新的根。在这种情形下，我们就做完了。我们从所有路径去除了一个黑色节点，而新根是黑色的，所以性质都保持着。 　　注意: 在情形2、5和6下，我们假定N是它父亲的左儿子。如果它是右儿子，则在这些情形下的左和右应当对调。 　　情形2: S是红色。在这种情形下我们在N的父亲上做左旋转，把红色兄弟转换成N的祖父，我们接着对调N的父亲和祖父的颜色。完成这两个操作后，尽管所有路径上黑色节点的数目没有改变，但现在N有了一个黑色的兄弟和一个红色的父亲（它的新兄弟是黑色因为它是红色S的一个儿子），所以我们可以接下去按情形4、情形5或情形6来处理。 　　

　　情形3: N的父亲、S和S的儿子都是黑色的。在这种情形下，我们简单的重绘S为红色。结果是通过S的所有路径，它们就是以前不通过N的那些路径，都少了一个黑色节点。因为删除N的初始的父亲使通过N的所有路径少了一个黑色节点，这使事情都平衡了起来。但是，通过P的所有路径现在比不通过P的路径少了一个黑色节点，所以仍然违反性质5。要修正这个问题，我们要从情形1开始，在P上做重新平衡处理。 　　情形4: S和S的儿子都是黑色，但是N的父亲是红色。在这种情形下，我们简单的交换N的兄弟和父亲的颜色。这不影响不通过N的路径的黑色节点的数目，但是它在通过N的路径上对黑色节点数目增加了一，添补了在这些路径上删除的黑色节点。 　　情形5: S是黑色，S的左儿子是红色，S的右儿子是黑色，而N是它父亲的左儿子。在这种情形下我们在S上做右旋转，这样S的左儿子成为S的父亲和N的新兄弟。我们接着交换S和它的新父亲的颜色。所有路径仍有同样数目的黑色节点，但是现在N有了一个黑色兄弟，他的右儿子是红色的，所以我们进入了情形6。N和它的父亲都不受这个变换的影响。 　　

　　情形6: S是黑色，S的右儿子是红色，而N是它父亲的左儿子。在这种情形下我们在N的父亲上做左旋转，这样S成为N的父亲（P）和S的右儿子的父亲。我们接着交换N的父亲和S的颜色，并使S的右儿子为黑色。子树在它的根上的仍是同样的颜色，所以性质3没有被违反。但是，N现在增加了一个黑色祖先: 要么N的父亲变成黑色，要么它是黑色而S被增加为一个黑色祖父。所以，通过N的路径都增加了一个黑色节点。 　　此时，如果一个路径不通过N，则有两种可能性:它通过N的新兄弟。那么它以前和现在都必定通过S和N的父亲，而它们只是交换了颜色。所以路径保持了同样数目的黑色节点。它通过N的新叔父，S的右儿子。那么它以前通过S、S的父亲和S的右儿子，但是现在只通过S，它被假定为它以前的父亲的颜色，和S的右儿子，它被从红色改变为黑色。合成效果是这个路径通过了同样数目的黑色节点。 　　在任何情况下，在这些路径上的黑色节点数目都没有改变。所以我们恢复了性质4。在示意图中的白色节点可以是红色或黑色，但是在变换前后都必须指定相同的颜色。 　　

　　红黑树实现源码 　　参考文章： 　　算法：树和图-理论 https://blog.csdn.net/weixin_43126117/article/details/97927143 　　[Data Structure] 数据结构中各种树 https://www.cnblogs.com/maybe2030/p/4732377.html#_label2 　　你真的懂树吗？二叉树、AVL平衡二叉树、伸展树、B-树和B+树原理和实现代码详解 www.srcmini.com/1315.html 　　伸展树（Splay Tree）进阶 – 从原理到实现 https://www.cnblogs.com/dilthey/p/9379652.html#splay-2.1 　　AVL树（查找、插入、删除）——C语言 https://www.cnblogs.com/lanhaicode/p/11321243.html 　　转载本站文章《讲透学烂二叉树(五)：分支平衡—AVL树与红黑树伸展树自平衡》,请注明出处：https://www.zhoulujun.cn/html/theory/algorithm/TreeGraph/8288.html