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);

// 更新當前節(jié)點平衡因子
node->balance_factor = getHeight(node->left) - getHeight(node->right);

// 檢查失衡并旋轉(zhuǎn)
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;

};