AVL树通过维持左右子树高度差不超过1来保证操作时间复杂度为O(log n)，需在插入删除后更新高度并进行旋转调整。
AVL树是一种自平衡的二叉搜索树，它通过维持左右子树的高度差不超过1来保证树的整体高度始终接近log(n)，从而确保查找、插入和删除操作的时间复杂度为O(log n)。在C++中实现AVL树需要理解二叉搜索树的基本结构，并加入平衡因子的维护与旋转操作。
AVL树节点设计
每个节点除了存储值外，还需要记录当前子树的高度，以便计算平衡因子（左子树高度减右子树高度）：
struct Node { int data; Node* left; Node* right; int height;Node(int value) : data(value), left(nullptr), right(nullptr), height(1) {}
};
高度初始化为1，因为单个节点的高度是1（不是0）。
立即学习“C++免费学习笔记（深入）”；
基本操作：获取高度与平衡因子
封装两个辅助函数用于判断是否失衡以及进行后续旋转：
int getHeight(Node* node) { return node ? node->height : 0;}int getBalanceFactor(Node* node) {return node ? getHeight(node->left) - getHeight(node->right) : 0;}
这两个函数会在插入和删除后频繁调用，用来决定是否需要旋转调整。
四种旋转操作
当某个节点的平衡因子大于1或小于-1时，就需要通过旋转恢复平衡。共四种情况：
右旋（LL型）
适用于左子树过高且新节点插入在左侧路径上：
Node* rotateRight(Node* y) { Node* x = y->left; Node* T2 = x->right;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; // 新的根
}
左旋（RR型）
适用于右子树过高：
Node* rotateLeft(Node* x) { Node* y = x->right; Node* 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; // 新的根
}
左右双旋（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);if (value 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 left->data) return rotateRight(root);// RR型if (balance root->right->data) return rotateLeft(root);// LR型if (balance > 1 && value > root->left->data) return rotateLeftRight(root);// RL型if (balance < -1 && value right->data) return rotateRightLeft(root);return root;
}
删除操作
删除节点需处理三种情况（无子、一子、两子），找到中序后继替代值，然后递归删除：
Node* findMin(Node* root) { while (root && root->left) root = root->left; return root;}Node remove(Node root, int value) {if (!root)return root;
if (value 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 right) 1 && getBalanceFactor(root->left) < 0) return rotateLeftRight(root);if (balance right) > 0) return rotateRightLeft(root);return root;
}
完整使用示例
可以封装成类，并提供遍历接口验证结构正确性：
class AVLTree {public: Node* root; AVLTree() : root(nullptr) {}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 <data << "(" <height <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);tree.printInorder(); // 输出应有序且各节点高度合理tree.remove(6);tree.printInorder();return 0;
}
基本上就这些。只要掌握旋转时机和方式，AVL树就能稳定运行。虽然现在STL中的set/map多用红黑树实现，但AVL作为经典平衡树仍是学习数据结构的重要一环。
以上就是C++怎么实现一个AVL树_C++数据结构与AVL树实现的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1483528.html
微信扫一扫 
支付宝扫一扫 
