平衡二叉树:
由来:为了解决二叉树在某些情况下形成链表。
特点:平衡因子小于2,进行平衡调整。
平衡因子:结点的左孩子-右孩子的绝对值。
平衡调整策略:LL型 LR型 RR型 RL型。
LL型调整规则(继承左结点的左孩子影响了平衡):将不平衡节点的左孩子提升为新的根节点;将原来的根节点(指不平衡结点),降为新的根节点的右孩子;各子树按大小关系连接。
RR型调整规则(继承右结点的右孩子影响了平衡):将不平衡节点的右孩子提升为新的根节点;原根结点变成新的根结点的左孩子;各子树按大小关系相接。
LR型调整规则(不平衡结点的左结点的右子树影响平衡):先将不平衡的结点的左子树的右子树变为不平衡结点的左子树的父结点;旋转的结果是LL型旋转,按照原不平衡节点LL型进行旋转。
RL型调整规则(不平衡节点的右结点的左子树影响了平衡):先将不平衡结点右子树的左子树变为不平衡结点的右子树的父结点;旋转的结果是一个RR型旋转,按照原不平衡节点RR型旋转。
下面是四种变换典型的案例: