AVL 平衡二叉树旋转方法

╰+哭是因爲堅強的太久メ 2024-02-18 21:47 13阅读 0赞

## 1、预备知识 ##

定义树（tree）的一种自然的方式是递归的方式。一棵树使一些节点的集合。这个集合可以是空集；若不是空集，则树由称作**根（root）**的节点 r 以及 0 个或多个非空的（子）树 T1，T2，T3，…，Tk 组成。这些子树每一颗的根都被来自根 r 的一条有向的边所连结。

每一颗子树的根叫做根 r 的**儿子（child）**，而根 r 是每一颗子树的根的**父亲（parent）**。没有儿子的根叫做**树叶（leaf）**。

平衡二叉树的初始高度为 -1，它保证输的深度为 O(logN)。一颗 AVL 树必须满足其每个节点的左子树和右子树的高度差 <= 1。

## 2、不平衡的状况 ##

假设一颗 AVL 树的某个节点为 r，有四种操作会使 r 的左右子树高度差大于 1，从而破坏了原有 AVL 树的平衡性。

1.  对 r 的左儿子的左子树进行一次插入（LL）
2.  对 r 的左儿子的右子树进行一次插入（LR）
3.  对 r 的右儿子的左子树进行一次插入（RL）
4.  对 r 的右儿子的右子树进行一次插入（RR）

其中 1、4 可以归为一类，2、3 可以归为一类。1、4 进行单旋转平衡，2、3 进行双旋转平衡。

## 3、旋转方法 ##

### ①左旋转（LL） ###

![这里写图片描述][SouthEast]

### ②左右双旋转（LR） ###

![这里写图片描述][SouthEast 1]

### ③右左双旋转（RL） ###

![这里写图片描述][SouthEast 2]

### ④右旋转（RR） ###

![这里写图片描述][SouthEast 3]

[SouthEast]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/539af4bccf0d4c188a709e7c5255b179.png
[SouthEast 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/f2c5fd975d8842d0924279a181c9a1b6.png
[SouthEast 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/6a5c1f674a914123aa7834bbc89e67ac.png
[SouthEast 3]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/fa6d9df21ff74afa82e731076d2c70cd.png