因为这道题晴神给出模板了，所以水过，顶多就是调试加深下理解
小结一下，AVL 插入先写出 BST 插入的基本模板（而 BST 插入就是在查找基础上修改的，所以最终还是 BST 查找的模板）：
/* 伪码 */ void bst_search(node_t *root, int val) { /* 死胡同 */ if (root == NULL) return;
/* 岔道口 */ if (root->data == val) {...} else if (root->data > val) bst_search(root->left, val); else bst_search(root->right, val); }
然后就是在查找基础上改为 BST 插入，就修改了三个地方：
/* 伪码 */ void bst_insert(node_t *&root, int val) { /* 死胡同 */ if (root == NULL) {root = create_node(val); return;}
/* 岔道口 */ if (root->data > val) bst_search(root->left, val); else bst_search(root->right, val); }
最后再修改为 AVL，先写出大概模板：
/* 伪码 */ void avl_insert(node_t *&root, int val) { /* 死胡同 */ if (root == NULL) {root = create_node(val); return;} /* 岔道口 */ if (root->data > val) { bst_search(root->left, val); //其他操作 } else { bst_search(root->right, val); //其他操作 } }
（可以看出它们非常非常非常相似）
最后才是 AVL 的操作
1. 插入 2. 更新高度 3. 判断是否失衡 4. 如果失衡，再判断是哪种树型（LL, LR, RR, RL）
这四点 "实战" 大概长这个样子：
/* 代码（节选） */ if (r->data > val) { //1. 插入 insert(r->left, val); //2. 更新高度 update_height(r); //3. 判是否平衡 if (get_balance(r) == 2) { //4. 判是哪种类型的不平衡 if (get_balance(r->left) == 1) { R(r); } else { L(r->left); R(r); } } }
（至于为什么通过 get_balance() == 2(或-2) 可以判断失衡， get_balance(r->left) == 1(或-1) 可以判断树型，这个晴神说得很详细了——我是配合中国大学 MOOC-zjuds 网课和晴神 AVL 一节一起理解的）