AVL树为什么分四种情况

Question

LL LR RR RL 为什么只有这四种情况，怎么抽象出来的?这四种情况能涵盖所有其他情况吗？

Answer 1

造成不平衡的时机就是在插入节点的时候,而在一个二叉搜索树中不平衡的情况（根节点的子树高度差大于1）就只有四种情况，比如有以下平衡二叉搜索树

graph TD
    A[10] -->B(5)
    A --> C[15]

我们分别尝试加入20，11，0，8(null节点可以看作空，写出来是为了方便看清左右)
当插入20时，形成RR

graph TD
    A[10] -->B(5)
    A --> C[15]
    C --> E[null]
    C --> D[20]

当插入11时，形成RL

graph TD
    A[10] -->B(5)
    A --> C[15]
    C --> D[11]
    C --> E[null]

当插入0时，形成LL

graph TD
    A[10] -->B(5)
    A --> C[15]
    B --> D[0]
    B --> E[null]

当插入8时，形成LR

graph TD
    A[10] -->B(5)
    A --> C[15]
    B --> D[null]
    B --> E[8]

而这四种情况都能通过一次或两次节点的左旋转后者右旋转而获得一个平衡的子树

Answer 2

• LL LR RR RL 为什么只有这四种情况——因为全部情况都可以归为这4种情况之一
• 怎么抽象出来的——通过观察总结
• 这四种情况能涵盖所有其他情况吗——能