AVL 树：旋转、插入、删除 C++ 例如：
陈莎拉
什么是 AVL 树？
AVL 树 是二叉搜索树，其中每个节点的左子树和右子树之间的高度差为 -1、0 或 +1。它们是自平衡二叉搜索树，保持对数搜索时间，以发明者 Adelson-Velsky 和 Landis (AVL) 的名字命名。
AVL 树如何工作？
要理解 AVL 树存在的意义，首先要看看普通 AVL 树会出现什么问题。 二进制搜索树假设按以下顺序插入这些键：
AVL 树可视化
当键按递增顺序插入时，树会线性增长，导致搜索复杂度退化为 O(n)。这违背了二叉搜索树的初衷——只有平衡树才能保持搜索复杂度对数级。现在考虑以不同顺序插入相同的键。
相同的键，不同的插入顺序会产生更浅的树形，因此每次搜索的时间复杂度为 O(log n)。AVL 树通过监控每次插入的高度并纠正不平衡来强制执行这种树形，同时保持二叉搜索树的顺序不变。
AVL 树中的平衡因子
平衡因子（BF） tracks 计算每个节点的高度，以便树可以动态地自我平衡。
平衡因子的性质
平衡因子 AVL 树
- 平衡因子是左子树高度与右子树高度之差。
Balance factor(node) = height(node->left) − height(node->right)- 只允许取 -1、0 和 +1 这三个值。
- 值为 -1 表示右子树包含一个额外的层——该节点是右重的。
- 值为 +1 表示左子树包含额外的一层——该节点是左重的。
- 值为 0 表示两侧高度相等——节点完全平衡。
AVL 旋转
当插入或删除操作打破平衡因子规则时，就会进行轮换。这四种情况分别是 LL、RR、LR 和 RL。
左 – 左旋转
当在左子树的左孩子处插入新节点时，执行此旋转。
AVL 树左 - 左旋转
执行一次向右旋转。当节点的 BF 值为 +2 且其左子节点的 BF 值为 +1 时，触发此操作。
右 – 右旋转
当在右子树的右孩子处插入新节点时，执行此旋转。
执行一次左旋转。当节点的 BF 值为 -2 且其右子节点的 BF 值为 -1 时，触发此操作。
右 - 左旋转
当在右子树的左孩子处插入新节点时，执行此旋转。
当 BF(节点) = −2 且 BF(右子节点) = +1 时触发。将右子节点向右旋转，然后将节点向左旋转。
左 - 右旋转
当在左子树的右孩子处插入新节点时，执行此旋转。
当 BF(节点) = +2 且 BF(左子节点) = −1 时触发。左子节点向左旋转，然后节点向右旋转。
AVL 树中的插入
插入操作几乎与普通的二叉搜索树插入操作完全相同。每次插入后，树都会向上遍历并重新平衡。插入操作的最坏情况时间复杂度为 O(log n)。
AVL 树插入实现
第三步： 使用标准二叉搜索树算法插入节点。在上面的例子中，插入节点 160。
第三步： 更新插入路径上每个祖先的平衡因子。
第三步： 如果任何祖先节点的平衡因子超出了范围，则执行匹配旋转。在本例中，节点 350 的平衡因子超出了范围，因此执行 LL 旋转可以恢复平衡。
- If
BF(node) = +2和BF(left-child) = +1进行LL旋转。 - If
BF(node) = −2和BF(right-child) = −1进行 RR 轮换。 - If
BF(node) = −2和BF(right-child) = +1执行 RL 旋转。 - If
BF(node) = +2和BF(left-child) = −1执行 LR 旋转。
AVL 树中的删除
删除操作遵循与普通二叉搜索树相同的逻辑，之后会重新平衡。
第三步： 在树中查找元素。
第三步： 使用标准的二叉搜索树删除方法删除节点。
第三步： 有两种可能的情况。
案例1： 从右子树删除。
- 1A。 If
BF(node) = +2和BF(left-child) = +1进行LL旋转。 - 1B。 If
BF(node) = +2和BF(left-child) = −1执行 LR 旋转。 - 1C。 If
BF(node) = +2和BF(left-child) = 0进行LL旋转。
案例2： 从左侧子树中删除。
- 2A。 If
BF(node) = −2和BF(right-child) = −1进行 RR 轮换。 - 2B。 If
BF(node) = −2和BF(right-child) = +1执行 RL 旋转。 - 2C。 If
BF(node) = −2和BF(right-child) = 0进行 RR 轮换。
C++ AVL 树的示例
下面是一个 C++ 实现AVL树的程序：
#include <iostream> #include <queue> #include <unordered_map> using namespace std; struct node { struct node *left; int data; int height; struct node *right; }; class AVL { public: struct node *root; AVL() { this->root = NULL; } int calheight(struct node *p) { if (p->left && p->right) { if (p->left->height < p->right->height) return p->right->height + 1; else return p->left->height + 1; } else if (p->left && p->right == NULL) { return p->left->height + 1; } else if (p->left == NULL && p->right) { return p->right->height + 1; } return 0; } int bf(struct node *n) { if (n->left && n->right) return n->left->height - n->right->height; else if (n->left && n->right == NULL) return n->left->height; else if (n->left == NULL && n->right) return -n->right->height; return 0; } struct node *llrotation(struct node *n) { struct node *p = n; struct node *tp = p->left; p->left = tp->right; tp->right = p; return tp; } struct node *rrrotation(struct node *n) { struct node *p = n; struct node *tp = p->right; p->right = tp->left; tp->left = p; return tp; } struct node *rlrotation(struct node *n) { struct node *p = n; struct node *tp = p->right; struct node *tp2 = p->right->left; p->right = tp2->left; tp->left = tp2->right; tp2->left = p; tp2->right = tp; return tp2; } struct node *lrrotation(struct node *n) { struct node *p = n; struct node *tp = p->left; struct node *tp2 = p->left->right; p->left = tp2->right; tp->right = tp2->left; tp2->right = p; tp2->left = tp; return tp2; } struct node *insert(struct node *r, int data) { if (r == NULL) { r = new struct node; r->data = data; r->left = r->right = NULL; r->height = 1; return r; } if (data < r->data) r->left = insert(r->left, data); else r->right = insert(r->right, data); r->height = calheight(r); if (bf(r) == 2 && bf(r->left) == 1) r = llrotation(r); else if (bf(r) == -2 && bf(r->right) == -1) r = rrrotation(r); else if (bf(r) == -2 && bf(r->right) == 1) r = rlrotation(r); else if (bf(r) == 2 && bf(r->left) == -1) r = lrrotation(r); return r; } void levelorder_newline() { if (this->root == NULL) { cout << "\nEmpty tree\n"; return; } levelorder_newline(this->root); } void levelorder_newline(struct node *v) { queue<struct node *> q; struct node *cur; q.push(v); q.push(NULL); while (!q.empty()) { cur = q.front(); q.pop(); if (cur == NULL && q.size() != 0) { cout << "\n"; q.push(NULL); continue; } if (cur != NULL) { cout << " " << cur->data; if (cur->left != NULL) q.push(cur->left); if (cur->right != NULL) q.push(cur->right); } } } struct node *deleteNode(struct node *p, int data) { if (p->left == NULL && p->right == NULL) { if (p == this->root) this->root = NULL; delete p; return NULL; } struct node *q; if (p->data < data) p->right = deleteNode(p->right, data); else if (p->data > data) p->left = deleteNode(p->left, data); else { if (p->left != NULL) { q = inpre(p->left); p->data = q->data; p->left = deleteNode(p->left, q->data); } else { q = insuc(p->right); p->data = q->data; p->right = deleteNode(p->right, q->data); } } if (bf(p) == 2 && bf(p->left) == 1) p = llrotation(p); else if (bf(p) == 2 && bf(p->left) == -1) p = lrrotation(p); else if (bf(p) == 2 && bf(p->left) == 0) p = llrotation(p); else if (bf(p) == -2 && bf(p->right) == -1) p = rrrotation(p); else if (bf(p) == -2 && bf(p->right) == 1) p = rlrotation(p); else if (bf(p) == -2 && bf(p->right) == 0) p = rrrotation(p); return p; } struct node *inpre(struct node *p) { while (p->right != NULL) p = p->right; return p; } struct node *insuc(struct node *p) { while (p->left != NULL) p = p->left; return p; } ~AVL() {} }; int main() { AVL b; int c, x; do { cout << "\n1.Display levelorder on newline"; cout << "\n2.Insert"; cout << "\n3.Delete\n"; cout << "\n0.Exit\n"; cout << "\nChoice: "; cin >> c; switch (c) { case 1: b.levelorder_newline(); break; case 2: cout << "\nEnter no. "; cin >> x; b.root = b.insert(b.root, x); break; case 3: cout << "\nWhat to delete? "; cin >> x; b.root = b.deleteNode(b.root, x); break; case 0: break; } } while (c != 0); }
上述代码的运行示例：
- 复制上面的代码并将其保存到名为“
avl.cpp. - 编译代码：
g++ avl.cpp -o run
- 运行代码。
./run
AVL 树的优点
- AVL 树的高度始终保持平衡，永远不会超过 log N。
- 由于该树不会退化，因此搜索速度比普通的二叉搜索树更快。
- 自平衡是自动的——无需重建步骤。
- 确定性性能适用于实时系统和内存索引。
