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

AI悦创原创大约 6 分钟...约 1843 字

定义

你好，我是悦创。

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

右旋步骤：

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

右旋后的树结构：

  B
 / \
C   A

左旋（Left Rotation）

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

A
 \
  B
   \
    C

左旋步骤：

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

左旋后的树结构：

  B
 / \
A   C

应用场景

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

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

详情

要根据给定的数列 4,3,6,5,7,8 创建对应的二叉搜索树（BST），然后通过旋转操作将其转化为平衡二叉树（比如AVL树），我们可以分步骤进行。首先是构建BST，然后根据树的平衡状态进行相应的旋转操作。

构建二叉搜索树

插入 4:
```
4
```
插入 3 (作为4的左子节点):
```
4
/
3
```
插入 6 (作为4的右子节点):
```
4
/ \
3   6
```
插入 5 (作为6的左子节点):
```
4
/ \
3   6
   /
  5
```
插入 7 (作为6的右子节点):
```
4
/ \
3   6
   / \
  5   7
```

插入 8 (作为7的右子节点):

现在，我们有了一个二叉搜索树。但是，这棵树是不平衡的，因为节点6的右子树高度比左子树高度大于1。

平衡二叉树

我们需要通过旋转来平衡这棵树。这里，我们将执行右旋和左旋的组合。

右旋节点6：注意到节点6的右子树（包含节点7和8）比左子树（包含节点5）高，我们可以通过右旋节点6来减小这种不平衡。
右旋后的树：
```
4
/ \
3   7
   / \
  6   8
 /
5
```
左旋节点4：现在，节点4的右子树比左子树高，我们通过左旋节点4来平衡整棵树。
左旋后的树：
```
    7
   / \
  4   8
 / \
3   6
   /
  5
```

现在，我们得到了一个更加平衡的树结构。每个节点的左右子树高度差不超过1，符合平衡二叉树的定义。通过这样的旋转操作，我们能够保持树的平衡，从而优化搜索、插入和删除操作的效率。

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

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

AI悦创·编程一对一

AI悦创·推出辅导班啦，包括「Python 语言辅导班、C++ 辅导班、java 辅导班、算法/数据结构辅导班、少儿编程、pygame 游戏开发、Linux、Web 全栈」，全部都是一对一教学：一对一辅导 + 一对一答疑 + 布置作业 + 项目实践等。当然，还有线下线上摄影课程、Photoshop、Premiere 一对一教学、QQ、微信在线，随时响应！微信：Jiabcdefh

C++ 信息奥赛题解，长期更新！长期招收一对一中小学信息奥赛集训，莆田、厦门地区有机会线下上门，其他地区线上。微信：Jiabcdefh

方法一：QQ

方法二：微信：Jiabcdefh