HuKai's Blog
HuKai
2022-03-20
目录

平衡二叉树（AVL树）

# 平衡二叉树概述

# 1. 二叉排序树的弊端

前面学习了二叉排序树，它的插入删除的时间性能比较好。而对于二叉排序树的査找，走的就是从根结点到要査找的结点的路径，其比较次数等于给定值的结点在二叉排序树的层数。极端情况，最少为1次，即根结点就是要找的结点，最多也不会超过树的深度。也就是说，二叉排序树的査找性能取决于二叉排序树的形状。可问题就在于，二叉排序树的形状是不确定的。

例如{62,88,58,47,35,73,51,99,37,93}这样的数组，我们可以构建如下图左图的二叉排序树。但如果数组元素的次序是从小到大有序，如{35,37,47,51,58,62,73,88,93,99},则二叉排序树就成了极端的右斜树，虽然它依然是一棵二叉排序树，但同样是査找结点99，左图只需要两次比较，而右图就需要10次比较才可以得到结果，二者差异很大。

也就是说，我们希望二叉排序树是比较平衡的，即其深度与完全二叉树相同，均为log2n+1，那么查找的时间复杂也就为O(logn)，近似于折半査找。不平衡的最坏情况就是像右图的斜树，查找时间复杂度为O(n)，这等同于顺序査找，实际上比顺序查找还慢。

因此，如果我们希望对一个集合按二叉排序树査找，最好是把它构建成一棵平衡的二叉排序树。

# 2. 平衡二叉树简介

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

解决平衡二叉树的算法由2位科学家共同发明，用他们首字母命名又被称为AVL树。

下图左边二叉树的节点45的左孩子46比45大，不满足二叉搜索树的条件，因此它也不是一棵平衡二叉树，右边二叉树满足二叉搜索树的条件。

下图左边二叉树的节点45左子树高度2，右子树高度0，左右子树高度差为2-0=2，因此它也不是一棵平衡二叉树。右边二叉树的节点均满足左右子树高度差至多为1，同时它满足二叉搜索树的要求，因此它是一棵平衡二叉树

# 3. 平衡二叉树相关概念

  • 平衡因子：将二叉树上结点的左子树深度减去右子树的深度的值称为该结点平衡因子BF。对于平衡二叉树，所有结点的平衡因子只能是-1,0,1，如果发现某个节点的BF值不在此范围，则需要对树进行调整。
  • 最小不平衡子树：距离插入结点最近的，且平衡因子的绝对值大于1的结点为根的子树，我们称为最小不平衡子树。

注意：最小不平衡子树的根结点有可能为整棵树的根结点，也有可能不是。但其且平衡因子的绝对值一定大于1。

在图三中，左边二叉树的节点45的BF = 1，插入节点43后，节点45的BF = 2。节点45是距离插入点43最近的BF不在[-1,1]范围内的节点，因此以节点45为根的子树为最小不平衡子树。

# 平衡二叉树的实现详解

# 1. 结点类定义

平衡二叉树的首要条件是它必须是一颗二叉排序树，因此结点类结构和普通二叉排序树一样。

/**
 * 平衡二叉树结点类
 * @author hukai
 *
 * @param <E>
 */
public class AVLNode<E extends Comparable<E>> {
	
	// 数据元素
	private E element;
	
	// 双亲，左孩子，右孩子结点
	private AVLNode<E> parent, leftNode, rightNode;
	
	public AVLNode() {}

	public AVLNode(E element) {
		super();
		this.element = element;
	}
	
	// getter setter...
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

在另外一些AVL树实现的节点设计方案中，会把平衡因子BF或者是结点的高度作为结点的一个属性存储起来。我们这里是提供获取结点高度的方法，通过结点的高度我们也可以间接计算出结点的BF。

# 2. 结点的高度&平衡因子&失衡方向

一个节点的BF可由其左右子树的高度计算出来。我们在结点类里提供返回以该结点为根结点的树的高度的方法：

/**
 * 返回以该结点为根结点的树的高度
 * @return
 */
private int height() {
	return Math.max(this.leftNode == null ? 0 : this.leftNode.height(), this.rightNode == null ? 0 : this.rightNode.height()) + 1;
}
1
2
3
4
5
6
7

有了获取高度的方法，我们就可以获取结点的平衡因子了：

/**
 * 获取该结点的平衡因子
 * @return
 */
public int bf(){
	// 左子树的高度
	int leftHeight = this.leftNode == null ? 0 : this.leftNode.height();
	// 右子树的高度
	int rightHeight = this.rightNode == null ? 0 : this.rightNode.height();
	
	return leftHeight - rightHeight;
}
1
2
3
4
5
6
7
8
9
10
11
12

节点的插入或删除都有可能导致AVL树失衡，但我们需要知道具体是怎样的操作导致的失衡，以便有针对性的处理。我们不妨定义一个枚举分别标识导致失衡的几种情况，在这里我们我们暂且称呼它为失衡方向：

private enum Direction{
	/**
	 * 无失衡状况
	 */
	OK,
	/**
	 * 在右子树插入右孩子节点导致失衡
	 */
	RR,
	/**
	 * 在右子树插入左孩子节点导致失衡
	 */
	RL,
	/**
	 * 在左子树插入右孩子节点导致失衡
	 */
	LR,
	/**
	 * 在左子树插入左孩子节点导致失衡
	 */
	LL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

同时我们需要提供一个方法获取当前结点的失衡方向：

/**
 * 获取失衡方向
 * @return
 */
private Direction getImbalDirection(){
	// 获取该结点平衡因子
	int bf = this.bf();
	// 平衡因子小于-1说明往右子树插入了结点导致不平衡
	if (bf < -1) {
		// 右子树的平衡因子大于0说明往右子树的左子树插入了结点
		if (this.rightNode.bf() > 0) {
			return Direction.RL;
		}
		// 在右子树插入右孩子节点
		return Direction.RR;
	}
	// 平衡因子大于1说明往左子树插入了结点导致不平衡
	if (bf > 1) {
		// 左子树的平衡因子小于0说明往左子树的右子树插入了结点
		if (this.leftNode.bf() < 0) {
			return Direction.LR;
		}
		// 在左子树插入左孩子节点
		return Direction.LL;
	}
	return Direction.OK;
}
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

# 3. AVL树失衡调整-单左旋

假如我们要为数组{4，5，6，3，2，8，7，0，1}构建一颗AVL树，首先插入{4，5，6}，在插入元素6后出现不平衡的情况：

当我们在右子树插入右孩子导致AVL树失衡时，我们需要进行单左旋调整。失衡方向对应上面枚举中的RR。旋转围绕最小失衡子树的根节点进行，具体步骤为：

  • 创建一个新的节点newNode，值等于当前节点的值；
  • 把新节点的左子树设置为当前节点的左子树（newNode.left = this.left）；
  • 把新节点的右子树设置为当前节点的右子树的左子树 （newNode.right =this.right.left）；
  • 把当前节点的值换为其右子节点的值（this.value=this.right.value）；
  • 把当前节点的右子树设置成其右子树的右子树（this.right=this.right.right）
  • 把当前节点的左子树设置为新节点（this.left=new Node）

代码实现：

/**
 * 左旋
 */
private void leftRotate() {
	//创建新的结点，以当前根结点的值
	AVLNode<E> newNode = new AVLNode<E>(this.element);
	// 把新节点的左子树设置为当前节点的左子树（newNode.left = this.left）
	newNode.leftNode = this.leftNode;
	// 把新节点的右子树设置为当前节点的右子树的左子树（newNode.right =this.right.left）
	newNode.rightNode = this.rightNode.leftNode;
	// 把当前节点的值换为其右子节点的值（this.value=this.right.value）
	this.element = this.rightNode.element;
	// 把当前节点的右子树设置成其右子树的右子树（this.right=this.right.right）
	this.rightNode = this.rightNode.rightNode;
	// 把当前节点的左子树设置为新节点（this.left=new Node）
	this.leftNode = newNode;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

# 4. AVL树失衡调整-单右旋

继续插入元素{3，2}，此时二叉树为：

插入3、2后出现了不平衡的情况。此时的插入情况是在左子树上插入左孩子导致AVL树失衡，我们需要进行单右旋调整。失衡方向对应上面枚举中的LL。旋转围绕最小失衡子树的根节点进行，具体步骤为：

  • 创建一个新的节点 newNode，值等于当前节点的值；
  • 把新节点的右子树设置为当前节点的右子树（ newNode.right = this.right）；
  • 把新节点的左子树设置为当前节点的左子树的右子树（newNode.left = this.left.right）；
  • 把当前节点的值换为左子节点的值（this.value=this.left.value）；
  • 把当前节点的左子树设置成左子树的左子树（this.left=this.left.left）；
  • 把当前节点的右子树设置为新节点（this.right=newNode）；

代码实现：

private void rightRotate() {
	// 创建一个新的节点 newNode，值等于当前节点的值；
	AVLNode<E> newNode = new AVLNode<E>(this.element);
	// 把新节点的右子树设置为当前节点的右子树（ newNode.right = this.right）；
	newNode.rightNode = this.rightNode;
	// 把新节点的左子树设置为当前节点的左子树的右子树（newNode.left = this.left.right）；
	newNode.leftNode = this.leftNode.rightNode;
	// 把当前节点的值换为左子节点的值（this.value=this.left.value）；
	this.element = this.leftNode.element;
	// 把当前节点的左子树设置成左子树的左子树（this.left=this.left.left）；
	this.leftNode = this.leftNode.leftNode;
	// 把当前节点的右子树设置为新节点（this.right=newNode）；
	this.rightNode = newNode;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

# 5. AVL树失衡调整-双旋

我们继续插入元素{8，7}：

我们发现第一次旋转后AVL树仍旧处于不平衡的状态，第二次旋转再次进行调整。

这种情况，总结起来就是在右子树上插入左孩子导致AVL树失衡，此时我们需要先对右子结点进行右旋，然后在对当前结点进行左旋。失衡方向对应上面枚举中的RL。

根据对称性原理，我们可以推测出在左子树上插入右孩子导致AVL树失衡时，需要先对左子结点进行左旋，然后在对当前结点进行右旋。失衡方向对应上面枚举中的LR。如图，继续插入节点{0，1}：

分析完上述4中情况后，我们可以写出完整的失衡调整代码了：

/**
 * 失衡调整
 */
private void adjust(){
	switch (this.getImbalDirection()) {
	case RR:
		// 在右子树插入右孩子节点导致失衡 -> 单左旋
		this.leftRotate();
		break;
	case LL:
		// 在左子树插入左孩子节点导致失衡 -> 单右旋
		this.rightRotate();
		break;
	case RL:
		// 在右子树插入左孩子节点导致失衡 -> 先右孩子右旋，自己再左旋
		this.rightNode.rightRotate();
		this.leftRotate();
		break;
	case LR:
		// 在左子树插入右孩子节点导致失衡 -> 先左孩子左旋，自己再右旋
		this.leftNode.leftRotate();
		this.rightRotate();
		break;
	default:
		break;
	}
}
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

# 6. 完整实现

结点类：

import java.util.Optional;

import com.hukai.demo.tree.TreeNode;
/**
 * 二叉排序树节点类
 * @author hukai
 *
 * @param <E>
 */
public class AVLNode<E extends Comparable<E>> {
	
	// 数据元素
	private E element;
	
	// 双亲，左孩子，右孩子结点
	private AVLNode<E> parent, leftNode, rightNode;
	
	public AVLNode() {}

	public AVLNode(E element) {
		super();
		this.element = element;
	}

    // getter setter...
	
	/**
	 * 获取以该结点为根结点的树的高度
	 * @return
	 */
	public int height() {
		return Math.max(this.leftNode == null ? 0 : this.leftNode.height(), this.rightNode == null ? 0 : this.rightNode.height()) + 1;
	}
	
	/**
	 * 获取该结点的平衡因子
	 * @return
	 */
	public int bf(){
		// 左子树的高度
		int leftHeight = this.leftNode == null ? 0 : this.leftNode.height();
		// 右子树的高度
		int rightHeight = this.rightNode == null ? 0 : this.rightNode.height();
		
		return leftHeight - rightHeight;
	}
	
	/**
	 * 左旋
	 */
	private void leftRotate() {
		//创建新的结点，以当前根结点的值
		AVLNode<E> newNode = new AVLNode<E>(this.element);
		// 把新节点的左子树设置为当前节点的左子树（newNode.left = this.left）
		newNode.leftNode = this.leftNode;
		// 把新节点的右子树设置为当前节点的右子树的左子树（newNode.right =this.right.left）
		newNode.rightNode = this.rightNode.leftNode;
		// 把当前节点的值换为其右子节点的值（this.value=this.right.value）
		this.element = this.rightNode.element;
		// 把当前节点的右子树设置成其右子树的右子树（this.right=this.right.right）
		this.rightNode = this.rightNode.rightNode;
		// 把当前节点的左子树设置为新节点（this.left=new Node）
		this.leftNode = newNode;
	}
	
	private void rightRotate() {
		// 创建一个新的节点 newNode，值等于当前节点的值；
		AVLNode<E> newNode = new AVLNode<E>(this.element);
		// 把新节点的右子树设置为当前节点的右子树（ newNode.right = this.right）；
		newNode.rightNode = this.rightNode;
		// 把新节点的左子树设置为当前节点的左子树的右子树（newNode.left = this.left.right）；
		newNode.leftNode = this.leftNode.rightNode;
		// 把当前节点的值换为左子节点的值（this.value=this.left.value）；
		this.element = this.leftNode.element;
		// 把当前节点的左子树设置成左子树的左子树（this.left=this.left.left）；
		this.leftNode = this.leftNode.leftNode;
		// 把当前节点的右子树设置为新节点（this.right=newNode）；
		this.rightNode = newNode;
	}
	
	/**
	 * 查找节点
	 * @param element
	 * @return
	 */
	public AVLNode<E> search(E element){
		
		int cmp = element.compareTo(this.getElement());
		
		if (cmp < 0) {
			// 如果查找的值小于当前结点，向左子树递归查找
			return Optional.ofNullable(this.getLeftNode()).map(n -> n.search(element)).orElse(null);
		}else if (cmp > 0) {
			//如果查找的值大于于当前结点，向右子树递归查找
			return Optional.ofNullable(this.getRightNode()).map(n -> n.search(element)).orElse(null);
		}else{
			// 等于当前节点，说明已经找到，直接返回
			return this;
		}
	}
	
	/**
	 * 查找当前结点下最小结点
	 * @return
	 */
	public AVLNode<E> searchMinNode(){
		AVLNode<E> minNode = this;
		while (minNode.getLeftNode() != null) {
			minNode = minNode.getLeftNode();
		}
		return minNode;
	}
	
	/**
	 * 添加结点
	 * @param node
	 */
	public void add(AVLNode<E> node){
		if (node == null) return;
		
		int cmp = node.getElement().compareTo(this.getElement());
		//判断传入的结点的值，和当前子树的根结点的值关系
		if (cmp < 0) {
			//如果当前结点左子结点为null
			if (this.getLeftNode() == null) {
				node.setParent(this);
				this.setLeftNode(node);
			}else{
				//递归的向左子树添加
				this.getLeftNode().add(node);
			}
		}else{
			//添加的结点的值大于当前结点的值
			if (this.getRightNode() == null) {
				node.setParent(this);
				this.setRightNode(node);
			}else{
				//递归的向右子树添加
				this.getRightNode().add(node);
			}
		}
		//当添加完一个结点后 调整失衡
		adjust();
	}
	
	/**
	 * 失衡调整
	 */
	private void adjust(){
		switch (this.getImbalDirection()) {
		case RR:
			// 在右子树插入右孩子节点导致失衡 -> 单左旋
			this.leftRotate();
			break;
		case LL:
			// 在左子树插入左孩子节点导致失衡 -> 单右旋
			this.rightRotate();
			break;
		case RL:
			// 在右子树插入左孩子节点导致失衡 -> 先右孩子右旋，自己再左旋
			this.rightNode.rightRotate();
			this.leftRotate();
			break;
		case LR:
			// 在左子树插入右孩子节点导致失衡 -> 先左孩子左旋，自己再右旋
			this.leftNode.leftRotate();
			this.rightRotate();
			break;
		default:
			break;
		}
	}
	
	/**
	 * 获取失衡方向
	 * @return
	 */
	private Direction getImbalDirection(){
		// 获取该结点平衡因子
		int bf = this.bf();
		// 平衡因子小于-1说明往右子树插入了结点导致不平衡
		if (bf < -1) {
			// 右子树的平衡因子大于0说明往右子树的左子树插入了结点
			if (this.rightNode.bf() > 0) {
				return Direction.RL;
			}
			// 在右子树插入右孩子节点
			return Direction.RR;
		}
		// 平衡因子大于1说明往左子树插入了结点导致不平衡
		if (bf > 1) {
			// 左子树的平衡因子小于0说明往左子树的右子树插入了结点
			if (this.leftNode.bf() < 0) {
				return Direction.LR;
			}
			// 在左子树插入坐孩子节点
			return Direction.LL;
		}
		return Direction.OK;
	}
	
	private enum Direction{
		/**
		 * 无失衡状况
		 */
		OK,
		/**
		 * 在右子树插入右孩子节点导致失衡
		 */
		RR,
		/**
		 * 在右子树插入左孩子节点导致失衡
		 */
		RL,
		/**
		 * 在左子树插入右孩子节点导致失衡
		 */
		LR,
		/**
		 * 在左子树插入左孩子节点导致失衡
		 */
		LL;
	}
	
}
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225

二叉树的实现类和普通二叉排序树相同，在此不做详述。

编辑 (opens new window)
#数据结构
上次更新: 2022/03/20, 16:39:15
二叉排序树
多路查找树

← 多路查找树→

最近更新
01
MyBatisPlus
03-20
02
MyBatis源码剖析-延迟加载
03-20
03
MyBatis源码剖析-二级缓存
03-20
更多文章>
Theme by Vdoing | Copyright © 2021-2022 HuKai | 赣ICP备17016768号