十三、彻底搞懂平衡二叉树AVL
这是EZ大数据的第17篇原创文章
当我不想做事的时候，我会抗拒；当我乐于做的时候，没有什么能阻挡我。
--达利欧《原则》
1
今天来个重头戏：平衡二叉树AVL。
由前面对二分搜索树的研究可知，在最坏的情况下，二分搜索树会退化成链表，此时时间复杂度为 O(n)。
因此我们引入平衡二叉树，它是一种结构平衡的二分搜索树。那么，在二分搜索树的基础上，平衡二叉树需要满足两个条件：
1.它的左右两个子树的高度差的绝对值不超过1
2.左右两个子树都是一颗平衡二叉树
AVL树是最早的自平衡二分搜索树结构，AVL树维护自身的平衡涉及到两个概念：
1.节点的高度
2.平衡因子：左子树的高度减去右子树的高度。
平衡因子的取值只可能为0，-1，1。分别对应着左右子树等高，左子树比较高，右子树比较高。如果平衡因子绝对值大于等于2，那么就不是平衡二叉树。
2
对于平衡二叉树的判断，首先我们要判断是否为二分搜索树，根据之前的总结，根节点大于左子树节点同时小于右子树节点，我们用中序遍历来判断一棵树是否为二分搜索树。具体如下：
// 判断该二叉树是否是一棵二分搜索树
public boolean isBST() {
ArrayList<K> keys = new ArrayList<>();
inOrder(root, keys);
for (int i = 1; i < keys.size(); i++) {
// 判断左节点和右节点大小
if (keys.get(i - 1).compareTo(keys.get(i)) > 0) {
return false;
}
}
return true;
}
private void inOrder(Node node, ArrayList<K> keys) {
if (node == null) {
return;
}
inOrder(node.left, keys);
keys.add(node.key);
inOrder(node.right, keys);
}
接下来我们计算节点的高度和平衡因子的值。初始设定高度height=1，那么节点高度的变化和平衡因子的计算，主要是在添加元素时，那么现在就需要修改之前我们BST的代码：
// 获得节点node的高度值
private int getHeight(Node node) {
if (node == null) {
return 0;
}
return node.height;
}
// 获得节点node的平衡因子
private int getBalanceFactor(Node node) {
if (node == null) {
return 0;
}
return getHeight(node.left) - getHeight(node.right);
}
// 向以node为根的二分搜索树中插入元素(key, value)，递归算法
private Node add(Node node, K key, V value) {
if (node == null) {
size++;
return new Node(key, value);
}
if (key.compareTo(node.key) < 0) {
node.left = add(node.left, key, value);
} else if (key.compareTo(node.key) > 0) {
node.right = add(node.right, key, value);
} else // key.compareTo(node.key) == 0
{
node.value = value;
}
// 更新height
node.height = 1 + Math.max(getHeight(node.left), getHeight(node.right));
// 计算平衡因子
int balanceFactor = getBalanceFactor(node);
if (Math.abs(balanceFactor) > 1) {
System.out.println("unbalanced: " + balanceFactor);
}
return node;
}
如上代码所示，当插入元素时，节点的高度发生变化，并且当前位置节点的高度=1+左右节点高度最大值。在计算平衡因子中，主要是获取左右节点高度的差值。
那么现在我们来判断是否为一棵平衡二叉树。
判断标准即为，左子树和右子树高度差的绝对值是否大于1。采用递归思想实现代码：
// 判断该二叉树是否是一棵平衡二叉树
public boolean isBalanced() {
return isBalanced(root);
}
private boolean isBalanced(Node node) {
if (node == null) {
return true;
}
int balanceFactor = getBalanceFactor(node);
if (Math.abs(balanceFactor) > 1) {
return false;
}
return isBalanced(node.left) && isBalanced(node.right);
}
3
当我们插入元素时，有可能破坏平衡二叉树的结构，所以当加入节点后，需要沿着节点向上维护平衡性。
最小失衡子树：在新插入的结点向上查找，以第一个平衡因子的绝对值超过1的结点为根的子树称为最小不平衡子树。
平衡二叉树的失衡调整主要是通过旋转最小失衡子树来实现，左旋与右旋。
现在来看左旋RR：插入的元素在不平衡的节点的右子树的右子树。此时的操作主要是：
1.节点的右孩子替代此节点位置
2.右孩子的左子树变为该节点的右子树
3.节点本身变为右孩子的左子树
如下图所示：
节点的右孩子替代此节点位置 —— 节点 66 的右孩子是节点 75 ，将节点 75 代替节点 66 的位置；
右孩子的左子树变为该节点的右子树 —— 节点 75 的左子树为节点 70，将节点 70 挪到节点 66 的右子树位置；
节点本身变为右孩子的左子树 —— 节点 66 变为了节点 75 的左子树。
具体实现代码如下：
// 对节点y进行向左旋转操作，返回旋转后新的根节点x
// y x
// / \ / \
// T1 x 向左旋转 (y) y z
// / \ - - - - - - - -> / \ / \
// T2 z T1 T2 T3 T4
// / \
// T3 T4
private Node leftRotate(Node y){
Node x = y.right;
Node T2 = x.left;
// 向左旋转过程
x.left = y;
y.right = T2;
// 更新height
y.height = 1 + Math.max(getHeight(y.left), getHeight(y.right));
x.height = 1 + Math.max(getHeight(x.left), getHeight(x.right));
return x;
}
现在我们来看右旋LL：插入的元素在不平衡的节点的左子树的左子树。此时的主要操作是：
1.节点的左孩子替代此节点
2.节点的左孩子的右子树变为节点的左子树
3.节点本身变为左孩子的右子树
示意图如下：
实现逻辑类似左旋RR。
直接看代码实现：
// 对节点y进行向右旋转操作，返回旋转后新的根节点x
// y x
// / \ / \
// x T4 向右旋转 (y) z y
// / \ - - - - - - - -> / \ / \
// z T3 T1 T2 T3 T4
// / \
// T1 T2
private Node rightRotate(Node y) {
Node x = y.left;
Node T3 = x.right;
// 向右旋转过程
x.right = y;
y.left = T3;
// 更新height
y.height = 1 + Math.max(getHeight(y.left), getHeight(y.right));
x.height = 1 + Math.max(getHeight(x.left), getHeight(x.right));
return x;
}
现在我们来看两个稍微难点的LR和RL。
LR：插入的元素在不平衡的节点的左子树的右子树。
示意图如下：
此时的解决办法就是，先进行左旋转，将树结构调整为LL结构，然后再进行右旋转，实现AVL。
RL：插入的元素在不平衡的节点的右子树的左子树。
示意图如下：
此时的解决办法为：先进行右旋转，然后再进行左旋转。
综合上述四种情况，实现汇总代码如下：
// 平衡维护
// LL
if (balanceFactor > 1 && getBalanceFactor(node.left) >= 0) { // 此时说明是在左子树的左子树添加元素，使用右旋转
return rightRotate(node);
}
// RR
if (balanceFactor < -1 && getBalanceFactor(node.right) <= 0) { // 此时说明是在右子树的右子树添加元素，使用左旋转
return leftRotate(node);
}
// LR
if (balanceFactor > 1 && getBalanceFactor(node.left) < 0) { // 此时说明是在左子树的右子树添加元素，先使用左旋转，再使用右旋转
node.left = leftRotate(node.left);
return rightRotate(node);
}
// RL
if (balanceFactor < -1 && getBalanceFactor(node.right) > 0) { // 此时说明是在右子树的左子树添加元素，使用右旋转，再使用左旋转
node.right = rightRotate(node.right);
return leftRotate(node);
}
关于平衡二叉树AVL的总结，今天就到这里，在总结过程中，对于二分搜索树以及AVL的特点有了更深的理解。同时对于递归思想的实现也有了更深刻的认识。特别有意思的就是左旋RR、右旋LL以及更为复杂的RL和LR的操作。
后续再总结一波红黑树。
今天就到这里吧，拜了个拜~
-----------------------
微博：EZ大数据
知乎：EZ大数据
记录自己的学习，工作，生活，还有那些坑，那些苦逼……
长按下图二维码关注，不用怀疑，你能获得很多东东
-----------------------