C++ AVL树：实现、平衡与性能优化

C++ AVL树是一种自平衡二叉查找树，它通过维护树的高度平衡来提高查找、插入和删除操作的效率。AVL树得名于它的发明者德国数学家G.M. Adelson-Velsky和苏联程序员E.M. Landis。
在AVL树中，每个节点包含一个关键字和两个子节点。每个节点都满足以下条件：

1. 左子树中所有节点的关键字都小于当前节点的关键字。
2. 右子树中所有节点的关键字都大于当前节点的关键字。
3. 左子树和右子树都是AVL树。
   为了保持AVL树的平衡，当插入或删除节点后，可能会导致树的平衡因子发生变化。平衡因子定义为左子树的高度减去右子树的高度。如果平衡因子的绝对值大于1，就需要进行旋转操作来重新平衡树。
   旋转操作包括四种类型：左旋、右旋、左右旋和右左旋。下面我们将通过代码示例来展示这四种旋转操作。
   首先，我们定义一个AVL树节点类：

   class AVLNode {
   public:
   int key;
   int height;
   AVLNode* left;
   AVLNode* right;
   };

   然后，我们实现插入操作：

   AVLNode* insert(AVLNode* node, int key) {
   if (node == nullptr) {
   return new AVLNode{key, 1, nullptr, nullptr};
   }
   if (key < node->key) {
   node->left = insert(node->left, key);
   } else if (key > node->key) {
   node->right = insert(node->right, key);
   } else { // Duplicate keys are not allowed in AVL tree.
   return node;
   }
   node->height = 1 + max(get_height(node->left), get_height(node->right));
   int balance = get_balance(node);
   if (balance > 1 && key < node->left->key) { // Left Left Case
   return rotate_right(node);
   }
   if (balance < -1 && key > node->right->key) { // Right Right Case
   return rotate_left(node);
   }
   if (balance > 1 && key > node->left->key) { // Left Right Case
   node->left = rotate_left(node->left);
   return rotate_right(node);
   }
   if (balance < -1 && key < node->right->key) { // Right Left Case
   node->right = rotate_right(node->right);
   return rotate_left(node);
   }
   return node; // Balanced case
   }

   在上面的代码中，我们首先比较要插入的关键字与当前节点的关键字。如果当前节点为空，则创建一个新的节点并返回。如果当前节点不为空，我们递归地插入到左子树或右子树中。然后，我们更新当前节点的height属性，并根据需要执行旋转操作来重新平衡树。最后，我们返回新的根节点或当前节点（如果树仍然平衡）。