大话数据结构-8.7 平衡二叉树(avl树) 328- 高飞网

8.7 平衡二叉树(avl树) 328

2017-01-11 23:04:52.0

    平衡二叉树(Self-Balancing Binary Search Tree或Height-Balanced Binary Search Tree),是一种二叉排序树,其中每一个节点的左子树和右子树的高差至多等于1。

    有两位俄罗斯数学家G.M.Adelson-Velskii和E.M.Landis在1962年共同发明一种解决平衡二叉树的算法,所以也称平衡二叉树为AVL树

    平衡二叉树,是一种高度平衡的二叉排序树。要么是一棵空树,要么它的左子树和右子树都是平衡二叉树,且左子树和右子树的深度之差的绝对值不超过1。二叉树上结点的左子树深度减去右子树深度的值称为平衡因子BF(Balance Factor)。则平衡二叉树上所有结点的平衡因子只可能是-1、0和1。只要二叉树上有一个结点的平衡因子绝对值大于1,则该二叉树就是不平衡的。

    距离插入结点最近的,且平衡因子的绝对值大于1的结点为根的子树,称之为最小不平衡子树。


8.7.1 平衡二叉树实现原理

    平衡二叉树构建的基本思想是:在构建二叉排序树的过程中,每当插入一个结点时,先检查是否因插入而破坏了树的平衡性,若是,则找出最小不平衡子树。在保持二叉排序树特性的前提下,调整最小不平衡子树中各结点之间的链接关系,进行相应的旋转,使之成为新的平衡子树。

    假设有一个数组a[10]={3,2,1,4,5,6,7,10,9,8}需要构建二叉排序树。在不考虑平衡情况下,会构建成如下图1的样子;但这棵二叉树高度为8,对于查找很不利(二叉排序树的查找时间复杂度与深度与有)。希望能构建成如图2的样子,高度只有4。


    对于数组a[10]的前两位3和2,正常构建,到第3个数1时,发现根结点的平衡因子变成了2(左深度2-右深度0),此时整棵树都成了最小不平衡子树,因此需要调整。如下图1。因为平衡因子BF值为正,因此将整个树进行右旋(顺时针旋转),此时结点2成了根结点,3成了2的右孩子,这样三个结点的BF值均为0,非常平衡。

    然后再增加结点4,平衡因子没有发生改变,如图3。增加结点5时,结点3的BF值为-2,说明要旋转了。由于BF是负值,所以对这棵最小平衡子树进行左旋(逆时针旋转),如图4.

    继续增加结点6时,发现根结点的BF值变成了-2,如图6。所以左旋转,注意此时本来结点3是4的左孩子,但由于旋转后需要满足二叉排序树特性,因此它成了结点2的右孩子,如图7,增加结点7,同样要左旋,如图8和9。


    当增加结点10时,结构无变化,如图10。再增加结点9,此时结点7的BF变成了-2,理论上只需要旋转最小不平衡子树7、9、10即可,但如果左旋转后结点9就成了10的右孩子,不符合二叉排序树的特性(左子孙比根结点小,右子孙比根结点大)。不能简单的右旋转。

    根本原因在于结点7的BF是-2,而结点10的BF是1。也即一正一负,符号不统一,而之前的旋转无论转旋右旋,根与子结点的平衡因子符号都是相同的。

    不统一,就先旋转为统一。于是先对结点9和结点10进行右旋,使得结点10成为9的右子树,结点9的BF为-1,此时就与结点7的BF值符号统一了。如图12所示。

    这样再以结点7为最小不平衡子树进行左旋,得到图13,接着插入8,情况下刚才类似,结点6的BF是-2,而它的右孩子9的BF是1,如图14,因此以9为根结点,进行右旋,得到图15,此时结点6和结点7的符号都是负,于是以6为根结点左旋,最终得到平衡二叉树。