数据结构探险篇 五.二叉平衡树的简析
文章目录
二叉平衡树的意义
二叉平衡树的定义
它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
二叉平衡树的作用
我们为什么要多此一举采用二叉平衡树呢,上一篇提到了,在最好情况下40亿条数据只需要查找32次就可以了,但是那是在二叉树是满二叉树的情况下,
满二叉树定义:如果一棵二叉树的结点要么是叶子结点，要么它有两个子结点，这样的树就是满二叉树
但是当我们插入顺序不好时,达到了最坏情况
就像上图第3个树,这个时候我们的二叉树就退化成了一个单链表而已,这个时候我们再去搜索,花费的时间与线性遍历一致,所以我们要采用二叉平衡树,这样二叉树就基本是满二叉树的状态,搜索效率极大提高
二叉平衡树的操作
平衡因子
即每一棵树都有左子树和右子树,那么他们的左子树与右子树的深度会有差距,这个深度的差值就是平衡因子
根据二叉平衡树的定义,当节点的平衡因子为 -1,0,1时一这个节点为根节点的二叉树是二叉平衡树
节点的旋转
节点的左旋转
通过上图我们可以发现对树的两种操作,
其中左旋转可以拆分成三步
- 旋转节点的左子树变成父节点的右子树
- 旋转节点代替父节点的位置
- 父节点成为旋转节点的左子树
右旋转同理
节点的右旋转
看图1我们可以发现原来以b为根的树是右子树较深,左旋转以后树就平衡了
看图2我们可以发现原来以a为根的树是左子树较深,右旋转以后树就平衡了
那我们就可以得到一个思路,就是当我们插入一个新节点后,我们发现左子树过深,即bf小于-1时,我们就将节点右旋转,当我们发现右子树过深时,也就是bf大于1时,我们进行左旋转
但是事实上没有这么简单
节点失衡情况
右子树过深,同时导致失衡的那个节点右子树也较深时**
这个时候直接对导致失衡的节点e进行左旋转就行了
左子树过深,同时导致过深的那个节点左子树也较深时**
这个时候直接对导致失衡的节点2进行右旋转就行了
左子树过深,同时导致过深的那个节点右子树较深时**
这个时候我们直接右旋节点是没有意义的,得到的还是失衡的树
我们应该分两步
- 左旋导致过深的那个节点的右子树
- 继续右旋该节点
右子树过深,同时导致过深的那个节点左子树较深时**
同上
- 右旋导致过深的那个节点的左子树
- 继续左旋该节点