介绍
在二叉搜索树的那一节里，我们在最后提到了如果二叉树严重不平衡，其时间复杂度会退化到线性的复杂度，例如从有序数组[1, 2, 3, 4, 5]中构建出的二叉树，就会成为一个线性表，如下图所示。
因此，我们需要有一棵能够自动平衡的二叉树，使得每次插入、删除和查找的复杂度都接近 Θ(nlog n) 的复杂度。AVL 树就是最早被提出的自平衡二叉搜索树，它是由两名俄国的科学家（G. M. Adelson-Velsky 和 E. M. Landis）提出。下面，我们就来看看它是如何做到自平衡的吧。
平衡因子
AVL 树最核心的思想就是计算每个节点的平衡因子（balance factor），平衡因子的定义是一个节点的左孩子的高度减去其右孩子的高度。这里的高度（height）就是指从一个节点出发到达最远叶子节点所经过的最长路径，例如下图的例子中节点 3 到达最远的叶子节点 2 所需要经过的路径长度为 2（从节点 3 到节点 1 和 从节点 1 到节点 2）。
如果是空节点，我们规定其高度为 -1，所以求任意一个节点的高度我们就可以先分别计算出左右孩子的高度，然后取较大者，最后加 1。于是，我们写出以下递归关系式：
在写出计算节点高度的代码时，我们首先需要构建树的节点Node类。
class Node(object):
def __init__(self, value):
self.value = value
self.left = None
self.right = None
self.height = 0 # 初始化为 0
然后是用于计算高度的calc_height函数。
def calc_height(self, node):
if not node:
return -1
return node.height
接下来计算节点的平衡因子就只需将左孩子的高度减去右孩子的高度即可。
def calc_balance_factor(self, node):
if not node:
return 0
return self.calc_height(node.left) - self.calc_height(node.right)
例如，下图中的两个例子，根节点的平衡因子分别为 2 和 -2。
旋转操作
从前面的例子中，我们发现当一个节点的平衡因子的绝对值大于等于 2 时，树就不再平衡。这里，AVL 树提供了一种旋转机制，使得旋转过后的树不仅能保持二叉搜索树的性质，同时能够使节点的平衡因子的绝对值小于 2，接下来我们就分别来讨论一下不同情况下的旋转操作。
LL 型
下图表示的是 LL 型的情况，在根节点的左孩子的左侧添加新节点 1 后，平衡因子从原来的 1 变为了 2，这时我们只需要对根节点 3 执行一次右旋操作树就平衡了。
LR 型
如果往根节点的左孩子的右侧添加新节点（下图中的节点 2），平衡因子也会从 1 变为 2，但这里我们不能采用单次右旋，而是要先对根节点的左孩子执行一次左旋操作，使之变为 LL 型，然后再对根节点进行右旋。
RR 型
RR 型正好与 LL 型的互为镜像，如果向根节点的右孩子的右侧添加一个新节点（下图中的节点 3）后，平衡因子由 -1 变为 -2，导致树的不平衡，这时我们需要对根节点执行一次左旋操作。
RL 型
RL 型与 LR 型也互为镜像，即如果将新节点（下图中的节点 2）插入到根节点的右孩子的左侧，平衡因子由 -1 变为 -2。同样，我们不能用一次左旋来使树重新平衡，而是先对根节点的右孩子执行一次右旋，变为 RR 型，然后再对根节点进行左旋。
一般情况
我们看到，上述的四种情况都是基于两种基本操作：左旋和右旋。然而，我们讨论的并不是一般的情况。举个例子，如果要对下图中的根节点进行右旋，我们会发现根节点的左孩子的右子树不为空，这时该怎么办呢？我们知道，旋转之后的树必须保持二叉树的性质，所以我们可以让多余的右子树作为原根节点的左子树，使得原根节点的值还是大于被调整子树的所有节点的值。
同理，下图也展示了左旋的一般情况，只是与右旋互为镜像操作。
因此，我们写出旋转操作的全部代码。
def left_rotation(self, node):
t1 = node.right
t2 = t1.left
# 重构树
t1.left = node
node.right = t2
# 更新 node 和 h1 的高度
node.height = max(self.calc_height(node.left), self.calc_height(node.right)) + 1
t1.height = max(self.calc_height(t1.left), self.calc_height(t1.right)) + 1
return t1
def right_rotation(self, node):
t1 = node.left
t2 = t1.right
# 重构树
t1.right = node
node.left = t2
# 更新 node 和 h1 的高度
node.height = max(self.calc_height(node.left), self.calc_height(node.right)) + 1
t1.height = max(self.calc_height(t1.left), self.calc_height(t1.right)) + 1
return t1
def settle_violation(self, root):
balance = self.calc_balance_factor(root)
if balance > 1:
# 情况 1：LL 型，右旋
if self.calc_balance_factor(root.left) >= 0:
return self.right_rotation(root)
# 情况 2：LR 型，先左旋后右旋
else:
root.left = self.left_rotation(root.left)
return self.right_rotation(root)
elif balance < -1:
# 情况 3：RR 型，左旋
if self.calc_balance_factor(root.right) <= 0:
return self.left_rotation(root)
# 情况 4：RL 型，先右旋后左旋
else:
root.right = self.right_rotation(root.right)
return self.left_rotation(root)
return root
旋转操作由于只涉及到了指针的变动，因而该过程的时间复杂度不随树的节点个数的增加而增加，即为 Θ(1)。
搜索
和二叉搜索树一样，AVL 树也是从根节点开始搜索，如果搜索的元素比根节点小，那么就从根节点的左子树中继续搜索，如果比根节点大，那么就从右子树中继续搜索，如果相等，则返回该节点，要是搜索到了叶子节点发现还是搜索失败，我们就返回None。
def search(self, value):
# 树的根节点为空就抛出异常
if not self.root:
raise ValueError("The tree is null")
return self.search_node(self.root, value)
def search_node(self, root, value):
if not root: # 如节点为空，则返回 None
return None
if value < root.value: # 从左子树查找
return self.search_node(root.left, value)
elif value > root.value: # 从右子树查找
return self.search_node(root.right, value)
else:
return root
由于 AVL 树是平衡的，所以查找的时间复杂度接近 Θ(log n)。
插入
AVL 树的插入操作也跟二叉搜索树一样，先找到插入的位置，即通过搜索操作找到插入位点，然后创建一个新节点，最后父节点指向该新节点。但由于 AVL 树是一棵自平衡的树，所以每插入一个节点都会更新搜索过程中所经过节点的高度，如发现有节点的高度的绝对值大于等于 2，则采取相应的旋转操作使之保持平衡。这里调用了前面写好的settle_violation函数，整个过程均采用递归的方式实现（这是最难理解的地方，尤其是代码，需要各位小伙伴多花时间研究研究啊～）。
def insert(self, value):
node = Node(value) # 创建新节点
self.root = self.insert_node(self.root, node)
def insert_node(self, root, node):
if not root:
return node
if node.value < root.value:
root.left = self.insert_node(root.left, node)
else:
root.right = self.insert_node(root.right, node)
root.height = max(self.calc_height(root.left), self.calc_height(root.right)) + 1 # 更新根节点的高度
return self.settle_violation(root) # 查看是否满足 AVL 树的性质
删除
同样，AVL 树的删除操作也类似于二叉搜索树，找到删除的节点，然后根据待删除节点的孩子节点个数，判断出该采取哪一种删除方式，由于它跟二叉搜索树一样，这里就不再赘述了，忘记了的小伙伴可以乘坐这里的传送门，找到删除操作的那一部分再看一看。与插入操作一样，删除操作也会检查搜索过程中所经过的所有节点的高度，如果其绝对值大于等于 2，我们也调用settle_violation函数来使树保持平衡，整个删除操作也是一个递归的过程（理解代码也是需要一个漫长的过程哦 ◠‿◠）。
def get_max(self, root):
if root.right:
return self.get_max(root.right)
return root
def remove(self, value):
# 根节点为空则抛出异常
if not self.root:
raise ValueError("The tree is null!")
self.root = self.remove_node(self.root, value)
def remove_node(self, root, value):
if not root:
return root
# 搜索
if value < root.value:
root.left = self.remove_node(root.left, value)
elif value > root.value:
root.right = self.remove_node(root.right, value)
else:
# 左右孩子为空
if not root.left and not root.right:
del root
return None
# 只有左孩子或右孩子
elif not root.left:
temp = root.right
del root
return temp
elif not root.right:
temp = root.left
del root
return temp
# 左右孩子都有
else:
temp = self.get_max(root.left)
root.value = temp.value
root.left = self.remove_node(root.left, temp.value)
root.height = max(self.calc_height(root.left), self.calc_height(root.right)) + 1 # 更新根节点的高度
return self.settle_violation(root) # 查看是否满足 AVL 树的性质
插入和删除操作都是由查找和旋转操作构成，故两者的复杂度均为 Θ(log n) + Θ(1) = Θ(log n)。
合并
最后将上面的这些函数都写在一个AVL_Tree类里。
class AVL_Tree(object):
def __init__(self):
self.root = None
演示
要是你觉得上面的代码很难理解，这里提供了 AVL 树的可视化过程。你可以结合本节的代码将例子输入到可视化的网站中。
→ 本节全部代码 ←
