数据结构七之AVL树

平衡因子：某个节点的左右子树的高差
AVL树的特点：
1、每个节点的平衡因子只可能为0，1，-1 （平衡因子的绝对值<=1）
2、搜索、添加、删除的时间复杂度为O（logn）
普通二叉搜索树和AVL树的搜索比较：
树的继承结构：
实例：往树中添加节点
1、最坏的情况：可能会导致所有的祖先节点全部失衡
2、父节点和非祖先节点都不会 失衡
AVL树添加或删除节点后，通过旋转返回平衡（即把每个节点的平衡因子的绝对值控制回到<=1）
右旋转：以失衡节点为远点，向右旋转
（单旋转：按指定方向旋转一次）左旋转：以失衡节点为远点，向左旋转

（双旋转：按指定方向旋转两次）
下图：先是p左旋转，再是g右旋转
下图：先是p右旋转，再是g左旋转
代码演示，添加节点后的平衡修复

示例：

、
、
、
、
删除导致的失衡

总结

以下是对于本来就是AVL树的节点进行的添加、删除节点总结

添加
1、可能会导致除了父节点之外的所有祖先节点失衡（注意，非祖先节点不会失衡）
2、只要让高度最低的失衡节点回复平衡，整棵树就会恢复平衡（仅需O(1)次旋转操作）

删除
1、可能会导致父节点或者祖先节点失衡（只有一个节点会失衡）
2、恢复平衡后，可能会导致更高层的祖先节点失衡（最坏情况需要O(logn)次旋转操作调整）

删除节点：平衡时间复杂度：
1、搜索：时间复杂度O(logn)
2、添加：时间复杂度O(logn), 恢复平衡只需要O(1)次旋转操作
3、删除：书简复杂度O(logn)，恢复平衡最坏情况需要O(logn)次旋转操作