平衡二叉树(AVL树)详细解析-通俗易懂_二叉树 0 1 -1

平衡二叉树定义:二叉排序树的平衡因子绝对值小于等于1，即平衡因子为-1、0、1,那么是平衡二叉树（平衡因子：根结点的左子树深度减右子树深度的差）。
最小不平衡子树：子树的根结点距离插入结点距离最近，且平衡因子绝对值大于1的树为最小不平衡子树。
平衡二叉树：当插入结点后出现最小不平衡子树，那么就要对最小不平衡子树重新构造，通过顺时针（平衡因子皆为正）或逆时针（平衡因子皆为负）旋转最小不平衡子树的根结点使之成为平衡二叉树。注意：如果最小不平衡子树的根结点与页结点不是同号的，需要将其先转为同号再进行上述旋转(如何双旋转：如果最小不平衡树的根结点平衡因子为负数，说明其右子树深度高，为R，结点逆时针旋转;如果最小不平衡树的根结点右子树平衡因子为正数，说明其左子树深度高，为L，结点顺时针旋转；这样就形成了从上往下为RL，则先下子树L旋转，再上子树R旋转；反之为LR旋转）。

我们在处理平衡二叉树的时候回出现4中情况:

LL型单旋转，顺时针旋转（新增结点在最小不平衡子树根的左子树的左子树下，L表示左子树，数字2表示平衡因子）

    /**
	 * 执行LL顺时针旋转，最小不平衡子树才需要旋转，平衡的会过滤，对比图理解会比较容易
	 * @param tree 不一定是最小不平衡子树，看LR第二个图计算可知
	 * @return 返回根结点
	 */
	public TreeNode<T> executeLeftLeft(TreeNode<T> tree) {
		TreeNode<T> newRoot;
		newRoot = tree.leftSub;
		tree.leftSub = newRoot.rightSub;
		newRoot.rightSub = tree;
		tree.hight = Math.max(getHeight(tree.leftSub), getHeight(tree.rightSub)) + 1;
		newRoot.hight = Math.max(getHeight(newRoot.leftSub), getHeight(tree)) + 1;
		return newRoot;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

LR型双旋转，先下后上旋转，先R逆时针选择，后L顺时针旋转（新增结点在最小不平衡子树根的左子树的右子树下，L表示左子树，数字2表示平衡因子）

	/**
	 * 执行LR旋转，则先R逆时针旋转，最后变成LL,再顺时针旋转即可，对比图理解会比较容易
	 * @param tree 不一定是最小不平衡子树，看LR第二个图计算可知
	 * @return 返回根结点
	 */
	public TreeNode<T> executeLeftRight(TreeNode<T> tree) {
		tree.leftSub = executeRightRight(tree.leftSub);
		return executeLeftLeft(tree);
	}
1
2
3
4
5
6
7
8
9
10

RR型单旋转，逆时针旋转（新增结点在最小不平衡子树根的右子树的右子树下，R表示右子树，数字-2表示平衡因子）

    /**
	 *  执行RR逆时针旋转，最小不平衡子树才需要旋转，平衡的会过滤，对比图理解会比较容易
	 * @param tree 不一定是最小不平衡子树，看LR第二个图计算可知
	 * @return
	 */
	public TreeNode<T> executeRightRight(TreeNode<T> tree) {
		TreeNode<T> newRoot;
		newRoot = tree.rightSub;
		tree.rightSub = newRoot.leftSub;
		newRoot.leftSub = tree;
		tree.hight = Math.max(getHeight(tree.leftSub), getHeight(tree.rightSub)) + 1;
		newRoot.hight = Math.max(getHeight(tree), getHeight(newRoot.leftSub)) + 1;
		return newRoot;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

RL型双旋转，先下后上旋转，先R逆时针选择，后L顺时针旋转（新增结点在最小不平衡子树根的右子树的左子树下，R表示右子树，数字-2表示平衡因子）

	/**
	 *  执行RL旋转，则先执行L顺时针旋转，最后变成RR,再逆时针旋转即可，对比图理解会比较容易
	 * @param tree 不一定是最小不平衡子树，看LR第二个图计算可知
	 * @return
	 */
	public TreeNode<T> executeRightLeft(TreeNode<T> tree) {
		tree.rightSub = executeLeftLeft(tree.rightSub);
		return executeRightRight(tree);
	}
1
2
3
4
5
6
7
8
9

下面举个栗子具体操作：
依次添加5、4、3、6、10、8、9、14、13这些结点
（1）前面添加到3时才会不平衡，因此就从添加3开始了，加3后，LL,根顺时针单旋转

（2）加6后任然是平衡树

（3）加10后，RR,最小不平衡树根逆时针单旋转

（4）加8后RR,最小不平衡树根逆时针单旋转

（5）加9后LR，所以先R逆时针旋转后L顺时针旋转

（6）加14后仍然是二叉平衡树

（7）加13后RL,所以先L顺时针旋转后R逆时针旋转

package com.art.arithmetic.tree.avl;

public class TreeNode<T extends Comparable<T>> {
	
	T data;  //树结点值
	TreeNode<T> leftSub;  //树的左子树
	TreeNode<T> rightSub;  //树的右子树
	int hight;   //树的高度
	
	private TreeNode<T> root;
	
	public TreeNode<T> getTree() {
		return root;
	}
	
	public TreeNode() {};
	
	public TreeNode(T data, TreeNode<T> leftSub, TreeNode<T> rightSub) {
		this.data = data;
		this.leftSub = leftSub;
		this.rightSub = rightSub;
		this.hight = 1;  //新增结点树的高度是1
	}
	
	public static void main(String[] args) {
		TreeNode<Integer> treeNode = new TreeNode<Integer>();
		int tree[] = {5, 4, 3, 6, 10, 8, 9, 14, 13};
		for (int i = 0; i < tree.length; i++) {
			treeNode.insert(tree[i]);
		}
		TreeNode<Integer> newTree = treeNode.getTree();
		System.out.println("树高：" + newTree.hight);
		treeNode.removeAndBalance(newTree, 9);
		newTree = treeNode.getTree();
		System.out.println("树高：" + newTree.hight);
		
	}
	
	/**
	 * 获取树的高度
	 * @param tree 二叉树
	 * @return
	 */
	public int getHeight(TreeNode<T> tree) {
		if (tree != null) {
			return tree.hight;
		}
		//如果树为空，则返回0
		return 0;
	}
	
	//平衡因子为<=1无需处理
	/**
	 * 执行LL顺时针旋转，最小不平衡子树才需要旋转，平衡的会过滤，对比图理解会比较容易
	 * @param tree 不一定是最小不平衡子树，看LR第二个图计算可知
	 * @return 返回根结点
	 */
	public TreeNode<T> executeLeftLeft(TreeNode<T> tree) {
		TreeNode<T> newRoot;
		newRoot = tree.leftSub;
		tree.leftSub = newRoot.rightSub;
		newRoot.rightSub = tree;
		tree.hight = Math.max(getHeight(tree.leftSub), getHeight(tree.rightSub)) + 1;
		newRoot.hight = Math.max(getHeight(newRoot.leftSub), getHeight(tree)) + 1;
		return newRoot;
	}
	
	/**
	 *  执行RR逆时针旋转，最小不平衡子树才需要旋转，平衡的会过滤，对比图理解会比较容易
	 * @param tree 不一定是最小不平衡子树，看LR第二个图计算可知
	 * @return
	 */
	public TreeNode<T> executeRightRight(TreeNode<T> tree) {
		TreeNode<T> newRoot;
		newRoot = tree.rightSub;
		tree.rightSub = newRoot.leftSub;
		newRoot.leftSub = tree;
		tree.hight = Math.max(getHeight(tree.leftSub), getHeight(tree.rightSub)) + 1;
		newRoot.hight = Math.max(getHeight(tree), getHeight(newRoot.leftSub)) + 1;
		return newRoot;
	}
	
	/**
	 * 执行LR旋转，则先R逆时针旋转，最后变成LL,再顺时针旋转即可，对比图理解会比较容易
	 * @param tree 不一定是最小不平衡子树，看LR第二个图计算可知
	 * @return 返回根结点
	 */
	public TreeNode<T> executeLeftRight(TreeNode<T> tree) {
		tree.leftSub = executeRightRight(tree.leftSub);
		return executeLeftLeft(tree);
	}
	
	/**
	 *  执行RL旋转，则先执行L顺时针旋转，最后变成RR,再逆时针旋转即可，对比图理解会比较容易
	 * @param tree 不一定是最小不平衡子树，看LR第二个图计算可知
	 * @return
	 */
	public TreeNode<T> executeRightLeft(TreeNode<T> tree) {
		tree.rightSub = executeLeftLeft(tree.rightSub);
		return executeRightRight(tree);
	}
	
	public void insert(T data) {
		root = insert(root, data);
	}
	
	/**
	 * 新增结点
	 * @param tree 被添加结点树
	 * @param data 结点值
	 * @return
	 */
	public TreeNode<T> insert(TreeNode<T> tree, T data) {
		if (tree == null) {
			return new TreeNode<T>(data, null, null);
		}
		int cmp = data.compareTo(tree.data);
		if (cmp > 0) {
			tree.rightSub = insert(tree.rightSub, data);
		} else if (cmp < 0) {
			tree.leftSub = insert(tree.leftSub, data);
		}
		return balance(tree);
	}
	/**
	 * 新增结点
	 * @param tree 二叉树
	 * @return
	 */
	public TreeNode<T> balance(TreeNode<T> tree) {
		if (tree == null) {
			return null;
		}
		int balanceFactor = 1;
		if (getHeight(tree.leftSub) - getHeight(tree.rightSub) > balanceFactor) {
			if (getHeight(tree.leftSub.leftSub) > getHeight(tree.leftSub.rightSub)) {
				tree = executeLeftLeft(tree);
			} else {
				tree = executeLeftRight(tree);
			}
		} else if (getHeight(tree.rightSub) - getHeight(tree.leftSub) > balanceFactor) {
			if (getHeight(tree.rightSub.rightSub) > getHeight(tree.rightSub.leftSub)) {
				tree = executeRightRight(tree);
			} else {
				tree = executeRightLeft(tree);
			}
		}
		tree.hight = Math.max(getHeight(tree.leftSub), getHeight(tree.rightSub)) + 1;
		return tree;
	}
	
	/**
	 * 查找二叉树的结点
	 * @param tree 二叉树
	 * @param data 数据
	 * @return
	 */
	public TreeNode<T> findNode(TreeNode<T> tree, T data) {
		if (tree == null) {
			return null;
		}
		int cmp = data.compareTo(tree.data);
		if (cmp < 0) {
			return findNode(tree.leftSub, data);
		} else if (cmp > 0) {
			return findNode(tree.rightSub, data);
		} else {
			return tree;
		}
	}
	
	/**
	 * 更新结点值
	 * @param tree 二叉树
	 * @param data 旧值
	 * @param newData 更新值
	 * @return
	 */
	public TreeNode<T> modifyNode(TreeNode<T> tree, T data, T newData) {
		if (tree == null) {
			return null;
		}
		int cmp = data.compareTo(tree.data);
		if (cmp < 0) {
			return findNode(tree.leftSub, data);
		} else if (cmp > 0) {
			return findNode(tree.rightSub, data);
		} else {
			tree.data = newData;
			return tree;
		}
	}
	
	/**
	 * 找最小值结点
	 * @param tree
	 * @return
	 */
	public TreeNode<T> findMinData(TreeNode<T> tree) {
		if (tree == null) {
			return null;
		} else if (tree.leftSub == null) {
			return tree;
		}
		return findMinData(tree.leftSub);
	}
	
	/**
	 * 找最大值结点
	 * @param tree
	 * @return
	 */
	public TreeNode<T> findMaxData(TreeNode<T> tree) {
		if (tree == null) {
			return null;
		} else if (tree.rightSub == null) {
			return tree;
		}
		return findMaxData(tree.rightSub);
	}
	
	/**
	 * 删除二叉树及平衡二叉树
	 * @param tree
	 * @param data
	 * @return
	 */
	public TreeNode<T> removeAndBalance(TreeNode<T> tree, T data) {
		TreeNode<T> treeNew = remove(tree, data);
		return balance(treeNew);
	}
	
	/**
	 * 删除二叉树结点
	 * @param tree
	 * @param data
	 * @return
	 */
	public TreeNode<T> remove(TreeNode<T> tree, T data) {
		if (tree == null) {
			return null;
		}
//		int flag = 1;  //设置标识是在查找结点的左子树还是右子树
		int cmp = data.compareTo(tree.data);
		if (cmp > 0) {
			tree.rightSub = remove(tree.rightSub, data);
//			flag = 1;
		} else if (cmp < 0) {
			tree.leftSub = remove(tree.leftSub, data);
//			flag = -1;
		} else if (tree.leftSub != null &&  tree.rightSub != null) {
//			if (flag == -1) { //为左子树，找左子树中值最大的结点替换当前结点
//				tree.data = findMaxData(tree.leftSub).data;
//				tree.rightSub = remove(tree.leftSub, tree.data);
//			} else {//为左子树，找右边子树中值最小的结点替换当前结点
				tree.data = findMinData(tree.rightSub).data;
				tree.rightSub = remove(tree.rightSub, tree.data);
//			}
		} else {
			tree = (tree.leftSub != null) ? tree.leftSub : tree.rightSub;
		}
		return tree;
	}
	
}
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
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265