平衡二叉树
- 算法
- 2025-10-30
- 113热度
- 0评论
一、 什么是平衡二叉树？
1.1 基本概念
平衡二叉树是一种特殊的二叉搜索树，它通过特定的平衡机制确保树的高度始终保持在对数级别。（解决了二叉搜索树的极端情况）
1.2 平衡条件
对于树中的任意节点，其左子树和右子树的高度差绝对值不超过1：
平衡因子 = 左子树高度 - 右子树高度 （注： 左 - 右）
平衡条件：|平衡因子| ≤ 1二、为什么需要平衡二叉树？
2.1 二叉搜索树的退化问题
有序插入导致链表化：
插入序列：1, 2, 3, 4, 5
普通BST：
1
\
2
\
3
\
4
\
5
高度：5，退化成链表！平衡BST：
2
/ \
1 4
/ \
3 5
高度：3，保持平衡！三、AVL的操作
3.1 树结构
struct AVLNode {
int value,
int height,
AVLNode* left, right;
AVLNode(int x) value(x), height(1), left(nullptr), right(nullptr) {}
}3.2 AVL的基本方法
int getHeight(AVLNode* root) {
return root ? root -> height : 0;
}
void updateHeight(AVLNode* root) {
if (root)
root -> height = 1 + max(getHeight(root -> left), getHeight(root -> right));
}
int getBalanceFactor(AVLNode* root) {
return root ? getHeight(root -> left) - getHeight(root -> right) : 0;
}3.3 AVL平衡时旋转操作
3.3.1 LL型（右旋）
A (平衡因子=2) B
/ 右旋操作 / \
B (平衡因子=1) ================> C A
/ \ /
C D D代码实现：
// 判断条件: 当前节点的平衡因子大于1, 并且当前节点的左子树的平衡因子大于等于0
// getBalanceFactor(A) > 1 && getBalanceFactor(B) >= 0
AVLNode* rightRotate(AVLNode* A){
AVLNode* B = A -> left;
AVLNode* D = B -> right;
B -> right = A;
A -> right = D;
updateHeight(A);
updateHeight(B);
return B;
}3.3.2 RR型（左旋）
A (平衡因子=-2 B
\ 左旋操作 / \
B (平衡因子=0) ================> A C
/ \ \
D C D代码实现：
// 判断条件： 当前节点的平衡因子小于1，且当前节点的左子树的平衡因子小于等于0
// getBalanceFactor(A) < 1， getBalanceFactor(B) <= 0
AVLNode* leftRotate(AVLNode* A) {
AVLNode* B = A -> right;
AVLNode* D = B -> left;
B -> left = A;
A -> right = D;
updateHeight(A);
updateHeight(B);
return B;
}3.3.3 LR型 (先左旋再右旋)
A (平衡因子=2) A C
/ 左旋 / 右旋 / \
B (平衡因子=-1) ========> C ========> B A
\ /
C B代码示例：
// 判断条件：当前节点的平衡因子大于1，且当前节点的左子树平衡因子小于0
// getBalanceFactor(A) > 1 && getBalanceFactor(A -> left) <0
AVLNode* leftRightRotate(AVLNode* A){
A -> left = leftRotate(A -> left);
return rightRotate(A);
}3.3.4 RL型（先右旋再左旋）
A (平衡因子=-2) A C
\ 右旋 \ 左旋 / \
B (平衡因子=1) ========> C ========> A B
/ \
C B// 判断条件：当前节点的平衡因子小于-1，且右子树平衡因子大于0
// getBalaceFactor(A) < -1 && getBalanceFactor(A -> right) > 0;
AVLNode* rightLeftRotate(AVLNode* A) {
A -> right = rightRotate(A -> right);
return leftRotate(A);
}3.4 AVL的基本操作
3.4.1 查找操作
查找操作和二叉搜索树是一样的方式
AVLNode* findAVLNode(AVLNode* root, int value) {
if (root == nullptr || root -> value == value)
return root;
if (value > root -> value)
retturn findAVLNode(root -> right, value);
else (value < root -> value)
return findAVLNode(root -> left, value);
}3.4.2 平衡操作
步骤：
- 更新当前节点的高度
- 根据类型去平衡二叉树
代码：
AVLNode* balanceAVLNode(AVLNode* root) {
updateHeight(root);
int balanceFactor = getBalanceFactor(root);
if (balanceFatcor > 1 && getBalanceFactor(root -> left) >= 0)
rightRotate(root);
else if (balanceFactor > 1 && getBalanceFactor(root -> left) < 0)
leftRightRotate(root);
else if (balanceFactor < 1 && getBalanceFactor(root -> right) <= 0)
leftRotate(root);
else if (balanceFactor < 1 && getBalanceFactor(root -> right) > 0)
rightLeftRotate(root);
return root;
}3.4.3 插入操作
代码：
AVLNode* insertAVLNode(AVLNode* root, int value) {
if (root == nullptr)
return new AVLNode(value);
if (value > root -> value) root -> right = insertAVLNode(root -> right, value);
else if (value < root -> value) root -> left = insertAVLNode(root -> left, value);
else return root;
// 平衡操作
return balanceAVLNode(root);
}3.4.4 删除操作
代码：
AVLNode* findMinNode(AVLNode* root) {
if (root && root -> left != nullptr){
root = root -> left;
}
return root;
}
AVLNode* deleteAVLNode(AVLNode* root, int value) {
if (root == nullptr)
return root;
if (value > root -> value) root -> right = deleteAVLNode(root -> right, value);
else if (value < root -> value) root -> left = deleteAVLNode(root -> left, value);
else {
if (root -> left == nullptr) {
AVLNode* temp = root -> right;
*root = *temp;
delete temp
}
else if (root -> right = nullptr){
AVLNode* temp = root -> left;
*root = *temp;
delete temp;
}
else {
AVLNode* minNode = findAVLNode(root -> right);
root -> value = minNode -> value;
return deleteAVL(root -> right, minNode -> value);
}
}
if (root == nullptr) return root;
return updateBalanceNode(root);
}四、示例代码
#include <iostream>
#include <vector>
using namespace std;
struct AVLNode{
int height; // 平衡因子
int value;
AVLNode* left;
AVLNode* right;
AVLNode(int x) : value(x), height(1), left(nullptr), right(nullptr) {}
};
class AVLTree{
private:
AVLNode* root;
// 获得节点高度
int getHeight(AVLNode* node) {
return node ? node -> height : 0;
}
// 更新节点高度
void updateHeight(AVLNode* node) {
if (node)
node -> height = 1 + max (getHeight(node -> left), getHeight(node -> right));
}
// 获得平衡因子
int getBalanceFactor(AVLNode* node){
return node ? (getHeight(node -> left) - getHeight(node -> right)) : 0;
}
// LL右旋
AVLNode* rightRotate(AVLNode* A){
AVLNode* B = A -> left;
AVLNode* D = B -> right;
// 执行旋转
B -> right = A;
A -> left = D;
// 更新高度
updateHeight(A);
updateHeight(B);
// 返回根节点
return B;
}
// RR左旋
AVLNode* leftRotate(AVLNode* A){
AVLNode* B = A -> right;
AVLNode* D = B -> left;
B -> left = A;
A -> right = D;
updateHeight(A);
updateHeight(B);
return B;
}
// LR 先左旋再右旋
AVLNode* leftRightRotate(AVLNode* A){
A -> left = leftRotate(A -> left);
return rightRotate(A);
}
// RL 先右旋在左旋
AVLNode* rightLeftRotate(AVLNode* A){
A -> right = rightRotate(A -> right);
return leftRotate(A);
}
// 插入操作
AVLNode* insertAVLNode(AVLNode* root, int value){
if (root == nullptr)
return new AVLNode(value);
if (value > root -> value) root -> right = insertAVLNode(root -> right, value);
else if (value < root -> value) root -> left = insertAVLNode(root -> left, value);
else{
return root;
}
return balanceAVLNode(root);
}
// 删除(插入)平衡操作
AVLNode* balanceAVLNode(AVLNode* root){
// 更新高度
updateHeight(root);
// 获得平衡因子
int balance = getBalanceFactor(root);
// 平衡调整
if (balance > 1 && getBalanceFactor(root -> left) >= 0){
return rightRotate(root);
}
if (balance > 1 && getBalanceFactor(root -> left) < 0){
return leftRightRotate(root);
}
if (balance < -1 && getBalanceFactor(root -> right) <= 0){
return leftRotate(root);
}
if (balance < -1 && getBalanceFactor(root -> right) > 0){
return rightLeftRotate(root);
}
// 不需要调整
return root;
}
AVLNode* findMinNode(AVLNode* root){
while (root && root -> left != nullptr)
root = root -> left;
return root;
}
// 删除操作
AVLNode* deleteAVLNode(AVLNode* root, int value){
if (root == nullptr)
return nullptr;
if (value < root -> value) root -> left = deleteAVLNode(root -> left, value);
else if (value > root -> value) root -> right = deleteAVLNode(root -> right, value);
else{
if (root -> left == nullptr){
AVLNode* temp = root -> right;
delete root;
root = temp;
}
else if (root -> right == nullptr){
AVLNode* temp = root -> left;
delete root;
root = temp;
}
else{
AVLNode* temp = findMinNode(root -> right);
root -> value = temp -> value;
root -> right = deleteAVLNode(root -> right, temp -> value);
}
}
if (root == nullptr) return nullptr;
return balanceAVLNode(root);
}
AVLNode* findAVLNode(AVLNode* root, int value){
if (root == nullptr || root -> value == value)
return root;
if (value > root -> value) return findAVLNode(root -> right, value);
else return findAVLNode(root -> left, value);
}
// 中序遍历
void inorderRecursive(AVLNode* root, vector<int> &res) {
if (root == nullptr) return;
inorderRecursive(root -> left, res);
res.push_back(root -> value);
inorderRecursive(root -> right, res);
}
public:
AVLTree() : root(nullptr) {}
void insert(int value){
root = insertAVLNode(root, value);
}
void remove(int value){
root = deleteAVLNode(root, value);
}
bool find(int value){
return findAVLNode(root, value) != nullptr;
}
// 中序遍历（升序）
vector<int> inorder() {
vector<int> result;
inorderRecursive(root, result);
return result;
}
int getHeight(int value){
AVLNode* temp = findAVLNode(root, value);
return temp != nullptr ? getHeight(temp) : 0;
}
int getBalanceFatcor(int value){
AVLNode* temp = findAVLNode(root, value);
return temp != nullptr ? getBalanceFactor(temp) : 0;
}
};
int main() {
AVLTree tree;
cout << "=== 平衡二叉树测试 ===" << endl;
// 插入测试
vector<int> values = {50, 30, 70, 20, 40};
for (int val: values) {
cout << "插入数值: ";
cout << val << " ";
tree.insert(val);
vector<int> in = tree.inorder();
for (int val1 : in) {
cout << val1 << ": Height: " << tree.getHeight(val1) << " BalanceFactor " << tree.getBalanceFatcor(val1) << " ";
}
cout << endl;
}
// 插入测试
values = {30, 70, 40};
for (int val: values) {
cout << "删除数值: ";
cout << val << " ";
tree.remove(val);
vector<int> in = tree.inorder();
for (int val1 : in) {
cout << val1 << ": Height: " << tree.getHeight(val1) << " BalanceFactor " << tree.getBalanceFatcor(val1) << " ";
}
cout << endl;
}
return 0;
}五、总结
时间复杂度：
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
| 查找 | O(log n) | 树高度为 O(log n) |
| 插入 | O(log n) | 查找 + 最多两次旋转 |
| 删除 | O(log n) | 查找 + 最多两次旋转 |
| 旋转 | O(1) | 只涉及常数次指针操作 |
| 空间 | O(n) | 存储n个节点 |
- 数据库系统：索引结构保证查询效率
- 文件系统：目录树管理
- 编译器：符号表管理
- 实时系统：保证最坏情况性能
- 游戏开发：场景管理、碰撞检测
通过旋转操作，平衡二叉树能够在插入和删除时自动调整结构，确保树的高度始终保持在 O(log n) 级别，从而保证所有操作的高效性。