平衡因子(Balance Factor)：某节点的左右子树的高度差（平衡因子 = 节点左树高度 - 节点右树高度）

AVL树的特点：

  • 每个节点的平衡因子只可能是1、0、-1（绝对值 <= 1，如果超过1，称之为失衡）
  • 每个节点的左右子树高度差不超过1
  • 搜索、添加、删除的时间复杂度是O(logn)

会导致失衡的原因有两种：添加节点、删除节点

添加失去平衡：

  • 最坏的情况下，可能会导致所有祖先节点都失衡；

  • 父节点、非祖先节点，都不可能失衡（添加节点一定是在叶子节点进行）

    删除失衡：

  • 只可能会导致父节点或祖先节点失衡，但只有一个节点会失衡 ；

  • 除了父节点以外的其他节点，都不可能失衡；

  • 父节点平衡后，可能导致其父节点的父节点失衡，以此类推；

    平均时间复杂度：

  • 搜索：O(logn)；

  • 添加：O(logn)，仅需要O(1)次的旋转操作；
  • 搜索：O(logn)，最多需要O(logn)次的旋转操作；

    失衡后进行恢复：

    LL、RR、LR、RL 指最终失衡节点的路径；
    如下图，添加的红色节点为n下子节点，而n为p的左子树节点，且p为g的左子树节点，故为LL ( Left-Left )
    image.png

方案1：根据路径不同，进行不同处理

LL - 右旋转（单旋）

image.png

RR - 左旋转（单旋）

image.png

LR - RR左旋转，LL右旋转（双旋）

  • 先执行左旋转，然后再执行右旋转（左旋后会发现，情况与右旋问题一致，故最后是右旋）

image.png

RL - LL右旋转，RR左旋转（双旋）

  • 如上类似

image.png

方案2：根据结果特征，统一操作

从图中可看出，将不平衡涉及的节点以及子树进行了分块：a、b、c、d、e、f、g，并得出以下特征：

  • 旋转前，分块从小到大分块（即从做到右）；
  • 旋转后，d始终是根节点，且b、f始终是d的左、右子树的根节点；
  • 旋转后，a - b - c、e - f - g、b - d - f分别组成一颗子树；

image.png