7.5 AVL 树 *¶
在“二叉搜索树”章节中我们提到,在多次插入和删除操作后,二叉搜索树可能退化为链表。在这种情况下,所有操作的时间复杂度将从 \(O(\log n)\) 劣化为 \(O(n)\) 。
如图 7-24 所示,经过两次删除节点操作,这棵二叉搜索树便会退化为链表。
图 7-24 AVL 树在删除节点后发生退化
图解 7-24:删除导致搜索树退化
对二叉搜索树连续删除一侧节点而不做平衡维护,会使子树高度差超限并退化为单侧链。
平衡因子是左子树高度减右子树高度,叶节点高度为 0、空子树高度为 −1;每个节点的平衡因子绝对值都不超过 1,树才平衡。以下平衡因子由图中连接计算得出。
三幅子图依次删除 5、3,节点数由 5 减为 4、再减为 3,标为“平衡二叉树”“普通二叉树”“链表”;全过程未做旋转维护。
初始根 4 的左右子节点为 2、5,2 的左右子节点为 1、3。先删去右叶节点 5 后,根 4 的左子树高度为 1,右子树为空、高度为 −1,平衡因子为 1 − (−1) = 2,此时即已失衡。再删去节点 2 的右叶节点 3,便只剩 4 → 2 → 1 的全左链。
数值大小顺序仍成立,但树已退化为链。AVL 树需要在删除后维护平衡。
再例如,在图 7-25 所示的完美二叉树中插入两个节点后,树将严重向左倾斜,查找操作的时间复杂度也随之劣化。
图 7-25 AVL 树在插入节点后发生退化
图解 7-25:插入导致搜索树失衡
向同一侧连续插入节点会逐层拉长分支高度,使原本平衡的二叉树超出平衡条件。
平衡因子是左子树高度减右子树高度,叶节点高度为 0、空子树高度为 −1;每个节点的平衡因子绝对值都不超过 1,树才平衡。以下平衡因子由图中连接计算得出。
本例是未执行旋转维护的普通二叉搜索树。三幅子图依次有 3、4、5 个节点,标为“完美二叉树”“平衡二叉树”“普通二叉树”;根 4 的右子节点始终是叶节点 5。
初始根 4 的左右子节点为 3、5。插入 2 时,2 小于 4 和 3,接到 3 的左侧;虽然最底层不再填满,4 与 3 的平衡因子都只是 1,仍保持平衡。再插入 1 时,沿 4 → 3 → 2 接到 2 的左侧,此时 3 与 4 的平衡因子都变为 2 而失衡。
不再完美不等于失衡。AVL 树会在插入后通过旋转恢复平衡。
1962 年 G. M. Adelson-Velsky 和 E. M. Landis 在论文“An algorithm for the organization of information”中提出了 AVL 树。论文中详细描述了一系列操作,确保在持续添加和删除节点后,AVL 树不会退化,从而使得各种操作的时间复杂度保持在 \(O(\log n)\) 级别。换句话说,在需要频繁进行增删查改操作的场景中,AVL 树能始终保持高效的数据操作性能,具有很好的应用价值。
7.5.1 AVL 树常见术语¶
AVL 树既是二叉搜索树,也是平衡二叉树,同时满足这两类二叉树的所有性质,因此是一种平衡二叉搜索树(balanced binary search tree)。
1. 节点高度¶
由于 AVL 树的相关操作需要获取节点高度,因此我们需要为节点类添加 height 变量:
/* AVL 树节点类 */
class TreeNode {
val; // 节点值
height; //节点高度
left; // 左子节点指针
right; // 右子节点指针
constructor(val, left, right, height) {
this.val = val === undefined ? 0 : val;
this.height = height === undefined ? 0 : height;
this.left = left === undefined ? null : left;
this.right = right === undefined ? null : right;
}
}
/* AVL 树节点类 */
class TreeNode {
val: number; // 节点值
height: number; // 节点高度
left: TreeNode | null; // 左子节点指针
right: TreeNode | null; // 右子节点指针
constructor(val?: number, height?: number, left?: TreeNode | null, right?: TreeNode | null) {
this.val = val === undefined ? 0 : val;
this.height = height === undefined ? 0 : height;
this.left = left === undefined ? null : left;
this.right = right === undefined ? null : right;
}
}
use std::rc::Rc;
use std::cell::RefCell;
/* AVL 树节点结构体 */
struct TreeNode {
val: i32, // 节点值
height: i32, // 节点高度
left: Option<Rc<RefCell<TreeNode>>>, // 左子节点
right: Option<Rc<RefCell<TreeNode>>>, // 右子节点
}
impl TreeNode {
/* 构造方法 */
fn new(val: i32) -> Rc<RefCell<Self>> {
Rc::new(RefCell::new(Self {
val,
height: 0,
left: None,
right: None
}))
}
}
/* AVL 树节点结构体 */
typedef struct TreeNode {
int val;
int height;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
/* 构造函数 */
TreeNode *newTreeNode(int val) {
TreeNode *node;
node = (TreeNode *)malloc(sizeof(TreeNode));
node->val = val;
node->height = 0;
node->left = NULL;
node->right = NULL;
return node;
}
“节点高度”是指从该节点到它的最远叶节点的距离,即所经过的“边”的数量。需要特别注意的是,叶节点的高度为 \(0\) ,而空节点的高度为 \(-1\) 。我们将创建两个工具函数,分别用于获取和更新节点的高度:
/* 获取节点高度 */
func (t *aVLTree) height(node *TreeNode) int {
// 空节点高度为 -1 ,叶节点高度为 0
if node != nil {
return node.Height
}
return -1
}
/* 更新节点高度 */
func (t *aVLTree) updateHeight(node *TreeNode) {
lh := t.height(node.Left)
rh := t.height(node.Right)
// 节点高度等于最高子树高度 + 1
if lh > rh {
node.Height = lh + 1
} else {
node.Height = rh + 1
}
}
/* 获取节点高度 */
fn height(node: OptionTreeNodeRc) -> i32 {
// 空节点高度为 -1 ,叶节点高度为 0
match node {
Some(node) => node.borrow().height,
None => -1,
}
}
/* 更新节点高度 */
fn update_height(node: OptionTreeNodeRc) {
if let Some(node) = node {
let left = node.borrow().left.clone();
let right = node.borrow().right.clone();
// 节点高度等于最高子树高度 + 1
node.borrow_mut().height = std::cmp::max(Self::height(left), Self::height(right)) + 1;
}
}
/* 获取节点高度 */
int height(TreeNode *node) {
// 空节点高度为 -1 ,叶节点高度为 0
if (node != NULL) {
return node->height;
}
return -1;
}
/* 更新节点高度 */
void updateHeight(TreeNode *node) {
int lh = height(node->left);
int rh = height(node->right);
// 节点高度等于最高子树高度 + 1
if (lh > rh) {
node->height = lh + 1;
} else {
node->height = rh + 1;
}
}
2. 节点平衡因子¶
节点的平衡因子(balance factor)定义为节点左子树的高度减去右子树的高度,同时规定空节点的平衡因子为 \(0\) 。我们同样将获取节点平衡因子的功能封装成函数,方便后续使用:
Tip
设平衡因子为 \(f\) ,则一棵 AVL 树的任意节点的平衡因子皆满足 \(-1 \le f \le 1\) 。
7.5.2 AVL 树旋转¶
AVL 树的特点在于“旋转”操作,它能够在不影响二叉树的中序遍历序列的前提下,使失衡节点重新恢复平衡。换句话说,旋转操作既能保持“二叉搜索树”的性质,也能使树重新变为“平衡二叉树”。
我们将平衡因子绝对值 \(> 1\) 的节点称为“失衡节点”。根据节点失衡情况的不同,旋转操作分为四种:右旋、左旋、先右旋后左旋、先左旋后右旋。下面详细介绍这些旋转操作。
1. 右旋¶
如图 7-26 所示,节点下方为平衡因子。从底至顶看,二叉树中首个失衡节点是“节点 3”。我们关注以该失衡节点为根节点的子树,将该节点记为 node ,其左子节点记为 child ,执行“右旋”操作。完成右旋后,子树恢复平衡,并且仍然保持二叉搜索树的性质。
图 7-26 右旋操作步骤
图解 7-26:AVL 树右旋
对首个失衡节点执行右旋,先重连局部子树的父子指针,再将新子树根接回上层父节点。
初始树根为 4,左右子节点为 3、5;3 只有左子节点 1,1 只有左子节点 0;0、5 为叶节点。
平衡因子定义为左子树高度减右子树高度;高度按边数计,叶节点高度为 0,空子树高度为 −1。自底向上检查时,首个失衡节点是 3,记为 node;其左子节点 1 记为 child。
本例 child(1)的右子树为空。代码先保存 grand_child = child.right,再改写 child.right = node,最后将 node.left = grand_child;保存旧引用必须在覆盖之前。
找到首个失衡节点 3
初始根 4 左接 3、右接 5;3 仅左接 1,1 仅左接 0,0、5 为叶节点。节点下方标出的平衡因子为:0、5 是 0,1 是 1,3 和 4 是 2。沿左分支自底向上,首个失衡节点为 3,因此先修复以 3 为根的子树。
标记旋转的两个节点
标记 node=3、child=1,尚未旋转:根 4 仍左接 3、右接 5,3 仅左接 1,1 仅左接 0。child.right 为空,因此保存的 grand_child 为空,旋转后 node.left 也应为空。
形成以 1 为根的局部子树
保存 child 原有的右引用(为空),再令 child.right = node、node.left = grand_child,形成局部子树:根 1 左接 0、右接 3,0、3 为叶节点。图中父节点 4 此时仅右接 5,尚未接到新根 1。旧位置 3 的虚线圆框及其指向 1 的虚线边只作旋转前对照,不是当前连接,整次旋转尚未完成。
将新子树根接回父节点
令 4.left 指向新子树根 1,完成接回:根 4 左接 1、右接 5;1 左接 0、右接 3,0、3、5 为叶节点。局部子树高度下降 1,根 4 的平衡因子从 2 变为 1;全树中序序列仍为 [0, 1, 3, 4, 5]。
局部子树高度下降 1,整棵树恢复 AVL 平衡,二叉搜索树的大小顺序保持不变。
如图 7-27 所示,当节点 child 有右子节点(记为 grand_child )时,需要在右旋中添加一步:将 grand_child 作为 node 的左子节点。
图 7-27 有 grand_child 的右旋操作
图解 7-27:带孙节点的 AVL 右旋
对失衡节点 5 执行右旋,使左子节点 3 升为新根,并将 3 原有的右子节点 4 转接为 5 的左子节点。
初始子树的根节点为 5,左、右子节点分别为 3 和 6;节点 3 的左、右子节点分别为 1 和 4;节点 1 只有左子节点 0。图中将失衡节点 5 记为 node,其左子节点 3 记为 child,3 的右子节点 4 记为 grand_child。
平衡因子是左子树高度减右子树高度,空子树高度为 −1、叶节点为 0。按连接计算,根 5 左高 2、右高 0,平衡因子为 2,需要右旋。
右旋时,左子节点 3 升为子树新根,原根 5 改接到 3 的右侧。由于 3 的右侧原本连着孙节点 4,需先保留 4 的引用,并在旋转中将它转接为 5 的左子节点;因为 3 < 4 < 5,转接后 4 仍处于 3 的右子树且位于 5 的左侧,二叉搜索树的大小顺序保持不变。
对应引用更新依次为:先保存 grand_child = child.right,再令 child.right = node,最后令 node.left = grand_child。节点 1 及其左子节点 0 仍挂在 3 的左侧,节点 6 仍是 5 的右子节点。
静态图从左到右有三幅子图:旋转前、完成右旋与孙节点转接、整理布局。中间子图已完成全部真实连接,5、6 旧位置的浅色虚线及旧连线仅作对照;最后一幅只移除虚线并整理布局,没有第二次旋转。
| 节点 | 旋转前左子 | 旋转前右子 | 旋转后左子 | 旋转后右子 |
|---|---|---|---|---|
| 5 | 3 | 6 | 4 | 6 |
| 3 | 1 | 4 | 1 | 5 |
| 1 | 0 | 无 | 0 | 无 |
| 0 | 无 | 无 | 无 | 无 |
| 4 | 无 | 无 | 无 | 无 |
| 6 | 无 | 无 | 无 | 无 |
旋转后新根 3 的左右子树高度均为 1,恢复平衡;0、4、6 仍为叶节点。
全部节点保留,中序遍历序列仍为 [0, 1, 3, 4, 5, 6]。
“向右旋转”是一种形象化的说法,实际上需要通过修改节点指针来实现,代码如下所示:
/* 右旋操作 */
fn right_rotate(node: OptionTreeNodeRc) -> OptionTreeNodeRc {
match node {
Some(node) => {
let child = node.borrow().left.clone().unwrap();
let grand_child = child.borrow().right.clone();
// 以 child 为原点,将 node 向右旋转
child.borrow_mut().right = Some(node.clone());
node.borrow_mut().left = grand_child;
// 更新节点高度
Self::update_height(Some(node));
Self::update_height(Some(child.clone()));
// 返回旋转后子树的根节点
Some(child)
}
None => None,
}
}
2. 左旋¶
相应地,如果考虑上述失衡二叉树的“镜像”,则需要执行图 7-28 所示的“左旋”操作。
图 7-28 左旋操作
图解 7-28:AVL 左旋与接回父节点
对失衡节点 4 执行左旋,将向右倾斜的链 4 → 5 → 6 调整为以 5 为根、左接 4 且右接 6 的平衡子树。
整棵树的外层根节点为 1,左子节点为 0,右子节点为 4;节点 4 只有右子节点 5,节点 5 只有右子节点 6。图中将失衡节点 4 记为 node,其右子节点 5 记为 child。
平衡因子是左子树高度减右子树高度,叶节点高度为 0、空子树高度为 −1;每个节点的平衡因子绝对值都不超过 1,树才平衡。以下平衡因子由图中连接计算得出。
三幅子图依次展示旋转前、局部旋转后和接回父节点后,并非逐条赋值的代码快照。初始节点 4 的左子树高度为 −1、右子树高度为 1,平衡因子为 −2;外层根 1 的平衡因子也是 −2。
左旋使 5 升为局部根,4 成为其左子节点,6 仍为右子节点。5 原本没有左子节点,所以旋转后 4 的右子节点为空。
中间画面的实线只有 1→0、5→4、5→6;父节点 1 到新根 5 尚无实线连接。另有节点 4 原位置的虚线圆框及从该旧位置指向 5 的虚线边,只作旋转前对照,不是额外节点或当前连接。最后一幅才画出 1→5,并移除虚线。
| 节点 | 旋转前左子 | 旋转前右子 | 接回父节点后左子 | 接回父节点后右子 |
|---|---|---|---|---|
| 1 | 0 | 4 | 0 | 5 |
| 4 | 无 | 5 | 无 | 无 |
| 5 | 无 | 6 | 4 | 6 |
| 0 | 无 | 无 | 无 | 无 |
| 6 | 无 | 无 | 无 | 无 |
把新子树根接回后,父节点 1 的右侧子树高度从 2 降为 1;其左子节点 0 保持不变,整棵树恢复平衡。
全部父子关系的前后对照见表,中序遍历序列保持 [0, 1, 4, 5, 6]。
同理,如图 7-29 所示,当节点 child 有左子节点(记为 grand_child )时,需要在左旋中添加一步:将 grand_child 作为 node 的右子节点。
图 7-29 有 grand_child 的左旋操作
图解 7-29:带孙节点的 AVL 左旋
左旋提升失衡节点的右子节点,并将该右子节点原有的左子节点转接到下移节点的右侧,恢复平衡且保持二叉搜索树有序。
旋转前树中共有 6 个节点:根 1 左接 0、右接 4;节点 4 左接 3、右接 5;节点 5 左空、右接 6;0、3、6 为叶节点。图中变量 node 指向失衡根节点 1,child 指向其右子节点 4,grand_child 指向 4 的左子节点 3。
平衡因子是左子树高度减右子树高度,叶节点高度为 0、空子树高度为 −1;每个节点的平衡因子绝对值都不超过 1,树才平衡。以下平衡因子由图中连接计算得出。
旋转前根 1 的左子树高度为 0、右子树高度为 2,平衡因子为 −2,需要左旋。
静态图从左到右有三幅子图:旋转前、完成左旋与孙节点转接、移除旧位置虚线并整理布局。
左旋将 child(节点 4)提升为新根,并将 node(节点 1)降为 4 的左子节点。此时节点 4 原有的左子位置被节点 1 占据,原本位于 4 左侧的孙节点 3 必须让出位置;由于 1 < 3 < 4,将节点 3 改接到节点 1 的右侧,仍严格满足二叉搜索树左小右大的顺序。
| 节点 | 旋转前左子节点 | 旋转前右子节点 | 旋转后左子节点 | 旋转后右子节点 |
|---|---|---|---|---|
| 1 | 0 | 4 | 0 | 3 |
| 4 | 3 | 5 | 1 | 5 |
| 5 | 无 | 6 | 无 | 6 |
| 0 | 无 | 无 | 无 | 无 |
| 3 | 无 | 无 | 无 | 无 |
| 6 | 无 | 无 | 无 | 无 |
指针调整顺序为:先以 grand_child = child.left 保存节点 3,再令 child.left = node 将 1 接为 4 的左子节点,最后令 node.right = grand_child 将 3 接为 1 的右子节点。节点 0 仍为 1 的左子节点,节点 5 及其右子节点 6 仍位于 4 的右侧。中间子图用浅色虚线标出节点 1 与 0 旋转前的原位置,旧位置 1 还以虚线连向旧位置 0 和节点 4;这些虚线仅作位移对照,不代表新增节点;最后一幅只移除虚线并整理树形布局,没有再次旋转。
左旋后以节点 4 为新根,左右子树高度均为 1,整棵树恢复平衡;全部 6 个节点的中序遍历序列保持 [0, 1, 3, 4, 5, 6] 不变。
可以观察到,右旋和左旋操作在逻辑上是镜像对称的,它们分别解决的两种失衡情况也是对称的。基于对称性,我们只需将右旋的实现代码中的所有的 left 替换为 right ,将所有的 right 替换为 left ,即可得到左旋的实现代码:
/* 左旋操作 */
fn left_rotate(node: OptionTreeNodeRc) -> OptionTreeNodeRc {
match node {
Some(node) => {
let child = node.borrow().right.clone().unwrap();
let grand_child = child.borrow().left.clone();
// 以 child 为原点,将 node 向左旋转
child.borrow_mut().left = Some(node.clone());
node.borrow_mut().right = grand_child;
// 更新节点高度
Self::update_height(Some(node));
Self::update_height(Some(child.clone()));
// 返回旋转后子树的根节点
Some(child)
}
None => None,
}
}
3. 先左旋后右旋¶
对于图 7-30 中的失衡节点 3 ,仅使用左旋或右旋都无法使子树恢复平衡。此时需要先对 child 执行“左旋”,再对 node 执行“右旋”。
图 7-30 先左旋后右旋
图解 7-30:AVL 树先左旋后右旋
针对先向左再向右弯折的路径 3 → 1 → 2,先对 child(1)执行左旋,再对 node(3)执行右旋,使 2 成为局部新根。
外层根节点为 4,右子节点为 5,左子节点为失衡节点 3;节点 3 只有左子节点 1,节点 1 只有右子节点 2。图中将失衡节点 3 记为 node,其左子节点 1 记为 child。
平衡因子是左子树高度减右子树高度,叶节点高度为 0、空子树高度为 −1;每个节点的平衡因子绝对值都不超过 1,树才平衡。以下平衡因子由图中连接计算得出。
据此计算,node(3)的平衡因子为 2,child(1)为 −1;外层根 4 的平衡因子也为 2。图中从最低的失衡节点 3 开始修复,完成后外层根随之恢复平衡。
静态图从左到右有三幅子图:旋转前、第一次旋转完成、第二次旋转完成。
第一次旋转:对 child(节点 1)执行左旋:节点 2 上升为这棵小子树的根,节点 1 降为 2 的左子节点,节点 3 的左子节点随之变为 2。如中间子图所示,原本弯折的路径被拉直为连续向左倾斜的路径 3 → 2 → 1。
第二次旋转:对原失衡节点 node(节点 3)执行右旋:节点 2 继续上升为局部子树的根,节点 3 降为 2 的右子节点,节点 1 保持为 2 的左子节点。外层父节点 4 的左子节点更新为 2,右子节点 5 保持不变。
对于这种“左-右”弯折形态,若直接对节点 3 做单次右旋,仍会留下新的失衡;只有先通过左旋把局部形态转化为“左-左”同向倾斜,再执行右旋,才能让节点 1、2、3 均匀分布在两侧。
两次旋转后整棵树恢复平衡,中序遍历序列保持 [1, 2, 3, 4, 5]。
4. 先右旋后左旋¶
如图 7-31 所示,对于上述失衡二叉树的镜像情况,需要先对 child 执行“右旋”,再对 node 执行“左旋”。
图 7-31 先右旋后左旋
图解 7-31:AVL 树先右旋后左旋
针对先向右再向左弯折的路径 3 → 5 → 4,先对 child(5)执行右旋,再对 node(3)执行左旋,使 4 成为局部新根。
外层根节点为 2,左子节点为 1,右子节点为失衡节点 3;节点 3 只有右子节点 5,节点 5 只有左子节点 4。图中将失衡节点 3 记为 node,其右子节点 5 记为 child。
平衡因子是左子树高度减右子树高度,叶节点高度为 0、空子树高度为 −1;每个节点的平衡因子绝对值都不超过 1,树才平衡。以下平衡因子由图中连接计算得出。
据此计算,node(3)的平衡因子为 −2,child(5)为 1;外层根 2 的平衡因子也为 −2。图中从最低的失衡节点 3 开始修复,完成后外层根随之恢复平衡。
静态图从左到右有三幅子图:旋转前、第一次旋转完成、第二次旋转完成。
第一次旋转:对 child(节点 5)执行右旋:节点 4 上升为这棵小子树的根,节点 5 降为 4 的右子节点,节点 3 的右子节点随之变为 4。如中间子图所示,原本弯折的路径被拉直为连续向右倾斜的路径 3 → 4 → 5。
第二次旋转:对原失衡节点 node(节点 3)执行左旋:节点 4 继续上升为局部子树的根,节点 3 降为 4 的左子节点,节点 5 保持为 4 的右子节点。外层父节点 2 的右子节点更新为 4,左子节点 1 保持不变。
这一过程与“先左旋后右旋”互为镜像:先纠正子节点子树的反向弯折,使其与失衡方向一致,再旋转失衡节点,即可在恢复平衡的同时保持所有节点的大小次序。
两次旋转后整棵树恢复平衡,中序遍历序列保持 [1, 2, 3, 4, 5]。
5. 旋转的选择¶
图 7-32 展示的四种失衡情况与上述案例逐个对应,分别需要采用右旋、先左旋后右旋、先右旋后左旋、左旋的操作。
图 7-32 AVL 树的四种旋转情况
图解 7-32:AVL 树的四种失衡形状与旋转选择
四种旋转前的局部树形,对应单旋或双旋两类修复方法。
四幅子图中,橙色节点 3 均为待修复的失衡节点,蓝色节点是它较高一侧的子节点,绿色节点标示子树继续延伸的方向;灰色圆角背景框圈出需要旋转调整的局部失衡子树。
平衡因子 f 是左子树高度减右子树高度。下表分别列出失衡节点 3 及其较高侧子节点的 f,供逐行核对选择依据。
从左到右排列四个旋转前案例:前两幅图的外层根节点均为 4、右子节点为 5,左侧挂着以 3 为根的失衡子树;后两幅图的外层根节点均为 2、左子节点为 1,右侧挂着以 3 为根的失衡子树。四种局部连接形态及下方标注的旋转方法汇总于数据表。表中“左左”等分类名用于概括两层分支方向;节点值、连线和旋转方法来自图面,平衡因子数值按叶高 0、空子树高 −1 推算,并非图上标注。
| 情况 | 失衡子树内的路径 | 节点 3 的 f(推算) | 较高侧子节点的 f(推算) | 旋转对象与次序 |
|---|---|---|---|---|
| 左左 | 3 的左子节点是 1,1 的左子节点是 0 | 2 | 1 | 对 3 右旋 |
| 左右 | 3 的左子节点是 1,1 的右子节点是 2 | 2 | −1 | 先对 1 左旋,再对 3 右旋 |
| 右左 | 3 的右子节点是 5,5 的左子节点是 4 | −2 | 1 | 先对 5 右旋,再对 3 左旋 |
| 右右 | 3 的右子节点是 5,5 的右子节点是 6 | −2 | −1 | 对 3 左旋 |
结合正文的通用规则:失衡节点 f > 1 时,检查左子节点;其 f ≥ 0 则直接右旋,f < 0 则先对左子节点左旋、再对失衡节点右旋。失衡节点 f < −1 时,检查右子节点;其 f ≤ 0 则直接左旋,f > 0 则先对右子节点右旋、再对失衡节点左旋。子节点 f = 0 也属于通用规则,例如删除后可能出现。
同向倾斜用单旋,反向弯折先旋转子节点再旋转失衡节点;中序次序保持不变。
如下表所示,我们通过判断失衡节点的平衡因子以及较高一侧子节点的平衡因子的正负号,来确定失衡节点属于图 7-32 中的哪种情况。
表 7-3 四种旋转情况的选择条件
| 失衡节点的平衡因子 | 子节点的平衡因子 | 应采用的旋转方法 |
|---|---|---|
| \(> 1\) (左偏树) | \(\geq 0\) | 右旋 |
| \(> 1\) (左偏树) | \(<0\) | 先左旋后右旋 |
| \(< -1\) (右偏树) | \(\leq 0\) | 左旋 |
| \(< -1\) (右偏树) | \(>0\) | 先右旋后左旋 |
为了便于使用,我们将旋转操作封装成一个函数。有了这个函数,我们就能对各种失衡情况进行旋转,使失衡节点重新恢复平衡。代码如下所示:
def rotate(self, node: TreeNode | None) -> TreeNode | None:
"""执行旋转操作,使该子树重新恢复平衡"""
# 获取节点 node 的平衡因子
balance_factor = self.balance_factor(node)
# 左偏树
if balance_factor > 1:
if self.balance_factor(node.left) >= 0:
# 右旋
return self.right_rotate(node)
else:
# 先左旋后右旋
node.left = self.left_rotate(node.left)
return self.right_rotate(node)
# 右偏树
elif balance_factor < -1:
if self.balance_factor(node.right) <= 0:
# 左旋
return self.left_rotate(node)
else:
# 先右旋后左旋
node.right = self.right_rotate(node.right)
return self.left_rotate(node)
# 平衡树,无须旋转,直接返回
return node
/* 执行旋转操作,使该子树重新恢复平衡 */
TreeNode *rotate(TreeNode *node) {
// 获取节点 node 的平衡因子
int _balanceFactor = balanceFactor(node);
// 左偏树
if (_balanceFactor > 1) {
if (balanceFactor(node->left) >= 0) {
// 右旋
return rightRotate(node);
} else {
// 先左旋后右旋
node->left = leftRotate(node->left);
return rightRotate(node);
}
}
// 右偏树
if (_balanceFactor < -1) {
if (balanceFactor(node->right) <= 0) {
// 左旋
return leftRotate(node);
} else {
// 先右旋后左旋
node->right = rightRotate(node->right);
return leftRotate(node);
}
}
// 平衡树,无须旋转,直接返回
return node;
}
/* 执行旋转操作,使该子树重新恢复平衡 */
TreeNode rotate(TreeNode node) {
// 获取节点 node 的平衡因子
int balanceFactor = balanceFactor(node);
// 左偏树
if (balanceFactor > 1) {
if (balanceFactor(node.left) >= 0) {
// 右旋
return rightRotate(node);
} else {
// 先左旋后右旋
node.left = leftRotate(node.left);
return rightRotate(node);
}
}
// 右偏树
if (balanceFactor < -1) {
if (balanceFactor(node.right) <= 0) {
// 左旋
return leftRotate(node);
} else {
// 先右旋后左旋
node.right = rightRotate(node.right);
return leftRotate(node);
}
}
// 平衡树,无须旋转,直接返回
return node;
}
/* 执行旋转操作,使该子树重新恢复平衡 */
TreeNode? Rotate(TreeNode? node) {
// 获取节点 node 的平衡因子
int balanceFactorInt = BalanceFactor(node);
// 左偏树
if (balanceFactorInt > 1) {
if (BalanceFactor(node?.left) >= 0) {
// 右旋
return RightRotate(node);
} else {
// 先左旋后右旋
node!.left = LeftRotate(node!.left);
return RightRotate(node);
}
}
// 右偏树
if (balanceFactorInt < -1) {
if (BalanceFactor(node?.right) <= 0) {
// 左旋
return LeftRotate(node);
} else {
// 先右旋后左旋
node!.right = RightRotate(node!.right);
return LeftRotate(node);
}
}
// 平衡树,无须旋转,直接返回
return node;
}
/* 执行旋转操作,使该子树重新恢复平衡 */
func (t *aVLTree) rotate(node *TreeNode) *TreeNode {
// 获取节点 node 的平衡因子
// Go 推荐短变量,这里 bf 指代 t.balanceFactor
bf := t.balanceFactor(node)
// 左偏树
if bf > 1 {
if t.balanceFactor(node.Left) >= 0 {
// 右旋
return t.rightRotate(node)
} else {
// 先左旋后右旋
node.Left = t.leftRotate(node.Left)
return t.rightRotate(node)
}
}
// 右偏树
if bf < -1 {
if t.balanceFactor(node.Right) <= 0 {
// 左旋
return t.leftRotate(node)
} else {
// 先右旋后左旋
node.Right = t.rightRotate(node.Right)
return t.leftRotate(node)
}
}
// 平衡树,无须旋转,直接返回
return node
}
/* 执行旋转操作,使该子树重新恢复平衡 */
func rotate(node: TreeNode?) -> TreeNode? {
// 获取节点 node 的平衡因子
let balanceFactor = balanceFactor(node: node)
// 左偏树
if balanceFactor > 1 {
if self.balanceFactor(node: node?.left) >= 0 {
// 右旋
return rightRotate(node: node)
} else {
// 先左旋后右旋
node?.left = leftRotate(node: node?.left)
return rightRotate(node: node)
}
}
// 右偏树
if balanceFactor < -1 {
if self.balanceFactor(node: node?.right) <= 0 {
// 左旋
return leftRotate(node: node)
} else {
// 先右旋后左旋
node?.right = rightRotate(node: node?.right)
return leftRotate(node: node)
}
}
// 平衡树,无须旋转,直接返回
return node
}
/* 执行旋转操作,使该子树重新恢复平衡 */
#rotate(node) {
// 获取节点 node 的平衡因子
const balanceFactor = this.balanceFactor(node);
// 左偏树
if (balanceFactor > 1) {
if (this.balanceFactor(node.left) >= 0) {
// 右旋
return this.#rightRotate(node);
} else {
// 先左旋后右旋
node.left = this.#leftRotate(node.left);
return this.#rightRotate(node);
}
}
// 右偏树
if (balanceFactor < -1) {
if (this.balanceFactor(node.right) <= 0) {
// 左旋
return this.#leftRotate(node);
} else {
// 先右旋后左旋
node.right = this.#rightRotate(node.right);
return this.#leftRotate(node);
}
}
// 平衡树,无须旋转,直接返回
return node;
}
/* 执行旋转操作,使该子树重新恢复平衡 */
rotate(node: TreeNode): TreeNode {
// 获取节点 node 的平衡因子
const balanceFactor = this.balanceFactor(node);
// 左偏树
if (balanceFactor > 1) {
if (this.balanceFactor(node.left) >= 0) {
// 右旋
return this.rightRotate(node);
} else {
// 先左旋后右旋
node.left = this.leftRotate(node.left);
return this.rightRotate(node);
}
}
// 右偏树
if (balanceFactor < -1) {
if (this.balanceFactor(node.right) <= 0) {
// 左旋
return this.leftRotate(node);
} else {
// 先右旋后左旋
node.right = this.rightRotate(node.right);
return this.leftRotate(node);
}
}
// 平衡树,无须旋转,直接返回
return node;
}
/* 执行旋转操作,使该子树重新恢复平衡 */
TreeNode? rotate(TreeNode? node) {
// 获取节点 node 的平衡因子
int factor = balanceFactor(node);
// 左偏树
if (factor > 1) {
if (balanceFactor(node!.left) >= 0) {
// 右旋
return rightRotate(node);
} else {
// 先左旋后右旋
node.left = leftRotate(node.left);
return rightRotate(node);
}
}
// 右偏树
if (factor < -1) {
if (balanceFactor(node!.right) <= 0) {
// 左旋
return leftRotate(node);
} else {
// 先右旋后左旋
node.right = rightRotate(node.right);
return leftRotate(node);
}
}
// 平衡树,无须旋转,直接返回
return node;
}
/* 执行旋转操作,使该子树重新恢复平衡 */
fn rotate(node: OptionTreeNodeRc) -> OptionTreeNodeRc {
// 获取节点 node 的平衡因子
let balance_factor = Self::balance_factor(node.clone());
// 左偏树
if balance_factor > 1 {
let node = node.unwrap();
if Self::balance_factor(node.borrow().left.clone()) >= 0 {
// 右旋
Self::right_rotate(Some(node))
} else {
// 先左旋后右旋
let left = node.borrow().left.clone();
node.borrow_mut().left = Self::left_rotate(left);
Self::right_rotate(Some(node))
}
}
// 右偏树
else if balance_factor < -1 {
let node = node.unwrap();
if Self::balance_factor(node.borrow().right.clone()) <= 0 {
// 左旋
Self::left_rotate(Some(node))
} else {
// 先右旋后左旋
let right = node.borrow().right.clone();
node.borrow_mut().right = Self::right_rotate(right);
Self::left_rotate(Some(node))
}
} else {
// 平衡树,无须旋转,直接返回
node
}
}
/* 执行旋转操作,使该子树重新恢复平衡 */
TreeNode *rotate(TreeNode *node) {
// 获取节点 node 的平衡因子
int bf = balanceFactor(node);
// 左偏树
if (bf > 1) {
if (balanceFactor(node->left) >= 0) {
// 右旋
return rightRotate(node);
} else {
// 先左旋后右旋
node->left = leftRotate(node->left);
return rightRotate(node);
}
}
// 右偏树
if (bf < -1) {
if (balanceFactor(node->right) <= 0) {
// 左旋
return leftRotate(node);
} else {
// 先右旋后左旋
node->right = rightRotate(node->right);
return leftRotate(node);
}
}
// 平衡树,无须旋转,直接返回
return node;
}
/* 执行旋转操作,使该子树重新恢复平衡 */
fun rotate(node: TreeNode): TreeNode {
// 获取节点 node 的平衡因子
val balanceFactor = balanceFactor(node)
// 左偏树
if (balanceFactor > 1) {
if (balanceFactor(node.left) >= 0) {
// 右旋
return rightRotate(node)
} else {
// 先左旋后右旋
node.left = leftRotate(node.left)
return rightRotate(node)
}
}
// 右偏树
if (balanceFactor < -1) {
if (balanceFactor(node.right) <= 0) {
// 左旋
return leftRotate(node)
} else {
// 先右旋后左旋
node.right = rightRotate(node.right)
return leftRotate(node)
}
}
// 平衡树,无须旋转,直接返回
return node
}
### 执行旋转操作,使该子树重新恢复平衡 ###
def rotate(node)
# 获取节点 node 的平衡因子
balance_factor = balance_factor(node)
# 左遍树
if balance_factor > 1
if balance_factor(node.left) >= 0
# 右旋
return right_rotate(node)
else
# 先左旋后右旋
node.left = left_rotate(node.left)
return right_rotate(node)
end
# 右遍树
elsif balance_factor < -1
if balance_factor(node.right) <= 0
# 左旋
return left_rotate(node)
else
# 先右旋后左旋
node.right = right_rotate(node.right)
return left_rotate(node)
end
end
# 平衡树,无须旋转,直接返回
node
end
7.5.3 AVL 树常用操作¶
1. 插入节点¶
AVL 树的节点插入操作与二叉搜索树在主体上类似。唯一的区别在于,在 AVL 树中插入节点后,从该节点到根节点的路径上可能会出现一系列失衡节点。因此,我们需要从这个节点开始,自底向上执行旋转操作,使所有失衡节点恢复平衡。代码如下所示:
def insert(self, val):
"""插入节点"""
self._root = self.insert_helper(self._root, val)
def insert_helper(self, node: TreeNode | None, val: int) -> TreeNode:
"""递归插入节点(辅助方法)"""
if node is None:
return TreeNode(val)
# 1. 查找插入位置并插入节点
if val < node.val:
node.left = self.insert_helper(node.left, val)
elif val > node.val:
node.right = self.insert_helper(node.right, val)
else:
# 重复节点不插入,直接返回
return node
# 更新节点高度
self.update_height(node)
# 2. 执行旋转操作,使该子树重新恢复平衡
return self.rotate(node)
/* 插入节点 */
void insert(int val) {
root = insertHelper(root, val);
}
/* 递归插入节点(辅助方法) */
TreeNode *insertHelper(TreeNode *node, int val) {
if (node == nullptr)
return new TreeNode(val);
/* 1. 查找插入位置并插入节点 */
if (val < node->val)
node->left = insertHelper(node->left, val);
else if (val > node->val)
node->right = insertHelper(node->right, val);
else
return node; // 重复节点不插入,直接返回
updateHeight(node); // 更新节点高度
/* 2. 执行旋转操作,使该子树重新恢复平衡 */
node = rotate(node);
// 返回子树的根节点
return node;
}
/* 插入节点 */
void insert(int val) {
root = insertHelper(root, val);
}
/* 递归插入节点(辅助方法) */
TreeNode insertHelper(TreeNode node, int val) {
if (node == null)
return new TreeNode(val);
/* 1. 查找插入位置并插入节点 */
if (val < node.val)
node.left = insertHelper(node.left, val);
else if (val > node.val)
node.right = insertHelper(node.right, val);
else
return node; // 重复节点不插入,直接返回
updateHeight(node); // 更新节点高度
/* 2. 执行旋转操作,使该子树重新恢复平衡 */
node = rotate(node);
// 返回子树的根节点
return node;
}
/* 插入节点 */
void Insert(int val) {
root = InsertHelper(root, val);
}
/* 递归插入节点(辅助方法) */
TreeNode? InsertHelper(TreeNode? node, int val) {
if (node == null) return new TreeNode(val);
/* 1. 查找插入位置并插入节点 */
if (val < node.val)
node.left = InsertHelper(node.left, val);
else if (val > node.val)
node.right = InsertHelper(node.right, val);
else
return node; // 重复节点不插入,直接返回
UpdateHeight(node); // 更新节点高度
/* 2. 执行旋转操作,使该子树重新恢复平衡 */
node = Rotate(node);
// 返回子树的根节点
return node;
}
/* 插入节点 */
func (t *aVLTree) insert(val int) {
t.root = t.insertHelper(t.root, val)
}
/* 递归插入节点(辅助函数) */
func (t *aVLTree) insertHelper(node *TreeNode, val int) *TreeNode {
if node == nil {
return NewTreeNode(val)
}
/* 1. 查找插入位置并插入节点 */
if val < node.Val.(int) {
node.Left = t.insertHelper(node.Left, val)
} else if val > node.Val.(int) {
node.Right = t.insertHelper(node.Right, val)
} else {
// 重复节点不插入,直接返回
return node
}
// 更新节点高度
t.updateHeight(node)
/* 2. 执行旋转操作,使该子树重新恢复平衡 */
node = t.rotate(node)
// 返回子树的根节点
return node
}
/* 插入节点 */
func insert(val: Int) {
root = insertHelper(node: root, val: val)
}
/* 递归插入节点(辅助方法) */
func insertHelper(node: TreeNode?, val: Int) -> TreeNode? {
var node = node
if node == nil {
return TreeNode(x: val)
}
/* 1. 查找插入位置并插入节点 */
if val < node!.val {
node?.left = insertHelper(node: node?.left, val: val)
} else if val > node!.val {
node?.right = insertHelper(node: node?.right, val: val)
} else {
return node // 重复节点不插入,直接返回
}
updateHeight(node: node) // 更新节点高度
/* 2. 执行旋转操作,使该子树重新恢复平衡 */
node = rotate(node: node)
// 返回子树的根节点
return node
}
/* 插入节点 */
insert(val) {
this.root = this.#insertHelper(this.root, val);
}
/* 递归插入节点(辅助方法) */
#insertHelper(node, val) {
if (node === null) return new TreeNode(val);
/* 1. 查找插入位置并插入节点 */
if (val < node.val) node.left = this.#insertHelper(node.left, val);
else if (val > node.val)
node.right = this.#insertHelper(node.right, val);
else return node; // 重复节点不插入,直接返回
this.#updateHeight(node); // 更新节点高度
/* 2. 执行旋转操作,使该子树重新恢复平衡 */
node = this.#rotate(node);
// 返回子树的根节点
return node;
}
/* 插入节点 */
insert(val: number): void {
this.root = this.insertHelper(this.root, val);
}
/* 递归插入节点(辅助方法) */
insertHelper(node: TreeNode, val: number): TreeNode {
if (node === null) return new TreeNode(val);
/* 1. 查找插入位置并插入节点 */
if (val < node.val) {
node.left = this.insertHelper(node.left, val);
} else if (val > node.val) {
node.right = this.insertHelper(node.right, val);
} else {
return node; // 重复节点不插入,直接返回
}
this.updateHeight(node); // 更新节点高度
/* 2. 执行旋转操作,使该子树重新恢复平衡 */
node = this.rotate(node);
// 返回子树的根节点
return node;
}
/* 插入节点 */
void insert(int val) {
root = insertHelper(root, val);
}
/* 递归插入节点(辅助方法) */
TreeNode? insertHelper(TreeNode? node, int val) {
if (node == null) return TreeNode(val);
/* 1. 查找插入位置并插入节点 */
if (val < node.val)
node.left = insertHelper(node.left, val);
else if (val > node.val)
node.right = insertHelper(node.right, val);
else
return node; // 重复节点不插入,直接返回
updateHeight(node); // 更新节点高度
/* 2. 执行旋转操作,使该子树重新恢复平衡 */
node = rotate(node);
// 返回子树的根节点
return node;
}
/* 插入节点 */
fn insert(&mut self, val: i32) {
self.root = Self::insert_helper(self.root.clone(), val);
}
/* 递归插入节点(辅助方法) */
fn insert_helper(node: OptionTreeNodeRc, val: i32) -> OptionTreeNodeRc {
match node {
Some(mut node) => {
/* 1. 查找插入位置并插入节点 */
match {
let node_val = node.borrow().val;
node_val
}
.cmp(&val)
{
Ordering::Greater => {
let left = node.borrow().left.clone();
node.borrow_mut().left = Self::insert_helper(left, val);
}
Ordering::Less => {
let right = node.borrow().right.clone();
node.borrow_mut().right = Self::insert_helper(right, val);
}
Ordering::Equal => {
return Some(node); // 重复节点不插入,直接返回
}
}
Self::update_height(Some(node.clone())); // 更新节点高度
/* 2. 执行旋转操作,使该子树重新恢复平衡 */
node = Self::rotate(Some(node)).unwrap();
// 返回子树的根节点
Some(node)
}
None => Some(TreeNode::new(val)),
}
}
/* 插入节点 */
void insert(AVLTree *tree, int val) {
tree->root = insertHelper(tree->root, val);
}
/* 递归插入节点(辅助函数) */
TreeNode *insertHelper(TreeNode *node, int val) {
if (node == NULL) {
return newTreeNode(val);
}
/* 1. 查找插入位置并插入节点 */
if (val < node->val) {
node->left = insertHelper(node->left, val);
} else if (val > node->val) {
node->right = insertHelper(node->right, val);
} else {
// 重复节点不插入,直接返回
return node;
}
// 更新节点高度
updateHeight(node);
/* 2. 执行旋转操作,使该子树重新恢复平衡 */
node = rotate(node);
// 返回子树的根节点
return node;
}
/* 插入节点 */
fun insert(_val: Int) {
root = insertHelper(root, _val)
}
/* 递归插入节点(辅助方法) */
fun insertHelper(n: TreeNode?, _val: Int): TreeNode {
if (n == null)
return TreeNode(_val)
var node = n
/* 1. 查找插入位置并插入节点 */
if (_val < node._val)
node.left = insertHelper(node.left, _val)
else if (_val > node._val)
node.right = insertHelper(node.right, _val)
else
return node // 重复节点不插入,直接返回
updateHeight(node) // 更新节点高度
/* 2. 执行旋转操作,使该子树重新恢复平衡 */
node = rotate(node)
// 返回子树的根节点
return node
}
### 插入节点 ###
def insert(val)
@root = insert_helper(@root, val)
end
### 递归插入节点(辅助方法)###
def insert_helper(node, val)
return TreeNode.new(val) if node.nil?
# 1. 查找插入位置并插入节点
if val < node.val
node.left = insert_helper(node.left, val)
elsif val > node.val
node.right = insert_helper(node.right, val)
else
# 重复节点不插入,直接返回
return node
end
# 更新节点高度
update_height(node)
# 2. 执行旋转操作,使该子树重新恢复平衡
rotate(node)
end
2. 删除节点¶
类似地,在二叉搜索树的删除节点方法的基础上,需要从底至顶执行旋转操作,使所有失衡节点恢复平衡。代码如下所示:
def remove(self, val: int):
"""删除节点"""
self._root = self.remove_helper(self._root, val)
def remove_helper(self, node: TreeNode | None, val: int) -> TreeNode | None:
"""递归删除节点(辅助方法)"""
if node is None:
return None
# 1. 查找节点并删除
if val < node.val:
node.left = self.remove_helper(node.left, val)
elif val > node.val:
node.right = self.remove_helper(node.right, val)
else:
if node.left is None or node.right is None:
child = node.left or node.right
# 子节点数量 = 0 ,直接删除 node 并返回
if child is None:
return None
# 子节点数量 = 1 ,直接删除 node
else:
node = child
else:
# 子节点数量 = 2 ,则将中序遍历的下个节点删除,并用该节点替换当前节点
temp = node.right
while temp.left is not None:
temp = temp.left
node.right = self.remove_helper(node.right, temp.val)
node.val = temp.val
# 更新节点高度
self.update_height(node)
# 2. 执行旋转操作,使该子树重新恢复平衡
return self.rotate(node)
/* 删除节点 */
void remove(int val) {
root = removeHelper(root, val);
}
/* 递归删除节点(辅助方法) */
TreeNode *removeHelper(TreeNode *node, int val) {
if (node == nullptr)
return nullptr;
/* 1. 查找节点并删除 */
if (val < node->val)
node->left = removeHelper(node->left, val);
else if (val > node->val)
node->right = removeHelper(node->right, val);
else {
if (node->left == nullptr || node->right == nullptr) {
TreeNode *child = node->left != nullptr ? node->left : node->right;
// 子节点数量 = 0 ,直接删除 node 并返回
if (child == nullptr) {
delete node;
return nullptr;
}
// 子节点数量 = 1 ,直接删除 node
else {
delete node;
node = child;
}
} else {
// 子节点数量 = 2 ,则将中序遍历的下个节点删除,并用该节点替换当前节点
TreeNode *temp = node->right;
while (temp->left != nullptr) {
temp = temp->left;
}
int tempVal = temp->val;
node->right = removeHelper(node->right, temp->val);
node->val = tempVal;
}
}
updateHeight(node); // 更新节点高度
/* 2. 执行旋转操作,使该子树重新恢复平衡 */
node = rotate(node);
// 返回子树的根节点
return node;
}
/* 删除节点 */
void remove(int val) {
root = removeHelper(root, val);
}
/* 递归删除节点(辅助方法) */
TreeNode removeHelper(TreeNode node, int val) {
if (node == null)
return null;
/* 1. 查找节点并删除 */
if (val < node.val)
node.left = removeHelper(node.left, val);
else if (val > node.val)
node.right = removeHelper(node.right, val);
else {
if (node.left == null || node.right == null) {
TreeNode child = node.left != null ? node.left : node.right;
// 子节点数量 = 0 ,直接删除 node 并返回
if (child == null)
return null;
// 子节点数量 = 1 ,直接删除 node
else
node = child;
} else {
// 子节点数量 = 2 ,则将中序遍历的下个节点删除,并用该节点替换当前节点
TreeNode temp = node.right;
while (temp.left != null) {
temp = temp.left;
}
node.right = removeHelper(node.right, temp.val);
node.val = temp.val;
}
}
updateHeight(node); // 更新节点高度
/* 2. 执行旋转操作,使该子树重新恢复平衡 */
node = rotate(node);
// 返回子树的根节点
return node;
}
/* 删除节点 */
void Remove(int val) {
root = RemoveHelper(root, val);
}
/* 递归删除节点(辅助方法) */
TreeNode? RemoveHelper(TreeNode? node, int val) {
if (node == null) return null;
/* 1. 查找节点并删除 */
if (val < node.val)
node.left = RemoveHelper(node.left, val);
else if (val > node.val)
node.right = RemoveHelper(node.right, val);
else {
if (node.left == null || node.right == null) {
TreeNode? child = node.left ?? node.right;
// 子节点数量 = 0 ,直接删除 node 并返回
if (child == null)
return null;
// 子节点数量 = 1 ,直接删除 node
else
node = child;
} else {
// 子节点数量 = 2 ,则将中序遍历的下个节点删除,并用该节点替换当前节点
TreeNode? temp = node.right;
while (temp.left != null) {
temp = temp.left;
}
node.right = RemoveHelper(node.right, temp.val!.Value);
node.val = temp.val;
}
}
UpdateHeight(node); // 更新节点高度
/* 2. 执行旋转操作,使该子树重新恢复平衡 */
node = Rotate(node);
// 返回子树的根节点
return node;
}
/* 删除节点 */
func (t *aVLTree) remove(val int) {
t.root = t.removeHelper(t.root, val)
}
/* 递归删除节点(辅助函数) */
func (t *aVLTree) removeHelper(node *TreeNode, val int) *TreeNode {
if node == nil {
return nil
}
/* 1. 查找节点并删除 */
if val < node.Val.(int) {
node.Left = t.removeHelper(node.Left, val)
} else if val > node.Val.(int) {
node.Right = t.removeHelper(node.Right, val)
} else {
if node.Left == nil || node.Right == nil {
child := node.Left
if node.Right != nil {
child = node.Right
}
if child == nil {
// 子节点数量 = 0 ,直接删除 node 并返回
return nil
} else {
// 子节点数量 = 1 ,直接删除 node
node = child
}
} else {
// 子节点数量 = 2 ,则将中序遍历的下个节点删除,并用该节点替换当前节点
temp := node.Right
for temp.Left != nil {
temp = temp.Left
}
node.Right = t.removeHelper(node.Right, temp.Val.(int))
node.Val = temp.Val
}
}
// 更新节点高度
t.updateHeight(node)
/* 2. 执行旋转操作,使该子树重新恢复平衡 */
node = t.rotate(node)
// 返回子树的根节点
return node
}
/* 删除节点 */
func remove(val: Int) {
root = removeHelper(node: root, val: val)
}
/* 递归删除节点(辅助方法) */
func removeHelper(node: TreeNode?, val: Int) -> TreeNode? {
var node = node
if node == nil {
return nil
}
/* 1. 查找节点并删除 */
if val < node!.val {
node?.left = removeHelper(node: node?.left, val: val)
} else if val > node!.val {
node?.right = removeHelper(node: node?.right, val: val)
} else {
if node?.left == nil || node?.right == nil {
let child = node?.left ?? node?.right
// 子节点数量 = 0 ,直接删除 node 并返回
if child == nil {
return nil
}
// 子节点数量 = 1 ,直接删除 node
else {
node = child
}
} else {
// 子节点数量 = 2 ,则将中序遍历的下个节点删除,并用该节点替换当前节点
var temp = node?.right
while temp?.left != nil {
temp = temp?.left
}
node?.right = removeHelper(node: node?.right, val: temp!.val)
node?.val = temp!.val
}
}
updateHeight(node: node) // 更新节点高度
/* 2. 执行旋转操作,使该子树重新恢复平衡 */
node = rotate(node: node)
// 返回子树的根节点
return node
}
/* 删除节点 */
remove(val) {
this.root = this.#removeHelper(this.root, val);
}
/* 递归删除节点(辅助方法) */
#removeHelper(node, val) {
if (node === null) return null;
/* 1. 查找节点并删除 */
if (val < node.val) node.left = this.#removeHelper(node.left, val);
else if (val > node.val)
node.right = this.#removeHelper(node.right, val);
else {
if (node.left === null || node.right === null) {
const child = node.left !== null ? node.left : node.right;
// 子节点数量 = 0 ,直接删除 node 并返回
if (child === null) return null;
// 子节点数量 = 1 ,直接删除 node
else node = child;
} else {
// 子节点数量 = 2 ,则将中序遍历的下个节点删除,并用该节点替换当前节点
let temp = node.right;
while (temp.left !== null) {
temp = temp.left;
}
node.right = this.#removeHelper(node.right, temp.val);
node.val = temp.val;
}
}
this.#updateHeight(node); // 更新节点高度
/* 2. 执行旋转操作,使该子树重新恢复平衡 */
node = this.#rotate(node);
// 返回子树的根节点
return node;
}
/* 删除节点 */
remove(val: number): void {
this.root = this.removeHelper(this.root, val);
}
/* 递归删除节点(辅助方法) */
removeHelper(node: TreeNode, val: number): TreeNode {
if (node === null) return null;
/* 1. 查找节点并删除 */
if (val < node.val) {
node.left = this.removeHelper(node.left, val);
} else if (val > node.val) {
node.right = this.removeHelper(node.right, val);
} else {
if (node.left === null || node.right === null) {
const child = node.left !== null ? node.left : node.right;
// 子节点数量 = 0 ,直接删除 node 并返回
if (child === null) {
return null;
} else {
// 子节点数量 = 1 ,直接删除 node
node = child;
}
} else {
// 子节点数量 = 2 ,则将中序遍历的下个节点删除,并用该节点替换当前节点
let temp = node.right;
while (temp.left !== null) {
temp = temp.left;
}
node.right = this.removeHelper(node.right, temp.val);
node.val = temp.val;
}
}
this.updateHeight(node); // 更新节点高度
/* 2. 执行旋转操作,使该子树重新恢复平衡 */
node = this.rotate(node);
// 返回子树的根节点
return node;
}
/* 删除节点 */
void remove(int val) {
root = removeHelper(root, val);
}
/* 递归删除节点(辅助方法) */
TreeNode? removeHelper(TreeNode? node, int val) {
if (node == null) return null;
/* 1. 查找节点并删除 */
if (val < node.val)
node.left = removeHelper(node.left, val);
else if (val > node.val)
node.right = removeHelper(node.right, val);
else {
if (node.left == null || node.right == null) {
TreeNode? child = node.left ?? node.right;
// 子节点数量 = 0 ,直接删除 node 并返回
if (child == null)
return null;
// 子节点数量 = 1 ,直接删除 node
else
node = child;
} else {
// 子节点数量 = 2 ,则将中序遍历的下个节点删除,并用该节点替换当前节点
TreeNode? temp = node.right;
while (temp!.left != null) {
temp = temp.left;
}
node.right = removeHelper(node.right, temp.val);
node.val = temp.val;
}
}
updateHeight(node); // 更新节点高度
/* 2. 执行旋转操作,使该子树重新恢复平衡 */
node = rotate(node);
// 返回子树的根节点
return node;
}
/* 删除节点 */
fn remove(&self, val: i32) {
Self::remove_helper(self.root.clone(), val);
}
/* 递归删除节点(辅助方法) */
fn remove_helper(node: OptionTreeNodeRc, val: i32) -> OptionTreeNodeRc {
match node {
Some(mut node) => {
/* 1. 查找节点并删除 */
if val < node.borrow().val {
let left = node.borrow().left.clone();
node.borrow_mut().left = Self::remove_helper(left, val);
} else if val > node.borrow().val {
let right = node.borrow().right.clone();
node.borrow_mut().right = Self::remove_helper(right, val);
} else if node.borrow().left.is_none() || node.borrow().right.is_none() {
let child = if node.borrow().left.is_some() {
node.borrow().left.clone()
} else {
node.borrow().right.clone()
};
match child {
// 子节点数量 = 0 ,直接删除 node 并返回
None => {
return None;
}
// 子节点数量 = 1 ,直接删除 node
Some(child) => node = child,
}
} else {
// 子节点数量 = 2 ,则将中序遍历的下个节点删除,并用该节点替换当前节点
let mut temp = node.borrow().right.clone().unwrap();
loop {
let temp_left = temp.borrow().left.clone();
if temp_left.is_none() {
break;
}
temp = temp_left.unwrap();
}
let right = node.borrow().right.clone();
node.borrow_mut().right = Self::remove_helper(right, temp.borrow().val);
node.borrow_mut().val = temp.borrow().val;
}
Self::update_height(Some(node.clone())); // 更新节点高度
/* 2. 执行旋转操作,使该子树重新恢复平衡 */
node = Self::rotate(Some(node)).unwrap();
// 返回子树的根节点
Some(node)
}
None => None,
}
}
/* 删除节点 */
// 由于引入了 stdio.h ,此处无法使用 remove 关键词
void removeItem(AVLTree *tree, int val) {
TreeNode *root = removeHelper(tree->root, val);
}
/* 递归删除节点(辅助函数) */
TreeNode *removeHelper(TreeNode *node, int val) {
TreeNode *child, *grandChild;
if (node == NULL) {
return NULL;
}
/* 1. 查找节点并删除 */
if (val < node->val) {
node->left = removeHelper(node->left, val);
} else if (val > node->val) {
node->right = removeHelper(node->right, val);
} else {
if (node->left == NULL || node->right == NULL) {
child = node->left;
if (node->right != NULL) {
child = node->right;
}
// 子节点数量 = 0 ,直接删除 node 并返回
if (child == NULL) {
return NULL;
} else {
// 子节点数量 = 1 ,直接删除 node
node = child;
}
} else {
// 子节点数量 = 2 ,则将中序遍历的下个节点删除,并用该节点替换当前节点
TreeNode *temp = node->right;
while (temp->left != NULL) {
temp = temp->left;
}
int tempVal = temp->val;
node->right = removeHelper(node->right, temp->val);
node->val = tempVal;
}
}
// 更新节点高度
updateHeight(node);
/* 2. 执行旋转操作,使该子树重新恢复平衡 */
node = rotate(node);
// 返回子树的根节点
return node;
}
/* 删除节点 */
fun remove(_val: Int) {
root = removeHelper(root, _val)
}
/* 递归删除节点(辅助方法) */
fun removeHelper(n: TreeNode?, _val: Int): TreeNode? {
var node = n ?: return null
/* 1. 查找节点并删除 */
if (_val < node._val)
node.left = removeHelper(node.left, _val)
else if (_val > node._val)
node.right = removeHelper(node.right, _val)
else {
if (node.left == null || node.right == null) {
val child = if (node.left != null)
node.left
else
node.right
// 子节点数量 = 0 ,直接删除 node 并返回
if (child == null)
return null
// 子节点数量 = 1 ,直接删除 node
else
node = child
} else {
// 子节点数量 = 2 ,则将中序遍历的下个节点删除,并用该节点替换当前节点
var temp = node.right
while (temp!!.left != null) {
temp = temp.left
}
node.right = removeHelper(node.right, temp._val)
node._val = temp._val
}
}
updateHeight(node) // 更新节点高度
/* 2. 执行旋转操作,使该子树重新恢复平衡 */
node = rotate(node)
// 返回子树的根节点
return node
}
### 删除节点 ###
def remove(val)
@root = remove_helper(@root, val)
end
### 递归删除节点(辅助方法)###
def remove_helper(node, val)
return if node.nil?
# 1. 查找节点并删除
if val < node.val
node.left = remove_helper(node.left, val)
elsif val > node.val
node.right = remove_helper(node.right, val)
else
if node.left.nil? || node.right.nil?
child = node.left || node.right
# 子节点数量 = 0 ,直接删除 node 并返回
return if child.nil?
# 子节点数量 = 1 ,直接删除 node
node = child
else
# 子节点数量 = 2 ,则将中序遍历的下个节点删除,并用该节点替换当前节点
temp = node.right
while !temp.left.nil?
temp = temp.left
end
node.right = remove_helper(node.right, temp.val)
node.val = temp.val
end
end
# 更新节点高度
update_height(node)
# 2. 执行旋转操作,使该子树重新恢复平衡
rotate(node)
end
3. 查找节点¶
AVL 树的节点查找操作与二叉搜索树一致,在此不再赘述。
7.5.4 AVL 树典型应用¶
- 组织和存储大型数据,适用于高频查找、低频增删的场景。
- 用于构建数据库中的索引系统。
- 红黑树也是一种常见的平衡二叉搜索树。相较于 AVL 树,红黑树的平衡条件更宽松,插入与删除节点所需的旋转操作更少,节点增删操作的平均效率更高。