假设您可能会破坏输入树：

1. 删除左侧树的最右边的元素，并使用它来构造一个新的根节点，该节点的左子节点是左树，右子节点是右树：O（log n）
2. 确定并设置该节点的平衡因子：O（log n）。在（临时）违反不变量的情况下，平衡因子可能不在{-1，0，1}范围内
3. 旋转以使平衡因子回到范围内：O（log n）旋转：O（log n）

因此，整个操作可以在O（log n）中执行。

编辑：经过深思熟虑，在以下算法中更容易推断出旋转。它也很有可能更快：

1. 确定两棵树的高度：O（log n）。
   假设右树较高（另一种情况是对称的）：

2. 从left树中删除最右边的元素（如有必要，旋转并调整其计算的高度）。让n那个元素。O（log n）

3. 在右侧树中，向左导航，直到到达其子树比最多高1的节点left。让它r成为那个节点。O（log n）

4. 用值为n的新节点，子树left和替换该节点r。O（1）
   通过构造，新节点是AVL平衡的，并且其子树比更高r。

5. 相应地增加其父母的余额。O（1）

6. 并像插入后一样重新平衡。O（log n）