C++怎么实现一个AVL自平衡树_C++数据结构与旋转操作详解-C++-PHP中文网

C++怎么实现一个AVL自平衡树_C++数据结构与旋转操作详解

冰火之心

发布： 2025-11-20 18:51:22

原创

708人浏览过

AVL树通过旋转操作维持平衡，确保操作时间复杂度为O(log n)。

c++怎么实现一个avl自平衡树_c++数据结构与旋转操作详解

AVL树是一种自平衡二叉搜索树，它通过保持每个节点的左右子树高度差不超过1来确保查找、插入和删除操作的时间复杂度始终为O(log n)。C++中实现AVL树需要结合二叉搜索树的基本结构，并在插入和删除后通过旋转操作维持平衡。

AVL树的基本结构

每个AVL节点包含数据值、左右子节点指针以及一个表示该节点高度的整数。结构定义如下：

struct TreeNode {
    int data;
    TreeNode* left;
    TreeNode* right;
    int height;
<pre class='brush:php;toolbar:false;'>TreeNode(int val) : data(val), left(nullptr), right(nullptr), height(1) {}

登录后复制

};

高度信息用于计算平衡因子（左子树高度减右子树高度），当平衡因子绝对值大于1时，说明树失衡，需进行旋转调整。

立即学习“C++免费学习笔记（深入）”；

旋转操作详解

AVL树通过四种旋转操作恢复平衡：左旋、右旋、左右双旋、右左双旋。这些操作是核心机制。

右旋转（Right Rotation）：适用于“左左”情况，即左子树过高且新节点插入在左侧。
左旋转（Left Rotation）：适用于“右右”情况，即右子树过高且新节点插入在右侧。
左右双旋：先对左子节点左旋，再对当前节点右旋，处理“左右”插入情形。
右左双旋：先对右子节点右旋，再对当前节点左旋，应对“右左”插入情形。

旋转函数示例如下：

int getHeight(TreeNode* node) {
    return node ? node->height : 0;
}
<p>int getBalance(TreeNode* node) {
return node ? getHeight(node->left) - getHeight(node->right) : 0;
}</p><p>TreeNode<em> rotateRight(TreeNode</em> y) {
TreeNode<em> x = y->left;
TreeNode</em> T2 = x->right;</p><pre class='brush:php;toolbar:false;'>x->right = y;
y->left = T2;

y->height = max(getHeight(y->left), getHeight(y->right)) + 1;
x->height = max(getHeight(x->left), getHeight(x->right)) + 1;

return x;

登录后复制

}

如此AI员工

国内首个全链路营销获客AI Agent

172

查看详情

TreeNode rotateLeft(TreeNode x) { TreeNode y = x->right; TreeNode T2 = y->left;

y->left = x;
x->right = T2;

x->height = max(getHeight(x->left), getHeight(x->right)) + 1;
y->height = max(getHeight(y->left), getHeight(y->right)) + 1;

return y;

登录后复制

}

插入操作与平衡维护

插入过程类似二叉搜索树，递归找到位置后创建新节点。回溯过程中更新各节点高度并检查平衡性，必要时执行相应旋转。

TreeNode* insert(TreeNode* root, int data) {
    if (!root)
        return new TreeNode(data);
<pre class='brush:php;toolbar:false;'>if (data < root->data)
    root->left = insert(root->left, data);
else if (data > root->data)
    root->right = insert(root->right, data);
else
    return root; // 不允许重复值

root->height = 1 + max(getHeight(root->left), getHeight(root->right));

int balance = getBalance(root);

// 左左情况
if (balance > 1 && data < root->left->data)
    return rotateRight(root);

// 右右情况
if (balance < -1 && data > root->right->data)
    return rotateLeft(root);

// 左右情况
if (balance > 1 && data > root->left->data) {
    root->left = rotateLeft(root->left);
    return rotateRight(root);
}

// 右左情况
if (balance < -1 && data < root->right->data) {
    root->right = rotateRight(root->right);
    return rotateLeft(root);
}

return root;

登录后复制

}