https://blog.csdn.net/qq_43915356/article/details/106381560

平衡二叉树全称平衡二叉搜索树，也叫AVL树。是一种自平衡的树。

• 不平衡的“发现者”是Mar，“麻烦结点”Nov 在发现者右子树的右边，因而叫 RR 插入，需要RR 旋转（右单旋）
• “发现者”是Mar，“麻烦结点”Apr 在发现者左子树的左边，因而叫 LL 插入，需要LL 旋转（左单旋）
• “发现者”是May，“麻烦结点”Jan在左子树的右边，因而叫 LR 插入，需要LR 旋转
• 麻烦节点的父节点即最下层平衡因子非０节点C，与其父节点B（发现节点的左节点）进行右旋转（RR），导致C代替B的位置，B成为C的左节点，C的左子树CL成为B的右子树。
    发现节点A与C进行左旋转（LL），导致C代替A的位置，A成为C的右节点，C的右子树成为A的左子树
• “发现者”是May，“麻烦结点”Jan在左子树的右边，因而叫 LR 插入，需要LR 旋转

最后更新于 2021-07-20 03:21:57 并被添加「」标签，已有 700 位童鞋阅读过。