平衡二叉树(-)

平衡二叉树(-)

二叉排序树构造的不好的话就会退化成斜树.

undefined

斜树:所有的结点都只有左子树的二叉树叫左斜树。所有结点都是只有右子树的二叉树叫右斜树。这两者统称为斜树。

由于斜树性能很差,所以我们在构造二叉排序树的时候要尽可能像它们靠近,才能得到最佳的操作性能--平衡二叉树。

什么是平衡二叉树

也叫 AVL 树.
二叉树首先是二叉排序树.

平衡二叉树要求每个节点的左子树和右子树的高度差至多等于 1,这个高度(深度)差的值叫做平衡因子 BF,也就是说 BF 的值不能大于1,否则就不是平衡二叉树。

由于BF的值不大于1,所以取值有1,0,-1.

如何计算平衡因子BF

undefined

高度计算:

5高度为3.
2高度为2.
1和4高度为1
3高度为0
6高度为1
7高度为0

5节点的左子树高度是3,右是2
5的平衡因子是3-2=1
同理已2节点为开始
那么
左子树高度1
右子树高度2
2的平衡因子是1-2=-1
所有节点都符合BF的定义.所以是平衡二叉树

平衡二叉树的实现原理

平衡二叉树的基本实现思路,是在构建二叉排序树的时候,每插入一个节点,都要检查这个节点的插入是否破坏了原有的平衡性,如果是的话,则找出最小不平衡子树,在保证整体二叉排序树的前提下,通过左旋或者右旋的方式将其调整为平衡子树。从而动态维护这棵平衡二叉树。

最小不平衡子树

距离插入节点最近的,且平衡因子绝对值大于1的节点为根的子树,叫做最小不平衡子树

undefined

比如上图中以存储元素58的节点为根的子树叫做最小不平衡子树。

左旋/右旋

所谓左旋和右旋指的是最小不平衡子树旋转的方向。
如果平衡因子小于 -1,即右子树高度值比较大,则需要左旋.

undefined

反之,如果平衡因子大于1,即左子树高度值比较大,则需要右旋.

undefined