什么是二叉树的AVL树？「草稿版」

定义

你好，我是悦创。

AVL 树是一种自平衡的二叉搜索树。

在这种树中，任何节点的两个子树的高度最多相差一，这有助于确保树保持相对平衡，从而保证树上的操作（如搜索、插入、删除）可以在对数时间内完成。AVL树是由两位苏联数学家 G. M. Adelson-Velsky和 E. M. Landis 命名的。

AVL 树的平衡是通过在每次插入或删除节点后使用一系列称为旋转的操作来实现的。这些旋转重新排列节点以保持树的平衡。根据树的不平衡类型，可以进行四种基本旋转：左旋、右旋、左右旋和右左旋。

• 左旋（Right Rotation）：当一个节点的左子树的高度比右子树的高度至少多2时进行。这种情况通常发生在左子树的左侧添加了新节点。
• 右旋（Left Rotation）：与左旋相反，当一个节点的右子树的高度比左子树的高度至少多2时进行。这通常发生在右子树的右侧添加了新节点。
• 左右旋（Left-Right Rotation）：这是一种双重旋转，首先在节点的左子节点上执行左旋，然后在原节点上执行右旋。这种情况发生在左子树的右侧添加了新节点。
• 右左旋（Right-Left Rotation）：与左右旋相反，首先在节点的右子节点上执行右旋，然后在原节点上执行左旋。这种情况发生在右子树的左侧添加了新节点。

通过这些旋转，AVL 树确保任何时间点，任何节点的左右子树高度差不会超过 1，从而保持了树的平衡。这样，AVL 树的搜索、插入和删除操作的时间复杂度都可以保持在 O(log n)，其中n是树中节点的数量。

样例🌰

• 平衡二叉树定义为：一个二叉树，其中每个节点的左右子树的高度差不超过1

给定的树结构如下：

    A
   / \
  B   C
 / \
D   E

我们可以分析各个节点的左右子树高度差：

• 节点A的左子树高度为2（B的高度），右子树高度为1（C的高度），高度差为1。
• 节点B的左子树高度为1（D的高度），右子树高度为1（E的高度），高度差为0。
• 节点C、D、E都是叶子节点，左右子树高度均为0，高度差为0。

由于所有节点的左右子树高度差都不超过1，因此这个树是平衡二叉树。

旋转原则

当我们谈论二叉搜索树（BST）的平衡问题时，"左旋"和"右旋"是常用的操作来维护或恢复树的平衡。这些操作在平衡二叉树（如AVL树）或红黑树中特别重要。下面我将介绍左旋和右旋的原理以及它们是如何应用的。

右旋（Right Rotation）

右旋通常应用于左子树比右子树高的情况。假设有以下二叉树结构：

    A
   / 
  B   
 / 
C   

右旋步骤：

1. 将节点B作为新的根节点。
2. 将节点A降为节点B的右子节点。
3. 如果节点B有一个右子节点，将其变为节点A的左子节点。

右旋后的树结构：

  B
 / \
C   A

左旋（Left Rotation）

左旋通常应用于右子树比左子树高的情况。假设有以下二叉树结构：

A
 \
  B
   \
    C

左旋步骤：

1. 将节点B作为新的根节点。
2. 将节点A降为节点B的左子节点。
3. 如果节点B有一个左子节点，将其变为节点A的右子节点。

左旋后的树结构：

  B
 / \
A   C

应用场景

• AVL树：在插入或删除节点时，AVL树会检查每个节点的平衡因子（左子树高度与右子树高度之差）。如果任何节点的平衡因子超出[-1, 1]的范围，则通过旋转操作来重新平衡树。
• 红黑树：在插入或删除操作后，红黑树可能需要通过一系列的左旋和右旋来维护其特定的平衡规则。

通过这些旋转操作，平衡二叉树能够保持较低的树高，从而确保操作（如搜索、插入、删除）的效率。

欢迎关注我公众号：AI悦创，有更多更好玩的等你发现！

公众号：AI悦创【二维码】