AVL树

发表于 | | 阅读次数:

什么是AVL树？

AVL树，又称为平衡二叉树，它是一种特殊的二叉查找树（Binary Search Tree, BST），其每一个节点的左右子树的高度差不超过1。

注意，一个节点的高度是从该节点到叶子节点的最长路径，所以，叶子节点的高度为0,而深度是指一个节点到树根的路径长度，两者是相反的概念。 一棵树的高度等于根节点的高度，而深度等于最大深度的叶子节点的深度，所以一个树的高度和深度是相同的。

二叉查找树的定义是递归的：1）左子树所有节点的值都比根节点小，右子树所有的节点都比根节点大，2）左子树和右子树都是二叉查找树。

当所有的插入序列都是等可能的情况下，二叉查找树的平均深度是O(log N)，但是当遇到极端情况（比如插入有序的序列）或者多次的插入\删除操作会使得二叉查找树的深度变大，而平衡二叉树加大了对二叉查找树的限制：任何一个节点的左右子树的高度差不能超过1，这就保证了平衡二叉树的深度为O(log N),使得平衡二叉树的最坏的查找效率是O(log N)，而二叉查找树的最坏查找效率可以是O(N)。那么问题的关键就是如何在插入和删除的时候保持平衡二叉树的性质。

如何在插入一个节点的时候保持树的平衡？

当插入一个新的节点的时候，如果插入的新节点使得一些节点的左右子树的高度差等于了2，那么这时候就需要旋转(rotation)来调整不平衡的子树，使得整个树仍然保持平衡二叉树的性质。导致不平衡插入只有四种情况：

  1. 左左，即插入点为不平衡节点的左儿子的左子树中，使得原来平衡节点的左子树比右子树高1，变成现在变成高2了。
  2. 右右，即插入点为不平衡节点的右儿子的右子树中，使得原来平衡节点的右子树比左子树高1，变成现在变成高2了，他是第一种情况的对称情况
  3. 左右，即插入点为不平衡节点的左儿子的右子树中，使得原来平衡节点的左子树比右子树高1，变成现在变成高2了。
  4. 右左，即插入点为不平衡节点的右儿子的左子树中，使得原来平衡节点的右子树比左子树高1，变成现在的高2，它是第三种情况的堆成情况。

我们先看前两种情况的处理方式（单旋转）:

左左的情况如下图1所示, k1为不平衡节点，由于新节点的插入到了X子树，使得k1的左子树的高度比右子树的高度差2，这时候，我们只需要做单旋转操作：1）把k1的右孩子变成k2(k1的左孩子)的右子树，2）把k2的左孩子变成k1,返回平衡后的树根k2。相同的图2显示了右右单旋转的操作过程



图1：左左单旋转



图2：右右单旋转

如果不平衡情况是第3，4种，那么单选并不能使得树变平衡，以第3种情况为例，我们使用单旋转来改变树的形态，其过程如图3所示，显然，单旋转不能使得左右的不平衡的状态达到平衡。



图3：单旋转不能处理左右不平衡的情况

那么第三种和第四种情况如何处理呢，我们不能再把k2提上去作为树的根了，那么如果我们把Y子树的根 作为新的树根呢，这是一个可行的方案，这就是双旋转最初的想法。

以第三种情况为例（见图4），也就是插入点位于不平衡节点的左孩子的右子树上，我需要两次旋转来调整树达到平衡，首先将k3（k2的右孩子）左旋转到k2的位置，然后在将k2通过单旋转到k1的位置，整个过程如图4所示，红线为需要变动的链接。其中，在k3左旋转到k2位置上时需要将k3的左子树变成k2的右子树，在k3右转到k1位置的时候需要将k3的右子树变成k1的右子树。图5展示了右左不平衡的情况的双旋转。



图4：左右双旋转



图5：右左双旋转

Java AVL树插入的实现

在上面的解释中，我们有一个重要的问题没有解决，也就是在插入后如何确定不平衡点。实际上，我们在插入后需要进行回溯去找到不平衡的父节点，回溯的方法有多种，比如用栈存储插入节点对比的路径，从栈中取出存储信息，另一种方法是使用递归，其实也是隐式的使用栈的操作，再用一种是在树的结构中保持父节点的引用，但是这会占用更多的内存。我的实现使用了栈的操作，接着后面分析了<数据结构与算法分析-Java语言描述>一书中递归的实现，后者的实现更巧妙，是值得推荐的操作，我自己的使用栈的实现原则上是和它一样的，但是它能跟让我深刻的理解递归背后的详细操作。

另一个讨论是在回溯的过程中是否有必要回溯所有的父节点，答案是必要的，尽管我们在调整的时候只有一个节点需要调整，也就是在一次过程中我们最多调整一个不平衡节点就使得整个树归于平衡，但是我们需要更新所有父节点的平衡信息，这个信息可以是高度或者高度差，我们的实现中使用高度。

另外一个问题，单旋只需要单次旋转，而双旋需要两次旋转，其实现方式是否不同？ 其实从双旋的过程来看，其实现和单旋一样，都归结到左旋和右旋操作，也就是把右儿子调整到父节点的位置，或者把左儿子调整到父节点的位置，这是两个基本的操作。我们写出正两个基本操作的伪代码。

1
2
3
4
5
6
7
8
9
描述：旋转一个节点的左孩子到父节点位置
输入：待旋转节点k1
输出：旋转后的树根
	k2=k1的左孩子
	让k1的左指针指向k2的右孩子
	让k2的右指针指向k1
	更新k1的高度信息为max(k1左孩子的高度，k1右孩子的高度）+1
	更新k2的高度信息为max（k2左孩子的高度，k1的高度）+1
	返回k2

相同的，我们也可以写出旋转一个节点的右孩子到父节点的位置

1
2
3
4
5
6
7
8
9
描述：旋转一个节点的右孩子到父节点位置
输入：待旋转节点k1,
输出：旋转后的树根
	k2=k1的右孩子
	让k1的右指针指向k2的的左孩子
	让k2左指针指向k1
	更新k1的高度信息为max(k1左孩子的高度，k1右孩子的高度)+1
	更新k2的高度信息为max（k1的高度，k2右孩子孩子的高度）+1
	返回k2

那么我们可以轻易的写出这两个函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
private int height(AvlNode<T>node) {//高度函数，在节点为null的时候返回-1
	return node==null?-1:node.height;
}
private AvlNode<T> rotateWithLeftChild(AvlNode<T> k1){
	AvlNode<T> k2=k1.left;
	k1.left=k2.right;//k1的左子树换成k2的右子树
	k2.right=k1;//k2的右子树变k1
	k1.height=Math.max(height(k1.left), height(k1.right))+1;
	k2.height=Math.max(height(k2.left), k1.height)+1;//k1现在是k2的右子树根
	return k2;
}
private AvlNode<T> rotateWithRightChild(AvlNode<T> k1){
	AvlNode<T> k2=k1.right;
	k1.right=k2.left;
	k2.left=k1;
	k1.height=Math.max(height(k1.left), height(k1.right))+1;
	k2.height=Math.max(k1.height, height(k2.right))+1;//k1现在是k2的左子树根
	return k2;
}

单旋转操作只需要调用上面的单次旋转操作即可，而双旋转需要两次旋转操作，以左右不平衡来说，我们的解决思路如一下伪代码：

1
2
3
4
5
6
7
描述：左右不平衡条件下的双旋转操作
输入：不平衡节点k1
输出：新的平衡树根
	k2=k1的左孩子
	k1的左孩子=旋转k2的右孩子到k2的位置后的新树根（rotateWithRightChild(k2)）
	newRoot=旋转k1的左孩子到k1的位置后的新树根（rotateWithLeftChild(k1)）
	返回newRoot

相信看了这个伪代码，你也可以很容易的写出右左不平衡条件下的双旋转操作，这里就不再写出。
其代码实现如下：

1
2
3
4
5
6
7
8
9
10
11
private AvlNode<T> doubleRotateWithLeftChild(AvlNode<T> k1){
	AvlNode<T> k2=k1.left;
	k1.left=rotateWithRightChild(k2);
	return rotateWithLeftChild(k1);
}
private AvlNode<T> doubleRotateWithRightChild(AvlNode<T> k1){
	AvlNode<T>k2=k1.right;
	k1.right=rotateWithLeftChild(k2);
	return rotateWithRightChild(k1);
}

实现了基本旋转操作之后，我们就可以在这个基础上编写一个调整函数来判定一个节点应该做什么样的调整，输入的节点可以是树中的任何一个节点，我们这个函数要做的有两件事情1）判定该节点是不是不平衡节点，如果是，则完成调整操作，2）更新该节点的高度信息。尽管旋转操作中更新了高度信息，我们还要照顾不需要旋转的情况，所有在算法结尾我们还是要重新计算一下根节点的高度，该其基本思路是如下伪代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
描述：平衡一个节点并返回平衡后的树根
输入：树的一个节点k1
输出：新的平衡树根
	if k1为null
		直接返回k1
	if k1左子树的高度-右子树的高度>1 //k1为不平衡节点，并且是左子树高的情况
		k2=k1左子树根
		if k2左子树的高度>=右子树的高度 //左左不平衡的情况
		//在插入的情况下只有大于，但是在删除的情况下有可能等于，这个情况会在删除中详细讨论。
			k1=rotateWithLeftChild(k1)
		else //左右不平衡的情况，双旋
			k1=doubleRotateWithLeftChild(k1)
	elseif k1的右子树的高度-左子树的高度>1 //右子树高的情况
		if k1的右子树的高度>=左子树的高度
			k1=rotateWithRightChild(k1)
		else//右左不平衡的情况
			k1=doubleRotateWithRightChild(k1)
	计算根节点k1新的高度值k1.height为其左右子树高度值的最大值+1
	返回新最终根节点k1

其代码实现我们用一个叫做balance的函数实现，其实现过程遵循前面的算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public AvlNode<T> balance(AvlNode<T> k1){
	if(k1==null)
		return k1;
	if(height(k1.left)-height(k1.right)>1) {//左子树更高的情况
		AvlNode<T> k2=k1.left;
		if(height(k2.left)>=height(k2.right)) {//左左不平衡情况
			k1=rotateWithLeftChild(k1);
		}else {//左右不平衡情况
			k1=doubleRotateWithLeftChild(k1);
		}
	}else if(height(k1.right)-height(k1.left)>1) {//右子树更高的情况
		AvlNode<T>k2=k1.right;
		if(height(k2.right)>=height(k2.left)) {//右右不平衡的情况
			k1=rotateWithRightChild(k1);
		}else {//右左不平衡的情况
			k1=doubleRotateWithRightChild(k1);
		}
	}
	//再算一遍新根的高度，处理非不平衡的情况
	k1.height=Math.max(height(k1.left), height(k1.right))+1;
	return k1;
}

完成了一个节点的平衡，我们就可以继续推进，接下来的问题就是执行插入，并且在插入后进行回溯，对回溯到节点执行balance操作即可。其算法思想如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
描述：向一个树中插入一个节点
输入：插入节点值为x, 待插入树的树根root
输出：插入节点x的后的平衡二叉树根
初始化:pathStack用于存储对比路径
	if root等于null
		返回 节点值为x的新节点
	currentNode初始化为root
	while currentNode不为null do
		if x<currentNode节点的值//插入点在左子树上
			pathStack.push(currentNode)
			currentNode=currentNode的左孩子
		elseif x>currentNode节点的值//插入点在右子树上
			pathStack.push(currentNode)
			currentNode=currentNode的右孩子
		else//等于的情况,说明节点已经存在
			直接返回root
	currentNode=pathStack.pop()//返回待插入节点的父节点
	if x>currentNode节点的值
		currentNode的右孩子=newNode(x)
	else
		currentNode的左孩子=newNode(x)
	while pathStack不为空 do
		nextNode=pathStack.pop()
		if nextNode的左孩子等于currentNode
			nextNode的左孩子=balance(currentNode)
		else if nexNode的右孩子等于currentNode
			nextNode的右孩子=balance(currentNode)
		currentNode=nextNode
	//当栈为空的时候还有最后一个节点没有balance，它就是currentNode
	返回 balance(currentNode)

实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public AvlNode<T> insert(T x, AvlNode<T>root){
	Stack<AvlNode<T>> pathStack=new Stack<>();
	if(root==null)
		return new AvlNode<T>(x);
	AvlNode<T> currentNode=root;
	while(currentNode!=null) {
		if(x.compareTo(currentNode.element)<0) {
			pathStack.push(currentNode);
			currentNode=currentNode.left;
		}else if(x.compareTo(currentNode.element)>0) {
			pathStack.push(currentNode);
			currentNode=currentNode.right;
		}else {
			return root;
		}
	}
	
	currentNode=pathStack.pop();
	if(x.compareTo(currentNode.element)<0)
		currentNode.left=new AvlNode<T>(x);
	else
		currentNode.right=new AvlNode<T>(x);
	while(!pathStack.isEmpty()) {
		AvlNode<T>nextNode=pathStack.pop();
		if(nextNode.right==currentNode)
			nextNode.right=balance(currentNode);
		else if(nextNode.right==currentNode)
			nextNode.left=balance(currentNode);
		currentNode=nextNode;
	}
	//剩余最后一个 节点没有balance
	return balance(currentNode);
}

另外一种是使用递归的方式来进行插入平衡，其核心思想如下：

1
2
3
4
5
6
7
8
9
10
11
描述：向一个树中插入一个节点
输入：插入节点值为x, 待插入树的树根root
输出：插入节点x的后的平衡二叉树根
	if root为null
		返回新节点newNode(x)
	if x>root的值
		root的右孩子=以root的右孩子作为树根插入x
	if x<root的值
		root的左孩子=以root的左孩子作为树根插入x
	newRoot=balance当前的树根至平衡节点
	return newRoot

代码实现很简洁

1
2
3
4
5
6
7
8
9
10
11
public AvlNode<T> insertRecursive(T x, AvlNode<T>root){
	if(root==null) {
		return new AvlNode<T>(x);
	}
	
	if(x.compareTo(root.element)>0)
		root.right=insertRecursive(x, root.right);
	else if(x.compareTo(root.element)<0)
		root.left=insertRecursive(x, root.left);
	return balance(root);
}

测试代码，插入31个有序Integer数字，并且按层打印，看其功能性，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public static void main(String[] args) {
	int MAX=1000000;
	long current=System.currentTimeMillis();
	AvlTree<Integer>avlTree=new AvlTree<>();
	for(int i=1;i<=MAX;i++) {
		avlTree.insert(i);
	}
	long end=System.currentTimeMillis();
	System.out.println("建立平衡二叉树时间："+(end-current)+"ms");
	//层序遍历按层打印该树
	Queue<AvlNode<Integer>>queue=new LinkedList<>();
	int cur=1;//当前层需要遍历的个数
	int next=0;//下一次需要遍历的个数
	queue.offer(avlTree.getRoot());
	while(!queue.isEmpty()) {
		AvlNode<Integer>curNode=queue.poll();
		System.out.print(curNode.element+"  ");
		cur--;
		if(curNode.left!=null) {
			queue.offer(curNode.left);
			next++;
		}
		if(curNode.right!=null) {
			queue.offer(curNode.right);
			next++;
		}
		
		if(cur==0) {
			System.out.println();
			cur=next;
			next=0;
		}
	}
}

运行结果如图6所示，2微秒建立的平衡二叉树，可以看出有序插入点情况下建立的是完全二叉树。


图6:测试结果

两种方式均能正确的完成平衡二叉树的插入，那么时间性能又如何呢，我们插入100,0000个数字做对比。结果是递归为1039ms，非递归为1263ms,两者相差不大，在平衡二叉树中递归的方式更高效一点。

Java AVL树删除的实现

在探讨AVL树的删除之前，我们先谈论二叉查找树的删除，其实二叉查找树的删除的解决的主要问题是：在删除掉指定节点后如何将被删除节点再连接到被删除节点的父节点上，使其继续保持二叉查找树的性质。在删除的过程中，我们总共可能会遇到三种情况，解决了这三种情况下的删除，也就解决了主要问题。

  • 待删除节点的左右子树为空。这种情况直接删除待删除节点，并且置待删除节点为null
  • 待删除节点有左儿子或右儿子。直接用左儿子或者右儿子代替待删除节点的位置
  • 待删除节点既有左儿子又有右儿子。做法是将待删除节点换成其右子树上节点最小的值，并删除最小值的节点，这种做法的考量是待删除节点的右子树的最小值一定没有左孩子，这样可以在删除该节点的时候更容易。

按照上面的想法，我们给出二叉查找树删除一个节点的递归过程的伪代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
描述：在二叉查找树上删除一个节点
输入：删除的节点值x，待删除节点二叉查找树的树根root
输出：删除节点后二叉查找树的树根
	if t=null
		未找到，直接返回null
	if x>root的值
		x在右子树上
		root.right=以root.right为树根删除x后的新树根
	else if x<root的值
		x在左子树上
		root.left=以root.left为树根删除x后的新树根
	//开始x=root的值
	else if root.left==null并且root.right==null
		直接返会null
	else if root.left!=null并且root.right!=null
		root的值=root.right上的最小值
		root.right=以root.right为树根删除root.right上的最小值后的新树根
	else
		root的左子树不为空或者右子树不为空
		root=root.left和root.right不为空者
	返回root

其实现Java实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public AvlNode<T> remove(T x, AvlNode<T>root){
		if(root==null)
			return null;
		if(x.compareTo(root.element)>0) {
			root.right=remove(x,root.right);
		}else if(x.compareTo(root.element)<0) {
			root.left=remove(x,root.left);
		}else if(root.left!=null&&root.right!=null) {
			root.element=findMin(root.right).element;
			root.right=remove(root.element,root.right);
		}else {
			root=(root.left==null?root.right:root.left);
			//这种情况涵盖了左右子树都为空和只有左子树或右子树的情况
			//如果都为空，那么会root会返回null，如果 左儿子为空，则会返回右孩子的引用
		}
		return root;
	}

了解了二叉查找树的删除情况及其实现方式，其实我们很容易想到如何删除AVL树中的一个节点，其实前面的步骤都是相似的，我们只需要在每次删除后进行balance调整，由于整个过程是个递归的过程，所以最终在删除结束后会进行类似插入一样的回溯过程。整个Java实现只需要将最后一行return root，变成return balance(root)，其代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public AvlNode<T> remove(T x, AvlNode<T>root){
		if(root==null)
			return null;
		if(x.compareTo(root.element)>0) {
			root.right=remove(x,root.right);
		}else if(x.compareTo(root.element)<0) {
			root.left=remove(x,root.left);
		}else if(root.left!=null&&root.right!=null) {
			root.element=findMin(root.right).element;
			root.right=remove(root.element,root.right);
		}else {
			root=(root.left==null?root.right:root.left);
			//这种情况涵盖了左右子树都为空和只有左子树或右子树的情况
			//如果都为空，那么会root会返回null，如果 左儿子为空，则会返回右孩子的引用
		}
		return balance(root);
	}

测试我们建立1-31的二叉平衡树，然后删除8，结果如下，可以看到，8删除的位置被9顶底，10的左子树没了：


图7：删除测试结果

本文全部源码请点击这里AVLTree

大功告成，放学校美图一张^_^



补充：
我们在balance的算法中在对比的过程中，其中用到了大于等于和小于等于而不是大于或者等于，如图8红色框内所示,我们是在k2左子树的高度大于等于右子树的高度进行左孩子单旋转，而不是大于，原因在于什么？插入过程中，如果遇到了左左不平衡情况，那么k2的左子树高度一定是大于右子树的高度，大于等于是包括大于的，所以在插入不平衡的情况并不影响其功能性。

关键在于我们在删除的时候也复用的balance函数，而删除的情况却会遇到这种左子树右右子树的情况，这种是什么情况呢，如图9所示.



图8：等于的情况

假设右子树最后一层近剩一个k3,那么删除k3的结果会导致左左不平衡，并且左子孩子的左右子树均相等。这种情况单旋转即可恢复平衡。那么左右双旋转是否也可以恢复平衡，答案是肯定的，详细见图10。


图9：左左不平衡，左孩子左右子树高度相等的情况，单旋转操作可以恢复平衡

图10中，我们把B子树分成了以k3为根，B1和B2子树为左右子树的树，并且B1和B2中至少有一个的高度等于A子树的高度-1(我们做出这种推测的前提是B树和A树的高度相等)，左右双旋转后可以看到在B1和B2中至少有一个的高度等于A子树的高度-1，我们旋转后的树都是平衡的，所以双旋转也是可以恢复到平衡状态的，只是这样比单旋转要更多的操作，所以我们在左左不平衡情况下不平衡节点的左孩子的左子树和右子树等高的情况下，选择做单旋转。


图10:采用左右双旋转的方式恢复平衡(左孩子左右子树高度相同)
坚持原创技术分享，您的支持将鼓励我继续创作！