一:什么是 AVL 树?
在我的上一篇文章《二分搜索树与二分查找法》中,详细介绍了二分搜索树这种数据结构。二分搜索树最大的问题就是它并非是一棵平衡二叉树。
在给定的数据比较极端的情况下,譬如将一个递增数组中的元素依次添加到二分搜索树中,此时的二分搜素树就会退化为一个链表。
为了解决二分搜索树的这个问题,两位前苏联的计算机科学家 Georgy Adelson-Velsky 与 Evgenii Landis 发明了一种可以自平衡的二叉查找树,这种数据结构以两位科学家的名字的首字母命名,即:AVL 树。
我们再来回顾一下什么是平衡二叉树?
首先,平衡二叉树必须是一棵二分搜索树。它或者是一颗空树,或它的左子树与右子树的高度之差(左子树的高度 - 右子树的高度,其别名叫平衡因子:balance factor)的绝对值不超过 1,且一棵平衡二叉树的左右子树均是一棵平衡二叉树。
接下来,我们就一起探究一下 AVL 树这种数据结构是如何在二分搜索树的基础上做到可以自平衡的。
二:AVL 树的实现
1. 节点高度与平衡因子
AVL 树是如何实现自平衡的?
AVL 想要满足平衡二叉树的这个特性,就要保证所有节点的平衡因子的绝对值不超过 1。所以,AVL 树能够做到维持自平衡,实际上就是在树的结构发生变化时(向 AVL 中添加节点或删除节点),通过检测节点的平衡因子来调整树的结构。
AVL 树的节点除了存储左孩子与右孩子的引用以及自身的 value 值以外,还需要能够表示出当前节点的高度。
所以,AVL 树的节点类 Node 设计如下:
public class Node<E extends Comparable<E>> {
public E e;
public Node left;
public Node right;
public int height;
public Node(E e) {
this.e = e;
left = null;
right = null;
height = 1;
}
}
那么,在我们的 AVLTree 这个类中,就可以设计出两个方法。
第一个是获取当前节点的高度的方法:getHeight
:
/**
* 返回 node 节点的高度
*
* @param node
* @return
*/
private int getHeight(Node node) {
if (node == null)
return 0;
return node.height;
}
第二个是获取当前节点的平衡因子:getBalanceFactor
:
/**
* 获得节点 node 的平衡因子
*
* @param node
* @return
*/
private int getBalanceFactor(Node node) {
if (node == null)
return 0;
return getHeight(node.left) - getHeight(node.right);
}
2. 向 AVL 树中添加元素
我们先来回顾一下向二分搜索树中添加元素的逻辑:
如果当前二分搜索树的根节点为空,那么新插入的节点就会成为根节点。
如果当前二分搜索树的根节点不为空,就让根作为当前比较的节点:新插入的节点与当前节点进行比较;如果值比当前节点小就要“向左走”,如果值比当前节点大就要“向右走”,然后让下一层的节点继续作为当前比较的节点,直至走到应该插入的位置。
下图为在向当前的二分搜索树中添加节点“28”的流程:
Java 代码如下:
/**
* @param e 向二分搜索树中添加新的元素
*/
public void add(E e) {
root = add(e, root);
}
/**
* @param e 向二分搜索树中新插入的节点
* @param node 当前比较的节点
* @return 返回二分搜索树的根节点
*/
private Node add(E e, Node node) {
if (node == null) {
size++;
return new Node(e);
}
if (e.compareTo((E) node.e) < 0) {
node.left = add(e, node.left);
} else if (e.compareTo((E) node.e) > 0) {
node.right = add(e, node.right);
}
return node;
}
而向 AVL 树中添加元素就不是这么简单了。
对于向 AVL 树中添加一个节点,我们除了要保证二分搜索树的特性(二分搜索树的每个节点的值都要大于其左子树的所有节点的值,且小于其右子树的所有节点的值)外,还要保证维持平衡二叉树的特性。
我们思考一下,如果当前的 AVL 树是平衡的,那么哪些情况会使得 AVL 树变得不平衡呢?其实无非就是以下这四种:
第一种情况:插入的元素在不平衡节点的左子树的左侧
我们向当前的 AVL 树中插入元素“4”,导致节点“12”的平衡因子变为了 <font color="red">2</font>,出现了不平衡。
这种情况发生的条件为当前节点(“12”)的平衡因子大于 1,且当前节点的左子树的平衡因子大于等于 0,表达式表示为:
getBalanceFactor(node) > 1 && getBalanceFactor(node.left) >= 0
第二种情况:插入的元素在不平衡节点的右子树的右侧
我们向当前的 AVL 树中插入元素“18”,导致节点“12”的平衡因子变为了 <font color="red">-2</font>,出现了不平衡。
这种情况发生的条件为当前节点(“12”)的平衡因子小于 -1,且当前节点的右子树的平衡因子小于等于 0,表达式表示为:
getBalanceFactor(node) < -1 && getBalanceFactor(node.right) <= 0
第三种情况:插入的元素在不平衡节点的左子树的右侧
我们向当前的 AVL 树中插入元素“10”,导致节点“12”的平衡因子变为了 <font color="red">2</font>,出现了不平衡。
这种情况发生的条件为当前节点(“12”)的平衡因子大于 1,且当前节点的左子树的平衡因子小于 0,表达式表示为:
getBalanceFactor(node) > 1 && getBalanceFactor(node.left) < 0
第四种情况:插入的元素在不平衡节点的右子树的左侧
我们向当前的 AVL 树中插入元素“14”,导致节点“12”的平衡因子变为了 <font color="red">-2</font>,出现了不平衡。
这种情况发生的条件为当前节点(“12”)的平衡因子小于 -1,且当前节点的右子树的平衡因子大于 0,表达式表示为:
getBalanceFactor(node) < -1 && getBalanceFactor(node.right) > 0
左旋与右旋
我们已经知道,向 AVL 树中添加元素时,以上的四种情况会导致出现不平衡,那么如何让当前的树的结构变得平衡呢?
对于第一种情况,我们需要用到右旋的操作:
右旋操作如上图所示。所谓的右旋指的是,将不平衡的节点 “y” 顺时针旋转,使得上图中左侧的结构变为右侧的结构,此时,右侧的这棵树既满足二分搜索树的特性,也满足平衡二叉树的特性。
证明如下:
左侧的结构是一棵二分搜索树,满足:,变为右侧的结构之后,仍然有:,所以右侧的结构也是一棵二分搜索树。
设 与 中,最大高度为 ,所以节点 的高度为 ;节点 也是平衡的,其平衡因子大于等于 0 且小于等于 1;所以, 的高度不是 就是 , 的高度表示为 ; 节点是不平衡的,它的平衡因子一定是 2,所以, 的高度为 。
那么,左侧的结构通过右旋操作变为了右侧的结构之后, 的高度为 , 的高度为 , 的左右子树的高度差为 1,所以可证明,通过右旋,使得右侧的结构不仅是一棵二分搜索树,也是一棵平衡二叉树。
右旋操作的 Java 代码如下:
/**
* 右旋:
*
* y x
* / \ / \
* x T4 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 = Math.max(getHeight(y.left),getHeight(y.right)) + 1;
x.height = Math.max(getHeight(x.left),getHeight(x.right)) + 1;
return x;
}
类似地,对于第二种情况,我们需要用到左旋的操作:
左旋操作如上图所示。所谓的左旋指的是,将不平衡的节点 “y” 逆时针旋转,使得上图中左侧的结构变为右侧的结构,此时,右侧的这棵树既满足二分搜索树的特性,也满足平衡二叉树的特性。
左旋的正确性证明和右旋是一样的,我就不再赘述了。
左旋的 Java 代码如下:
/**
* 左旋:
*
* y x
* / \ / \
* T4 x y z
* / \ ========> / \ / \
* T3 z T4 T3 T1 T2
* / \
* T1 T2
*/
private Node leftRotate(Node y){
Node x = y.right;
Node T3 = x.left;
x.left = y;
y.right = T3;
// 更新 height
y.height = Math.max(getHeight(y.left),getHeight(y.right)) + 1;
x.height = Math.max(getHeight(x.left),getHeight(x.right)) + 1;
return x;
}
对于第三种情况,我们需要将不平衡节点 node 的左孩子先进行一次左旋,然后再对不平衡节点 node 进行右旋,这样就使得整棵树的结构既满足二分搜索树的特性,也满足平衡二叉树的特性了:
同理,对于第四种情况,我们需要将不平衡节点 node 的右孩子先进行一次右旋,然后再对不平衡节点 node 进行左旋,示意图如下:
向 AVL 树中添加元素的完整代码
通过上文的分析,我们已经知道了向 AVL 树中添加元素时,哪些情况会出现使得 AVL 树出现不平衡,以及这些不平衡的情况该如何解决。
向 AVL 树中添加元素的 Java 代码如下:
/**
* @param e 向 AVL 中添加新的元素
*/
public void add(E e) {
root = add(e, root);
}
/**
* @param e 向 AVL 中新插入的节点
* @param node 当前比较的节点
* @return 返回 AVL 的根节点
*/
private Node add(E e, Node node) {
if (node == null) {
size++;
return new Node(e);
}
if (e.compareTo((E) node.e) < 0) {
node.left = add(e, node.left);
} else if (e.compareTo((E) node.e) > 0) {
node.right = add(e, node.right);
}
// 更新 height
node.height = 1 + Math.max(getHeight(node.left), getHeight(node.right));
// 计算平衡因子
int balanceFactor = getBalanceFactor(node);
// 平衡的维护
// 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);
}
return node;
}
3. 向 AVL 树中删除元素
除了向 AVL 树中添加元素会导致树的结构发生变化以外,删除元素也会使得 AVL 树的结构发生变化,只要是树的结构发生变化,就有可能出现不平衡的节点,所以在二分搜索树中删除节点的代码的基础上,我们也要做可以实现自平衡性的修改。
我们先来回顾一下,向二分搜索树中删除节点的操作:
在二分搜索树中删除元素分为以下几种情况:
第一种情况为,我们删除的节点只有左子树没有右子树。
那么我们只需要让删除的节点的左孩子取代删除节点的位置即可。
第二种情况为,我们删除的节点只有右子树没有左子树。
我们只需要让删除节点的右孩子取代删除节点的位置即可。
第三种情况为,我们删除的节点既有左子树也有右子树。
对于这种情况,我们使用 Hibbard Deletion 算法。如果我们要删除一个既有左子树也有右子树的节点,首先需要找到待删除节点的后继节点(successor)。
对于二分搜索树而言,待删除节点的后继节点就是该节点右子树“最左的”那个节点,将后继节点替换待删除的节点就完成了删除操作。
在二分搜索树中删除一个元素的完整 Java 代码如下:
public void remove(E e) {
root = remove(e, root);
}
private Node remove(E e, Node node) {
if (node == null) {
return null;
}
if (e.compareTo((E) node.e) < 0) {
node.left = remove(e, node.left);
return node;
} else if (e.compareTo((E) node.e) > 0) {
node.right = remove(e, node.right);
return node;
} else {
if (node.left == null) {
Node rightNode = node.right;
node.right = null;
size--;
return rightNode;
}
if (node.right == null) {
Node leftNode = node.left;
node.left = null;
size--;
return leftNode;
}
// Hibbard Deletion
Node successor = minimum(node.right);
Node right = removeMin(node.right);
Node left = node.left;
successor.left = left;
successor.right = right;
node.left = null;
node.right = null;
return successor;
}
}
对于 AVL 树的删除节点的方法,我们只需要在二分搜索树中删除节点的方法之上,加入维护自平衡的部分即可。这个部分实际上和向 AVL 树中添加元素维护自平衡的原理是一样的。
向 AVL 树中删除节点的 Java 代码如下:
public void remove(E e) {
root = remove(e, root);
}
private Node remove(E e, Node node) {
if (node == null)
return null;
Node retNode;
if (e.compareTo((E) node.e) < 0) {
node.left = remove(e, node.left);
retNode = node;
} else if (e.compareTo((E) node.e) > 0) {
node.right = remove(e, node.right);
retNode = node;
} else {
// 待删除节点的左子树为空
if (node.left == null) {
Node rightNode = node.right;
node.right = null;
size--;
retNode = rightNode;
}
// 待删除的节点右子树为空时
else if (node.right == null) {
Node leftNode = node.left;
node.left = null;
size--;
retNode = leftNode;
}
// 待删除的节点左右子树均不为空
else {// Hibbard Deletion
Node successor = minimum(node.right);
Node right = remove((E) node.right, successor);
Node left = node.left;
successor.left = left;
successor.right = right;
node.left = null;
node.right = null;
retNode = successor;
}
}
if(retNode == null)
return null;
// 更新 height
retNode.height = 1 + Math.max(getHeight(retNode.left), getHeight(retNode.right));
// 计算平衡因子
int balanceFactor = getBalanceFactor(retNode);
// 平衡的维护
// LL
if (balanceFactor > 1 && getBalanceFactor(retNode.left) >= 0)
return rightRotate(retNode);
// RR
if(balanceFactor < -1 && getBalanceFactor(retNode.right) <= 0)
return leftRotate(retNode);
// LR
if(balanceFactor > 1 && getBalanceFactor(retNode.left) < 0) {
retNode.left = leftRotate(retNode.left);
return rightRotate(retNode);
}
// RL
if(balanceFactor < -1 && getBalanceFactor(retNode.right) > 0) {
retNode.right = rightRotate(retNode.right);
return leftRotate(retNode);
}
return retNode;
}
三:AVL 树与二分搜索树的性能测试
在完成 AVL 树的性能测试前,我们需要两个验证方法,第一个是验证当前的 AVL 树满足二分搜索树的特性,第二个是验证当前的 AVL 树是一棵平衡二叉树。
这两个方法的实现也非常简单:
/**
* 验证当前的 AVL 树是否满足二分搜索树的特性
*
* @return
*/
public boolean isBST() {
ArrayList<E> list = new ArrayList<>();
inOrder(root, list);
for (int i = 1; i < list.size(); i++)
if (list.get(i - 1).compareTo(list.get(i)) > 0)
return false;
return true;
}
/**
* @param node 中序遍历以 node 为 根的 AVL
*/
private void inOrder(Node node, List<E> list) {
if (node == null) {
return;
}
inOrder(node.left, list);
list.add((E) node.e);
inOrder(node.right, list);
}
/**
* 验证当前的二叉树是否是一棵平衡的二叉树
*
* @return
*/
public boolean isBalanced() {
return isBalanced(root);
}
/**
* 验证当前的二叉树是否是一棵平衡的二叉树
*
* @param node
* @return
*/
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);
}
我们的性能测试代码如下:
class AVLTreeTest {
@Test
void AVLAndBSTPerformanceTest() {
int[] testArr = new int[20000];
for (int i = 0; i < testArr.length; i++)
testArr[i] = i;
testBst(testArr);
testAvl(testArr);
}
@Test
void AVLTest(){
AVLTree<Integer> avl = new AVLTree<>();
for (int i = 0; i < 1000; i++){
avl.add(i);
if(!avl.isBalanced() || !avl.isBST())
throw new RuntimeException("error!");
}
for(int i = 0; i < 1000; i++){
avl.remove(i);
if(!avl.isBalanced() || !avl.isBST())
throw new RuntimeException("error!");
}
System.out.println("correct!");
}
private void testBst(int[] testArr) {
BST<Integer> bst = new BST<>();
long start = System.nanoTime();
for (int i = 0; i < testArr.length; i++)
bst.add(i);
for (int i = 0; i < testArr.length; i++)
if (!bst.contains(i)) throw new RuntimeException("error");
long end = System.nanoTime();
System.out.println("BST : " + (end - start) / 1000000000.0 + " s");
}
private void testAvl(int[] testArr) {
AVLTree<Integer> avl = new AVLTree<>();
long start = System.nanoTime();
for (int i = 0; i < testArr.length; i++)
avl.add(i);
for (int i = 0; i < testArr.length; i++)
if (!avl.contains(i)) throw new RuntimeException("error");
long end = System.nanoTime();
System.out.println("AVL : " + (end - start) / 1000000000.0 + " s");
}
}
我们的性能测试非常简单,首先初始化一个容量为 20000 的单调递增的数组,然后将数组所有的元素依次添加到二分搜索树与 AVL 树这两种数据结构中,并在所有元素添加完毕后,依次执行查询操作。
由于数组是单调递增的,我们的二分搜索树会退化为一个链表,添加和查询元素的时间复杂度均为;而 AVL 树则因为其自平衡的特性使得添加和查找元素的复杂度为 。
在我的计算机上,AVLAndBSTPerformanceTest 这个单元测试的执行结果为:
BST : 1.935773389 s
AVL : 0.018965793 s
我们可以看到,二者的差异是巨大的。
四:总结
在这一篇文章中,我介绍了 AVL 树这种数据结构以及 AVL 树是如何通过左旋和右旋来实现自平衡的。并且,我们通过一个小的测试来验证在数据极端的情况下,AVL 树和二分搜索树的性能差异。
AVL 树是计算机科学中,最早被发明的自平衡二叉查找树,除了 AVL 外,还有很多优秀的平衡二叉查找树这种数据结构,期待在后面的文章中,我可以与你一同研究与学习。
本文中使用的代码均在:
https://github.com/jinrunheng/datastructure-and-algorithm/
好啦,至此为止,这一篇文章我就介绍完毕了~欢迎大家关注我的公众号【kim_talk】,在这里希望你可以收获更多的知识,我们下一期再见!