Java数据结构与算法(树)——平衡二叉树(AVL树)
一、定义
平衡二叉查找树(Balanced Binary Sort Tree,BBST)简称平衡二叉树,是一种高度平衡的二叉树,由苏联数学家 Adele - Veliki 和 Landis 在 1962 年提出,故又命名为 AVL 树。
平衡二叉树的性质:首先是一种二叉查找树,并且其中每个节点的左子树和右子树的高度相差至多等于 1。
平衡因子BF(Balance Factor)——将二叉树上节点的左子树高度减去右子树高度的值称为平衡因子。平衡二叉树上,所有节点的平衡因子只可能是 -1,0,1。
最小不平衡子树——距离插入节点最近的,且平衡因子的绝对值大于 1 的节点为根的子树。以下图为例,左图是一棵平衡二叉树,当插入节点 1 时,节点 4 的 BF = 2(左子树高度 - 右子树高度 = 2 - 0 = 2),则以节点 4 为根节点的子树即为最小不平衡子树。
二、构建平衡二叉树及不平衡情况的处理方法
构建平衡二叉树的基本思想就是在构建二叉搜索树的过程中,每当插入一个新节点时,先检查是否因插入而破坏了树的平衡性,若是,则在保持二叉搜索树特性的前提下,调整最小不平衡子树中各节点之间的链接关系,进行相应的旋转调整,使之成为新的平衡二叉树。
注意:
不平衡的情况其实千变万化,比如左边深度为一万,右边深度为 0。但是我们考虑的是,在平衡二叉树中修改一个节点以后引起的不平衡,所以,左右子树的差的绝对值只能为 2。
旋转的情况:
(1)单旋:
最小不平衡子树的根节点的 BF 与它的子树的 BF 符号相同时,需要一次旋转。最小不平衡子树的根节点的 BF 大于 1 时,右旋;小于 -1 时,左旋。
(2)双旋:
最小不平衡子树的根节点的 BF 与它的子树的 BF 符号相反时,需要两次旋转,即先对子树进行一次旋转后使得 BF 符号相同之后,再反向旋转一次完成平衡。
1、左左(右旋)
插入节点 1 时,原平衡二叉树失衡,右旋过程图示如下:
最小不平衡子树的根节点 6 的 BF = 2,左子树根节点 4 的 BF = 1,同号且大于 1,右旋。具体操作:
- 当前根节点的左子树的右子树变成当前根节点的左子树(因为它满足大于左子树且小于根节点的要求);
- 原根节点的左子树变成新的根节点;
- 原根节点变成新根节点的右子树。
2、右右(左旋)
插入节点 8 时,原平衡二叉树失衡,左旋过程图示如下:
最小不平衡子树的根节点 4 的 BF = -2,右子树根节点 6 的 BF = -1,同号且小于 -1,左旋。具体操作:
- 当前根节点的右子树的左子树变成当前根节点的右子树;
- 原根节点的右子树变成新的根节点;
- 原根节点变成新根节点的左子树。
3、双旋
如下图,插入节点 8 时,最小不平衡子树的根节点 9 的 BF = 2,左子树根节点 6 的 BF = -1,反号,仅一次单旋不能解决问题。
解决方法:
双旋:最小不平衡子树的左子树根节点 6 的 BF = -1,先左旋最小不平衡子树的左子树,再右旋最小不平衡子树。如下图所示:
先右旋再左旋的情况类似。