平衡二叉树
定义及性质
平衡二叉树是其左右子树的高度差小于2的二叉搜索树
复杂度
平衡二叉树通过平衡调整,保证其左右子树高度差小于2,因此插入和查找的平均复杂度为O(lgN),最坏情况下也是O(lgN)
插入结点最多需要一次旋转(单旋转和双旋转)调整即可完成平衡
删除结点,在最坏情况下,删除结点向上后引起了树的失衡,又需要重新旋转调整,保持平衡.
例如在某些左子树的高度总是比右子树的高度小1的情况下,删除左子树的结点,导致左子树的高度比右子树的高度小2,引起失衡,再次旋转调整平衡.
因此删除的时间复杂度在O(lgN),一次删除最多需要O(lgN)次旋转调整
四种失衡情况
1. 结点的左孩子的左子树插入,LL型
2. 结点的左孩子的右子树插入,LR型
3. 结点的右孩子的左子树插入,RL型
4. 结点的右孩子的右子树插入,RR型
注意这里的结点是以第一个失衡点作为结点.
对于四种失衡情况的调整
1. LL型
对于LL型,做一个右旋即可
2. LR型
对于LR型,先对失衡点的左孩子做一个左旋,再对失衡点做一个右旋
3. RL型
对于RL型,先对失衡点的右孩子做一个右旋,再对失衡点做一个左旋
4. RR型
对于RR型,对失衡点做一个左旋即可
两种旋转调整平衡
1. 左旋
LeftRotation(x)
y=x.right // y指向旋转结点的右孩子
y.p=x.p // 调整y的父结点
if x.p != null
if x.p.left==x
x.p.left=y
else
x.p.right=y
x.right=y.left // 旋转结点的右孩子调整为y的左孩子
if y.left != null // 调整父结点
y.left.p=x
y.left=x // 将旋转结点作为y的左孩子
x.p=y // 调整父结点
2. 右旋
RightRotation(x)
y=x.left // y指向旋转结点的左孩子
y.p=x.p // 调整y的父结点
if x.p != null
if x.p.left==x
x.p.left=y
else
x.p.right=y
x.left=y.right // 旋转结点的左孩子调整为y的右孩子
if y.right != null // 调整父结点
y.right.p=x
y.right=x // 将旋转结点作为y的右孩子
x.p=y // 调整父结点
// 四种类型的旋转调整
LL(x)
RightRotation(x)
LR(x)
LeftRotation(x.left)
RightRotation(x)
RL(x)
RightRotation(x.right)
LeftRotation(x)
RR(x)
LeftRotation(x)
例如对于如下的一个失衡的二叉树
其中0013为新添加结点,在添加了0013后该树不平衡,第一个失衡点出现在0020,因此要对以0020为根的树做个平衡调整
首先0013是在0020的左孩子的左子树插入的,因此属于LL型,做一个右旋,变如下nightwish
