平衡二叉树是一种特别形式的二叉搜索树，它采用平衡化旋转来避免二叉搜索树出现退化的情况。
二叉搜索树的效率理论上来说，对二叉搜索树进行一次操作的时间复杂度是 O(lgn)，这是因为二叉搜索树在理想状态下是近似于完全二叉树的。但是，在实际操作中，二叉搜索树很容易退化成线性的数据结构。例如，往二叉搜索树中插入一个有序序列，这时会得到一条链，如图 1 所示。
图 1：二叉搜索树退化成线性
这时候，对二叉搜索树进行操作的平均时间复杂度就会退化成 O(n)。左右子树的大小相差巨大的二叉搜索树，就处于非常不平衡的状态。这样的状态会使操作的时间复杂度大大提高。为了维持二叉搜索树的平衡状态，就出现了不同的平衡二叉树算法。
AVL树本节教程要讲到的平衡二叉树，又称为 AVL 树。它维持二叉搜索树平衡的根本在于持续维护这样一个性质：二叉搜索树中，每一个节点的左右子树深度差的绝对值不大于1。
举例来说，图 2（a）所示为 AVL 树，而图 2（b）所示则不是 AVL 树。
图 2：两棵二叉树
那么，如何判断一棵树是否符合 AVL 树的性质？答案就是维护每个节点的平衡因子。每个节点的平衡因子即为节点左子树的深度减去右子树的深度得到的差。在符合 AVL 性质的情况下，平衡因子只能取 -1、0、1。
正因为这样，在插入或删除一个节点之后，要从插入或删除的位置沿通向根的路径回溯，更新这些经过的节点的平衡因子。在检测到当前节点的平衡因子的绝对值大于1时，停止回溯，根据回溯路径中当前节点以及当前节点深度+1 和深度+2 两层节点的位置，选择旋转方法对二叉树的结构进行调整。
如果一棵平衡二叉树中的节点发生了变化，使二叉树不再平衡，此时需要采用平衡化旋转来调整树的结构，使得在不破坏二叉搜索树性质的情况下，让二叉树重新达到平衡。
平衡化旋转分为两种：单向旋转和双向旋转。如果回溯路径中当前节点以及下两层节点处于一条直线上，就可以采用单向旋转。如果在下两层的节点中，每一个节点都是父亲节点的右孩子，那么如图 3 所示，此时采用单向左旋。
图 3：单向左旋
由于此处 A
这样的过程同样可以用图来展示。举例来说，在图 4 这样一棵平衡二叉树中插入节点后，整棵树就变得不平衡了。每个节点上方的数字就是该节点的平衡因子，而长方形代表子树，长方形里面的式子等于它的深度。
图 4：插入节点后平衡因子变化
要想调整二叉树的结构，这里就要用到平衡左旋了。我们取每一棵子树的根节点来代表这一整棵子树，用一共 5 个节点来演示单向左旋的过程。图 5 所示就是单向左旋的效果。
图 5：单向左旋
平衡树的结构最后被调整成了图 6 所示这样，而平衡因子也重新变得符合 AVL 树性质了。
图 6：调整完毕
同样的道理，如果需要进行平衡旋转时，当前节点的下两层节点都是父节点的左孩子，那么就需要采用单向右旋。单向右旋的道理和单向左旋非常相似，下面就主要用图来演示，不多做讲解了。单向右旋的过程如图 7～图 9 所示。
图 7：单向右旋
图 8：插入节点后平衡因子变化
图 9：单向右旋
同样，此处 A
下面看看如何用代码实现单向平衡旋转：
#单向左旋函数，其中parent是p的父节点
def SingleTurnL(parent, p):
q = p.right #找到下一层的节点
#重新连接子树的位置
p.right = q.left
q.left = p
if p == parent.left: #把q连接到原来p的父节点
parent.left = q
else:
parent.right = q
#单向右旋函数，其中fa是p的父节点
def SingleTurnR(parent,p):
q = p.left
#重新连接子树的位置
p.left = q.right
q.right = p
if p == parent.left: #把q连接到原来p的父节点
parent.left = q
else:
parent.right = q
双向旋转实际上是进行两次不同方向的单向旋转操作。在当前节点以及下两层的节点构成折线形状时，需要进行双向旋转。根据进行不同方向单向旋转的先后顺序，双向旋转也被分为两类：先左后右双向旋转和先右后左双向旋转。
在经过的回溯路径中，如果深度为当前节点深度+1 的节点是当前节点的左孩子，而深度为当前节点深度+2 的节点是深度+1 层节点的右孩子时，使用先左后右双向旋转。
图 10 所示为旋转的过程。可以看出，在调整二叉树结构的过程中，先进行一次单向左旋，再进行一次单向右旋。
图 10：先左后右双向旋转
根据原本的结构可以推断出，B
图 11：插入节点后平衡因子变化
在破坏之后，为了维持二叉搜索树的平衡，我们进行先左后右双向旋转。首先我们要对 A、B 以及它们的子树做单向左旋，如图 12 所示。
图 12：单向左旋
对 A、B 的单向左旋结束后，把 A 与 C 相连，然后再对 A 和 C 做单向右旋。如图 13 所示，在单向右旋的过程中，B 和 B 的子树被看作一个整体。
图 13：单向右旋
经过两次旋转后，二叉树又重新变得平衡了。按同样的规律，先右后左双向旋转适用于这种情况：深度为当前节点深度+1 的节点是当前节点的右孩子，而深度为当前节点深度+2 的节点是深度+1 层节点的左孩子。
这种情况下，先对 A、B 两节点进行单向右旋，再对 A、C 两节点进行单向左旋，如图 14 所示。
图 14：先右后左双向旋转
同样地，我们以图示的形式把旋转过程展现出来。如图 15 所示，在二叉树中插入节点后，二叉树的平衡性被破坏了。
图 15：插入节点后平衡因子变化
把节点A、B单独拿出来进行单向右旋，如图 16 所示。
图 16：单向右旋
把 B 和它的子树看成一个整体，作为 A 的右子树，再对节点 A、C 进行单向左旋，如图 17 所示。
图 17：单向左旋
这样，二叉树又重新变得平衡了。而在写好了单向旋转函数的基础上，双向旋转函数的逻辑就很简单了，即调用两次单向旋转函数。
代码可以这么写：
#先左后右双向旋转，fa是p父节点的位置，p是当前节点
def DoubleLR(fa,p):
SingleTurnL(p,left[p]) #调用单向左旋函数
SingleTurnR(fa,p) #调用单向右旋函数
#先右后左双向旋转，fa是p父节点的位置，p是当前节点
def DoubleRL(fa,p):
SingleTurnR(p,right[p]) #调用单向右旋函数
SingleTurnL(fa,p) #调用单向左旋函数
到这里，维持 AVL 树平衡的4种旋转方法就学习完毕了。有了这些旋转方法，再加上前面所学到的二叉搜索树基本操作函数，就可以编写出一棵完整的平衡二叉树了。除 AVL 树，还有 TREAP（树堆）、红黑树等数据结构，都是以维持二叉搜索树平衡的宗旨来设计的。
【python算法系列一】冒泡排序算法采用重复遍历数组并依次比较相邻元素的方法来排序。由于在冒泡算法进行排序的过程中，最大数/最小数会慢慢“浮”到数组的末尾，所以算法由此命名。https://blog.csdn.net/m0_70372647/article/details/124736577【python算法系列二】快速排序算法快速排序的思想是：取数组中的一个数作为基准值，把所有小于基准值的数都放在它的一侧，再把所有大于基准值的数都放在它的另一侧。随后，对基准值左右两侧的数组分别进行快速排序。由此可以看出，快速排序的整个排序过程也是递归进行的。快速排序的平均时间复杂度是 O(nlgn)，最好情况下的时间复杂度是 O(nlgn)。最坏情况下，快速排序的时间复杂度可能退化成 O(n2)，但这种情况很少见。它的空间复杂度是 O(nlgn)。它是一个不稳定的排序算法。如果使用得当，快速排序的速度可以达到归并排序和堆排序的数倍，所以.https://blog.csdn.net/m0_70372647/article/details/124758205【python算法系列三】 希尔排序算法希尔排序，又叫“缩小增量排序”，是对插入排序进行优化后产生的一种排序算法。它的执行思路是：把数组内的元素按下标增量分组，对每一组元素进行插入排序后，缩小增量并重复之前的步骤，直到增量到达 1。一般来说，希尔排序的时间复杂度为 O(n1.3)～O(n2)，它视增量大小而定。希尔排序的空间复杂度是 O(1)，它是一个不稳定的排序算法。进行希尔排序时，元素一次移动可能跨越多个元素，从而可能抵消多次移动，提高了效率。下面是使用（数组长度/2）作为初始增量的升序希尔排序，每一轮排序过后，增量都缩小一半。1) 如https://blog.csdn.net/m0_70372647/article/details/124808637【python算法系列四】堆排序算法堆排序，就像它的名字一样，利用了堆的特性来进行排序。实现堆排序的思路是，把数组构建成一棵二叉树，并随着每次堆的变化更新堆顶的最大/最小值。堆排序的时间复杂度在所有情况下都是 O(nlgn)，它也是一个不稳定的算法。在开始编写堆排序的程序之前，我们首先要了解“堆”的概念。堆是一种数据结构，它是一种特殊的完全二叉树：如果这个堆是一个大顶堆（最大的元素在堆顶），那么每个节点上的元素都应该比它的子节点上的元素要大，最大的元素在根节点上；反之，如果是小顶堆，那么每个节点上的元素都应该比它的子节点小，最小的元素在根节https://blog.csdn.net/m0_70372647/article/details/124870580【python算法系列五】桶排序算法由于桶排序算法把每个数都放到合适的“桶”里进行排序，因此而得名。桶排序的算法原理可以理解为创建一个新的数组，把数依次放入合适的桶内，再按一定顺序输出桶。当每个桶的数据范围为 1 且数据皆为整数时，桶排序的时间复杂度在所有情况下都是 O(n)，因为它是一个线性的排序算法。但是，它的空间需求要视排序数据的范围而定，所以极有可能浪费很多空间。假设我们有 10 个整数 [1,1,3,19,35,49,50,5,10,16]，它们的范围在 1～50。如图 1 所示，我们建立 50 个存放数据的桶。图 1：https://blog.csdn.net/m0_70372647/article/details/124871084【python算法系列六】选择排序算法选择排序表示从无序的数组中，每次选择最小或最大的数据，从无序数组中放到有序数组的末尾，以达到排序的效果。选择排序的平均时间复杂度是O(n2)，最好情况下的时间复杂度和最坏情况下的时间复杂度都是 O(n2)。另外，它是一个不稳定的排序算法。选择排序的过程如下;1) 如图 1 所示，我们仍以递增排序的算法为例，先遍历未排序的数组，找到最小的元素。然后，把最小的元素从未排序的数组中删除，添加到有序数组的末尾。因为最小的元素是 1，所以 1 被添加到仍为空的有序数组末尾。图 1：选择并放置第一个元素https://blog.csdn.net/m0_70372647/article/details/124897318【python算法系列七】插入排序算法排序通常指把毫无规律的数据，按照一种特定的规律，整理成有序排列的状态。一般情况下，排序算法按照关键字的大小，以从小到大或从大到小的顺序将数据排列。排序算法是最基础也是最重要的算法之一，在处理大量数据时，使用一个优秀的排序算法可以节省大量时间和空间。因为不同的排序算法拥有不同的特点，所以我们应根据情况选择合适的排序算法。初级排序算法是指几种较为基础且容易理解的排序算法。初级排序算法包括插入排序、选择排序和冒泡排序 3 种。虽然它们的效率相对于高级排序算法偏低，但是在了解初级排序算法之后，再去学习相对复https://blog.csdn.net/m0_70372647/article/details/124907803【python算法系列八】归并排序算法相比起初级排序算法，高级排序算法往往有更加复杂的逻辑，但也会有更高的时间或空间效率。其中有些高级排序算法是由初级排序算法优化而来的。在处理大量数据时，高级排序算法的一般更加常用。本节教程介绍的第一种高级排序算法是归并排序。“归并”一词，意为“合并”。顾名思义，归并排序算法就是一个先把数列拆分为子数列，对子数列进行排序后，再把有序的子数列合并为完整的有序数列的算法。它实际上采用了分治的思想，之后我们会深度讲解分治思想。归并排序的平均时间复杂度是 O(nlgn)，最好情况下的时间复杂度是 O(nlg.https://blog.csdn.net/m0_70372647/article/details/124908304【Python算法系列九】 顺序查找算法定义查找的定义为：在一个数据元素集合中，通过一定的方法确定与给定关键字相同的数据元素是否存在于集合中。一般来说，如果查找成功，程序会返回数据的位置或相关信息；如果查找失败，则返回相应的提示。查找的方法可以分为两种：比较查找法与计算式查找法。比较查找法基于两种数据结构：线性表和树。查找的对象（一般是由同一类型的数据元素/记录构成的集合）又可以被称为查找表。查找还分为静态查找和动态查找。对查找表进行静态查找时，程序只进行查找并返回信息；进行动态查找时，在静态查找的基础上，还增加了增删查找表中.https://blog.csdn.net/m0_70372647/article/details/124931956【Python算法系列十】二分查找算法二分查找，也叫折半查找，是一种适用于顺序存储结构的查找方法。它是一种效率较高的查找方法，时间复杂度为 O(lgn)，但它仅能用于有序表中。也就是说，表中的元素需按关键字大小有序排列。二分查找用左右两个指针来标注查找范围。程序开始时，查找范围是整个线性表，左指针指向第一个元素，右指针指向最后一个元素；每一次循环过后，查找范围都缩小为原先的一半，直到左右指针重叠或者左指针处于右指针的右侧。因为每次缩小一半的范围，所以可以得出二分查找的时间复杂度为 O(lgn)。...https://blog.csdn.net/m0_70372647/article/details/124936085
【Python算法系列十一】二叉树的3种遍历方式二叉树的遍历是指从根结点出发，按照某种次序依次访问二叉树中所有结点，使得每个结点被访问一次且仅被访问一次。遍历二叉树的方法主要分 3 种：先序遍历、中序遍历和后序遍历：先序遍历指最先遍历节点本身，再遍历节点的左子树，最后遍历右子树的遍历方法；中序遍历指最先遍历节点的左子树，再遍历节点本身，最后遍历右子树的遍历方法；后序遍历指最先遍历节点的左子树，再遍历右子树，最后遍历节点本身的一种遍历方法。在图 1 中，L 是左子树，R 是右子树，D 当前节点。如果用这三个字母来表示 3 种遍历.https://blog.csdn.net/m0_70372647/article/details/124989895
