平衡二叉树(AVL树)介绍
案例分析
平衡二叉树可能存在的问题
给你一个数列{1,2,3,4,5,6}，要求创建一棵二叉排序树(BST)，并分析问题所在。
存在的问题：
- 左子树全部为空，从形式上看更像单链表。
- 插入速度没有影响，但是查询速度明显降低，而且每次查询还需要比较左子树，查询速度比单链表还慢。
- 解决方案：平衡二叉树(AVL)
基本介绍
-
平衡二叉树也叫平衡二叉搜索树(Self-balancing binary search tree)，又被称为AVL树，可以保证查询效率较高，平衡二叉树的前提是它必须是一棵二叉排序树。
-
具有以下特点：他是一棵空树或者它的左右两个子树高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树，平衡二叉树的常用实现方法有：红黑树，AVL，替罪羊树，Treap，伸展树等。
-
举例说明
AVL树左旋转思路图解
应用案例
单旋转(左旋转)
要求：给你一个数列{4,3,6,5,7,8}，创建处对应的平衡二叉树；
思路图解
对节点进行左旋转的步骤
-
创建一个新的节点newNode(以4这个值创建)，新节点的值等于当前根节点的值；
-
把新节点的左子树设置为当前节点的左子树；
newNode.left = left;
-
把新节点的右子树设置为当前节点的右子树的左子树；
newNode.right = right.left;
-
把当前节点的值替换为右子节点的值；
value = right.value;
-
把当前节点的右子树设置为右子树的右子树；
right = right.right;
-
把当前节点的左子树设置为新节点；
left = newLeft;
AVL树高度求解
代码
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
| package com.jokerdig.avl;
public class AVLTreeDemo {
public static void main(String[] args) {
int[] arr = {4,3,6,5,7,8};
AVLTree avl = new AVLTree();
for (int i = 0; i < arr.length; i++) {
avl.add(new Node(arr[i]));
}
System.out.println("中序遍历");
avl.infixOrder();
System.out.println("没有旋转之前,树的高度为：");
System.out.println(avl.getRoot().height());
System.out.println("左子树高度为：");
System.out.println(avl.getRoot().leftHeight());
System.out.println("右子树高度为：");
System.out.println(avl.getRoot().rightHeight());
}
}
class AVLTree{
private Node root;
public Node getRoot() {
return root;
}
public void add(Node node){
if(root==null){
root = node;
}else{
root.add(node);
}
}
public void infixOrder(){
if(root!=null){
root.infixOrder();
}else{
System.out.println("没有数据");
}
}
}
class Node{
int value;
Node left;
Node right;
public Node(int value) {
this.value = value;
}
@Override
public String toString() {
return "Node{" +
"value=" + value +
'}';
}
public int leftHeight(){
if(left==null){
return 0;
}else{
return left.height();
}
}
public int rightHeight(){
if(right==null){
return 0;
}else{
return right.height();
}
}
public int height(){
return Math.max(left==null? 0:left.height(), right==null?0:right.height())+1;
}
public void add(Node node){
if(node==null) {
return;
}
if(node.value<this.value){
if(this.left==null){
this.left = node;
}else{
this.left.add(node);
}
}else{
if(this.right==null){
this.right = node;
}else{
this.right.add(node);
}
}
}
public void infixOrder(){
if(this.left!=null){
this.left.infixOrder();
}
System.out.println(this);
if(this.right!=null){
this.right.infixOrder();
}
}
}
|
运行结果
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| 中序遍历
Node{value=3}
Node{value=4}
Node{value=5}
Node{value=6}
Node{value=7}
Node{value=8}
没有旋转之前,树的高度为：
4
左子树高度为：
1
右子树高度为：
3
Process finished with exit code 0
|
AVL树左旋转代码实现
代码
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
| package com.jokerdig.avl;
public class AVLTreeDemo {
public static void main(String[] args) {
int[] arr = {4,3,6,5,7,8};
AVLTree avl = new AVLTree();
for (int i = 0; i < arr.length; i++) {
avl.add(new Node(arr[i]));
}
System.out.println("中序遍历");
avl.infixOrder();
System.out.println("左旋转后,树的高度为：");
System.out.println(avl.getRoot().height());
System.out.println("左子树高度为：");
System.out.println(avl.getRoot().leftHeight());
System.out.println("右子树高度为：");
System.out.println(avl.getRoot().rightHeight());
}
}
class AVLTree{
private Node root;
public Node getRoot() {
return root;
}
public void add(Node node){
if(root==null){
root = node;
}else{
root.add(node);
}
}
public void infixOrder(){
if(root!=null){
root.infixOrder();
}else{
System.out.println("没有数据");
}
}
}
class Node{
int value;
Node left;
Node right;
public Node(int value) {
this.value = value;
}
@Override
public String toString() {
return "Node{" +
"value=" + value +
'}';
}
public int leftHeight(){
if(left==null){
return 0;
}else{
return left.height();
}
}
public int rightHeight(){
if(right==null){
return 0;
}else{
return right.height();
}
}
public int height(){
return Math.max(left==null? 0:left.height(), right==null?0:right.height())+1;
}
private void leftRotate(){
Node newNode = new Node(value);
newNode.left = left;
newNode.right = right.left;
value = right.value;
right = right.right;
left = newNode;
}
public void add(Node node){
if(node==null) {
return;
}
if(node.value<this.value){
if(this.left==null){
this.left = node;
}else{
this.left.add(node);
}
}else{
if(this.right==null){
this.right = node;
}else{
this.right.add(node);
}
}
if(rightHeight()-leftHeight()>1){
leftRotate();
}
}
public void infixOrder(){
if(this.left!=null){
this.left.infixOrder();
}
System.out.println(this);
if(this.right!=null){
this.right.infixOrder();
}
}
}
|
运行结果
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| 中序遍历
Node{value=3}
Node{value=4}
Node{value=5}
Node{value=6}
Node{value=7}
Node{value=8}
左旋转后,树的高度为：
3
左子树高度为：
2
右子树高度为：
2
Process finished with exit code 0
|
AVL树右旋转图解和实现
应用案例
单旋转(右旋转)
要求：给你一个数列{10,12,8,9,7,6}，创建处对应的平衡二叉树；
思路图解
对节点进行右旋转的步骤
-
创建一个新的节点newNode(以10这个节点创建)，值等于当前根节点；
-
把新节点的右子树设置为当前节点的右子树；
newNode.right = right;
-
把新节点的左子树设置为当前节点左子树的右子树；
newNode.left = left.right;
-
把当前节点的值换为左子节点的值；
value = left.value;
-
把当前节点的左子树设置为左子树的左子树；
left = left.left;
-
把当前节点的右子树设置为新节点；
right = newLeft;
代码实现
代码
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
| package com.jokerdig.avl;
public class AVLTreeDemo {
public static void main(String[] args) {
int[] arr = {10,12,8,9,7,6};
AVLTree avl = new AVLTree();
for (int i = 0; i < arr.length; i++) {
avl.add(new Node(arr[i]));
}
System.out.println("中序遍历");
avl.infixOrder();
System.out.println("右旋转后,树的高度为：");
System.out.println(avl.getRoot().height());
System.out.println("左子树高度为：");
System.out.println(avl.getRoot().leftHeight());
System.out.println("右子树高度为：");
System.out.println(avl.getRoot().rightHeight());
}
}
class AVLTree{
private Node root;
public Node getRoot() {
return root;
}
public void add(Node node){
if(root==null){
root = node;
}else{
root.add(node);
}
}
public void infixOrder(){
if(root!=null){
root.infixOrder();
}else{
System.out.println("没有数据");
}
}
}
class Node{
int value;
Node left;
Node right;
public Node(int value) {
this.value = value;
}
@Override
public String toString() {
return "Node{" +
"value=" + value +
'}';
}
public int leftHeight(){
if(left==null){
return 0;
}else{
return left.height();
}
}
public int rightHeight(){
if(right==null){
return 0;
}else{
return right.height();
}
}
public int height(){
return Math.max(left==null? 0:left.height(), right==null?0:right.height())+1;
}
private void leftRotate(){
Node newNode = new Node(value);
newNode.left = left;
newNode.right = right.left;
value = right.value;
right = right.right;
left = newNode;
}
private void rightRotate(){
Node newNode = new Node(value);
newNode.right = right;
newNode.left = left.right;
value = left.value;
left = left.left;
right = newNode;
}
public void add(Node node){
if(node==null) {
return;
}
if(node.value<this.value){
if(this.left==null){
this.left = node;
}else{
this.left.add(node);
}
}else{
if(this.right==null){
this.right = node;
}else{
this.right.add(node);
}
}
if(rightHeight()-leftHeight()>1){
leftRotate();
}else if(leftHeight()-rightHeight()>1){
rightRotate();
}
}
public void infixOrder(){
if(this.left!=null){
this.left.infixOrder();
}
System.out.println(this);
if(this.right!=null){
this.right.infixOrder();
}
}
}
|
运行结果
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| 中序遍历
Node{value=6}
Node{value=7}
Node{value=8}
Node{value=9}
Node{value=10}
Node{value=12}
右旋转后,树的高度为：
3
左子树高度为：
2
右子树高度为：
2
Process finished with exit code 0
|
AVL树双旋转图解和实现
应用案例
双旋转
之前分析的两个数列，进行单旋转就可以将非平衡二叉树转为平衡二叉树，但在某些情况下，单旋转不能完成平衡二叉树的转换。
例如：{10,11,7,6,8,9}; // 不能通过单旋转转换为AVL树。
问题分析
解决单个旋转存在的问题
- 当符合右旋转的条件时，如果当前节点的左子节点的右子树高度，大于当前节点的左子节点的左子树高度，先将当前节点的左子节点的树进行左旋转，然后在对当前节点进行右旋转。
- 当符合左旋转的条件时，如果当前节点的右子节点的左子树高度，大于当前节点的右子节点的右子树高度，先将当前节点的右子节点的树进行右旋转，然后在对当前节点进行左旋转。
代码实现
代码
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
| package com.jokerdig.avl;
public class AVLTreeDemo {
public static void main(String[] args) {
int[] arr = {10,11,7,6,8,9};
AVLTree avl = new AVLTree();
for (int i = 0; i < arr.length; i++) {
avl.add(new Node(arr[i]));
}
System.out.println("中序遍历");
avl.infixOrder();
System.out.println("双旋转后,树的高度为：");
System.out.println(avl.getRoot().height());
System.out.println("左子树高度为：");
System.out.println(avl.getRoot().leftHeight());
System.out.println("右子树高度为：");
System.out.println(avl.getRoot().rightHeight());
}
}
class AVLTree{
private Node root;
public Node getRoot() {
return root;
}
public void add(Node node){
if(root==null){
root = node;
}else{
root.add(node);
}
}
public void infixOrder(){
if(root!=null){
root.infixOrder();
}else{
System.out.println("没有数据");
}
}
}
class Node{
int value;
Node left;
Node right;
public Node(int value) {
this.value = value;
}
@Override
public String toString() {
return "Node{" +
"value=" + value +
'}';
}
public int leftHeight(){
if(left==null){
return 0;
}else{
return left.height();
}
}
public int rightHeight(){
if(right==null){
return 0;
}else{
return right.height();
}
}
public int height(){
return Math.max(left==null? 0:left.height(), right==null?0:right.height())+1;
}
private void leftRotate(){
Node newNode = new Node(value);
newNode.left = left;
newNode.right = right.left;
value = right.value;
right = right.right;
left = newNode;
}
private void rightRotate(){
Node newNode = new Node(value);
newNode.right = right;
newNode.left = left.right;
value = left.value;
left = left.left;
right = newNode;
}
public void add(Node node){
if(node==null) {
return;
}
if(node.value<this.value){
if(this.left==null){
this.left = node;
}else{
this.left.add(node);
}
}else{
if(this.right==null){
this.right = node;
}else{
this.right.add(node);
}
}
if(rightHeight()-leftHeight()>1){
if(right!=null && right.leftHeight()>right.rightHeight()){
right.rightRotate();
leftRotate();
}else{
leftRotate();
}
}else if(leftHeight()-rightHeight()>1){
if(left!=null && left.rightHeight()>left.leftHeight()){
left.leftRotate();
rightRotate();
}else{
rightRotate();
}
}
}
public void infixOrder(){
if(this.left!=null){
this.left.infixOrder();
}
System.out.println(this);
if(this.right!=null){
this.right.infixOrder();
}
}
}
|
运行结果
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| 中序遍历
Node{value=6}
Node{value=7}
Node{value=8}
Node{value=9}
Node{value=10}
Node{value=11}
双旋转后,树的高度为：
3
左子树高度为：
2
右子树高度为：
2
Process finished with exit code 0
|
