C++ AVL树实现详解：从基础插入到性能优化的完整指南
struct AVLNode {
int key;
string value;
AVLNode* left;
AVLNode* right;
int balance_factor; // height(left) - height(right)
AVLNode(int k, string v) : key(k), value(v),
left(nullptr), right(nullptr),
balance_factor(0) {}
};
AVLNode insert(AVLNode node, int key, string value) {
// 标准BST插入
if (!node) return new AVLNode(key, value);
if (key < node->key)
node->left = insert(node->left, key, value);
else
node->right = insert(node->right, key, value);
// 更新当前节点平衡因子
node->balance_factor = getHeight(node->left) - getHeight(node->right);
// 检查失衡并旋转
if (node->balance_factor > 1) {
if (key < node->left->key) // LL型
return rightRotate(node);
else { // LR型
node->left = leftRotate(node->left);
return rightRotate(node);
}
}
else if (node->balance_factor < -1) {
if (key > node->right->key) // RR型
return leftRotate(node);
else { // RL型
node->right = rightRotate(node->right);
return leftRotate(node);
}
}
return node;
}
struct OptimizedAVLNode {
int key;
string value;
int8_t balance; // -2~2足够应对所有情况
OptimizedAVLNode* left;
OptimizedAVLNode* right;
};