AVL 树
从一棵随机 AVL 树开始，逐步插入、查找或删除值：查看每个节点的平衡因子、LL、RR、LR 和 RL 旋转、其数组形式，并高亮 C++ 代码。
所有内容均在此浏览器中模拟，不会发送到任何服务器。
无步骤
无步骤
AVL 树
数组索引 · 平衡因子
数组形式
索引 i 的子节点位于 2i+1 和 2i+2。
- 无关
- 已经过
- 正在比较
- 已找到
- 新增
- 待删除
- 后继节点
- 失衡
- 支点
无步骤
代码
#include <iostream>
#include <algorithm>
using namespace std;
class Node { // 节点保存其值和指向两个子节点的指针
private: // 私有属性：只有方法可以访问
int value;
Node* left;
Node* right;
public:
Node(int v) : value(v), left(nullptr), right(nullptr) {}
int getValue() const { return value; }
Node* getLeft() const { return left; }
Node* getRight() const { return right; }
void setValue(int v) { value = v; }
void setLeft(Node* n) { left = n; }
void setRight(Node* n) { right = n; }
};
int height(Node* n) { // 高度：叶子节点为 1，空位（nullptr）为 0
if (n == nullptr) return 0;
return 1 + max(height(n->getLeft()), height(n->getRight()));
}
int balanceFactor(Node* n) { // 平衡因子：左子树高度减去右子树高度
return height(n->getLeft()) - height(n->getRight());
}
Node* rotateRight(Node* y) { // 单右旋：左子节点 x 上升，y 下降
Node* x = y->getLeft();
y->setLeft(x->getRight());
x->setRight(y);
return x;
}
Node* rotateLeft(Node* x) { // 单左旋：右子节点 y 上升，x 下降
Node* y = x->getRight();
x->setRight(y->getLeft());
y->setLeft(x);
return y;
}
Node* rebalance(Node* n) { // 返回平衡后的子树根节点
int bf = balanceFactor(n); // 计算该节点的平衡因子
if (bf > 1) { // 左偏。如果左子节点不是右偏，则为 LL 情况
if (balanceFactor(n->getLeft()) < 0) // 左子节点右偏：LR 情况，先左旋
n->setLeft(rotateLeft(n->getLeft())); // LR 情况的第一次旋转
return rotateRight(n); // 右旋：解决 LL 以及 LR 的后半部分
}
if (bf < -1) { // 右偏。如果右子节点不是左偏，则为 RR 情况
if (balanceFactor(n->getRight()) > 0) // 右子节点左偏：RL 情况，先右旋
n->setRight(rotateRight(n->getRight())); // RL 情况的第一次旋转
return rotateLeft(n); // 左旋：解决 RR 以及 RL 的后半部分
}
return n; // 因子在 -1 到 1 之间：无需旋转
}
Node* insert(Node* root, int v) { // 将 v 插入 AVL 树并返回根节点
if (root == nullptr) // 空位：新节点放在这里
return new Node(v); // 创建新节点
if (v < root->getValue()) // 较小的值放左边，较大的值放右边
root->setLeft(insert(root->getLeft(), v)); // 进入左子树
else
root->setRight(insert(root->getRight(), v)); // 进入右子树
return rebalance(root); // 每次调用返回时检查该节点的平衡性
}
int main() {
Node* root = buildTree(); // 所示的树，已构建完成
root = insert(root, v); // 首次调用，来自 main
return 0; // 操作结束
}