C++怎么实现一个AVL树_C++数据结构与AVL树实现-C++-PHP中文网

C++怎么实现一个AVL树_C++数据结构与AVL树实现

尼克

发布： 2025-11-11 21:21:04

原创

277人浏览过

AVL树通过维持左右子树高度差不超过1来保证操作时间复杂度为O(log n)，需在插入删除后更新高度并进行旋转调整。

c++怎么实现一个avl树_c++数据结构与avl树实现

AVL树是一种自平衡的二叉搜索树，它通过维持左右子树的高度差不超过1来保证树的整体高度始终接近log(n)，从而确保查找、插入和删除操作的时间复杂度为O(log n)。在C++中实现AVL树需要理解二叉搜索树的基本结构，并加入平衡因子的维护与旋转操作。

AVL树节点设计

每个节点除了存储值外，还需要记录当前子树的高度，以便计算平衡因子（左子树高度减右子树高度）：

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

登录后复制

};

高度初始化为1，因为单个节点的高度是1（不是0）。

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

基本操作：获取高度与平衡因子

封装两个辅助函数用于判断是否失衡以及进行后续旋转：

int getHeight(Node* node) {
    return node ? node->height : 0;
}
<p>int getBalanceFactor(Node* node) {
return node ? getHeight(node->left) - getHeight(node->right) : 0;
}</p>

登录后复制

这两个函数会在插入和删除后频繁调用，用来决定是否需要旋转调整。

四种旋转操作

当某个节点的平衡因子大于1或小于-1时，就需要通过旋转恢复平衡。共四种情况：

右旋（LL型）

适用于左子树过高且新节点插入在左侧路径上：

Node* rotateRight(Node* y) {
    Node* x = y->left;
    Node* T2 = x->right;
<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数字人能力，实现7*24小时AI数字人直播带货，低成本实现直播业务快速增增，全天智能在线直播

查看详情

左旋（RR型）

适用于右子树过高：

Node* rotateLeft(Node* x) {
    Node* y = x->right;
    Node* T2 = y->left;
<pre class='brush:php;toolbar:false;'>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; // 新的根

登录后复制

}

左右双旋（LR型）

先对左孩子左旋，再对当前节点右旋：

Node* rotateLeftRight(Node* node) {
    node->left = rotateLeft(node->left);
    return rotateRight(node);
}

登录后复制

右左双旋（RL型）

先对右孩子右旋，再对当前节点左旋：

Node* rotateRightLeft(Node* node) {
    node->right = rotateRight(node->right);
    return rotateLeft(node);
}

登录后复制

插入操作

插入逻辑类似BST，但在递归返回过程中更新高度并检查平衡性：

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

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

int balance = getBalanceFactor(root);

// LL型
if (balance > 1 && value < root->left->data)
    return rotateRight(root);

// RR型
if (balance < -1 && value > root->right->data)
    return rotateLeft(root);

// LR型
if (balance > 1 && value > root->left->data)
    return rotateLeftRight(root);

// RL型
if (balance < -1 && value < root->right->data)
    return rotateRightLeft(root);

return root;

登录后复制

}

删除操作

删除节点需处理三种情况（无子、一子、两子），找到中序后继替代值，然后递归删除：

Node* findMin(Node* root) {
    while (root && root->left)
        root = root->left;
    return root;
}
<p>Node<em> remove(Node</em> root, int value) {
if (!root)
return root;</p><pre class='brush:php;toolbar:false;'>if (value < root->data)
    root->left = remove(root->left, value);
else if (value > root->data)
    root->right = remove(root->right, value);
else {
    if (!root->left || !root->right) {
        Node* temp = root->left ? root->left : root->right;
        delete root;
        return temp;
    } else {
        Node* temp = findMin(root->right);
        root->data = temp->data;
        root->right = remove(root->right, temp->data);
    }
}

if (!root) return root;

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

// 同样四种旋转修复
if (balance > 1 && getBalanceFactor(root->left) >= 0)
    return rotateRight(root);

if (balance < -1 && getBalanceFactor(root->right) <= 0)
    return rotateLeft(root);

if (balance > 1 && getBalanceFactor(root->left) < 0)
    return rotateLeftRight(root);

if (balance < -1 && getBalanceFactor(root->right) > 0)
    return rotateRightLeft(root);

return root;

登录后复制

}

完整使用示例

可以封装成类，并提供遍历接口验证结构正确性：

class AVLTree {
public:
    Node* root;
    AVLTree() : root(nullptr) {}
<pre class='brush:php;toolbar:false;'>void insert(int value) { root = insert(root, value); }
void remove(int value) { root = remove(root, value); }

void inorder(Node* node) {
    if (node) {
        inorder(node->left);
        cout << node->data << "(" << node->height << ") ";
        inorder(node->right);
    }
}

void printInorder() {
    inorder(root);
    cout << endl;
}

登录后复制

};

测试代码：

int main() {
    AVLTree tree;
    tree.insert(10);
    tree.insert(20);
    tree.insert(5);
    tree.insert(6);
    tree.insert(15);
    tree.insert(25);
<pre class='brush:php;toolbar:false;'>tree.printInorder(); // 输出应有序且各节点高度合理

tree.remove(6);
tree.printInorder();

return 0;

登录后复制

}

基本上就这些。只要掌握旋转时机和方式，AVL树就能稳定运行。虽然现在STL中的set/map多用红黑树实现，但AVL作为经典平衡树仍是学习数据结构的重要一环。

以上就是C++怎么实现一个AVL树_C++数据结构与AVL树实现的详细内容，更多请关注php中文网其它相关文章！