AVL树的含义：是二叉搜索树BST。当一棵二叉搜索树找到一个值时，时间复杂度是O(h)，所以我们让树尽可能平衡，即最大高度尽可能小。因此，AVL。参考例子：AcWing：AVL树的根[1]百度百科[2]：在计算机科学中，AVL树是第一个发明的自平衡二叉搜索树。在一棵AVL树中，任意一个节点的两棵子树的高度最大差为1，所以又称为高度平衡树。添加和删??除可能需要一个或多个树旋转来重新平衡树。AVL树的名字来源于它的发明者G.M.Adelson-Velsky和??E.M.Landis，他们在1962年的论文《An algorithm for the organization of information》中发表了它。BST本质上维护了一个有序的序列。AVL树中的左手右手操作不会改变树的中序遍历结果。如何将上图中的A向右旋转？将B旋转到根节点，则使A成为B的右孩子，将E补给A作为A的左孩子。左旋右旋到节点u右旋：根u的左儿子成为新根p，根的左儿子变成新根p，新根p的右儿子原来的右儿子变成原根uu并且需要更新p的高度voidR(int&u){intp=l[u];l[u]=r[p],r[p]=u;update(u),update(p);u=p;}右旋到节点u：根u的右儿子成为新的根p，根的右儿子成为新根p，原左儿子，新根p的左儿子成为原根u，u和p的高度都需要更新voidL(int&u){intp=r[u];r[u]=l[p],l[p]=u;update(u),update(p);u=p;}左右更新高度儿子决定，因为在求身高的时候，他两个儿子的身高已经默认更新了：voidupdate(intu){h[u]=max(h[l[u]],h[r[u]])+1;}插入的四种情况四种情况(1)新数插入左子树，导致左子树比右子树高2；对于四种情况①，左孩子的左子树比右子树高1。A应该向右旋转。例子如上图，向右旋转88就可以了。(2)新数插入左子树，导致左子树比右子树高2；在这四种情况下，左孩子的右子树比左子树高1。您应该将B向左旋转，将A向右旋转。对应的情况如下：706165//左手61706561//右手70656170（三）右子树插入新数，导致右子树比左子树高2；右孩子的右子树高于其左子树1对于②在四种情况下。A应该是左撇子。对应的情况是像8896120，向左旋转88即可。(4)新数插入右子树，导致右子树比左子树高2；4种情况下右孩子的左子树比右子树高1。您应该将B向右旋转，将A向左旋转。对应情况如下：709688//右旋96708896//左旋70967088插入代码voidinsert(int&u,intw){if(!u)u=++idx,v[u]=w;elseif(w
