平衡二叉树(AVL树)介绍

案例分析

平衡二叉树可能存在的问题

给你一个数列{1,2,3,4,5,6},要求创建一棵二叉排序树(BST),并分析问题所在。

image-20221117102717941

存在的问题:

  1. 左子树全部为空,从形式上看更像单链表。
  2. 插入速度没有影响,但是查询速度明显降低,而且每次查询还需要比较左子树,查询速度比单链表还慢。
  3. 解决方案:平衡二叉树(AVL)

基本介绍

  1. 平衡二叉树也叫平衡二叉搜索树(Self-balancing binary search tree),又被称为AVL树,可以保证查询效率较高,平衡二叉树的前提是它必须是一棵二叉排序树。

  2. 具有以下特点:他是一棵空树或者它的左右两个子树高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树,平衡二叉树的常用实现方法有:红黑树,AVL,替罪羊树,Treap,伸展树等。

  3. 举例说明

    image-20221117104714357

AVL树左旋转思路图解

应用案例

单旋转(左旋转)

要求:给你一个数列{4,3,6,5,7,8},创建处对应的平衡二叉树;

思路图解

image-20221117111035723

对节点进行左旋转的步骤

  1. 创建一个新的节点newNode(以4这个值创建),新节点的值等于当前根节点的值;

  2. 把新节点的左子树设置为当前节点的左子树;

    newNode.left = left;

  3. 把新节点的右子树设置为当前节点的右子树的左子树;

    newNode.right = right.left;

  4. 把当前节点的值替换为右子节点的值;

    value = right.value;

  5. 把当前节点的右子树设置为右子树的右子树;

    right = right.right;

  6. 把当前节点的左子树设置为新节点;

    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;


/**
* @author Joker大雄
* @data 2022/11/18 - 9:26
**/
public class AVLTreeDemo {
public static void main(String[] args) {
int[] arr = {4,3,6,5,7,8};
// 创建一个AVLTree
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());
}
}
// 创建AVLTree
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(){
// 统计出来左子树和右子树的高度,在+1;(即加上本身这个节点)
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;


/**
* @author Joker大雄
* @data 2022/11/18 - 9:26
**/
public class AVLTreeDemo {
public static void main(String[] args) {
int[] arr = {4,3,6,5,7,8};
// 创建一个AVLTree
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());
}
}
// 创建AVLTree
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(){
// 统计出来左子树和右子树的高度,在+1;(即加上本身这个节点)
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);
}
}
// 当添加完一个节点后,如果(右子树高度-左子树高度)>1
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},创建处对应的平衡二叉树;

思路图解

image-20221118103234632

对节点进行右旋转的步骤

  1. 创建一个新的节点newNode(以10这个节点创建),值等于当前根节点;

  2. 把新节点的右子树设置为当前节点的右子树;

    newNode.right = right;

  3. 把新节点的左子树设置为当前节点左子树的右子树;

    newNode.left = left.right;

  4. 把当前节点的值换为左子节点的值;

    value = left.value;

  5. 把当前节点的左子树设置为左子树的左子树;

    left = left.left;

  6. 把当前节点的右子树设置为新节点;

    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;


/**
* @author Joker大雄
* @data 2022/11/18 - 9:26
**/
public class AVLTreeDemo {
public static void main(String[] args) {
// int[] arr = {4,3,6,5,7,8}; // 测试左旋转数组
int[] arr = {10,12,8,9,7,6}; // 测试右旋转数组
// 创建一个AVLTree
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());
}
}
// 创建AVLTree
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(){
// 统计出来左子树和右子树的高度,在+1;(即加上本身这个节点)
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);
}
}
// 当添加完一个节点后,如果(右子树高度-左子树高度)>1
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树。

image-20221119093019145

问题分析

解决单个旋转存在的问题

  1. 当符合右旋转的条件时,如果当前节点的左子节点的右子树高度,大于当前节点的左子节点的左子树高度,先将当前节点的左子节点的树进行左旋转,然后在对当前节点进行右旋转。
  2. 当符合左旋转的条件时,如果当前节点的右子节点的左子树高度,大于当前节点的右子节点的右子树高度,先将当前节点的右子节点的树进行右旋转,然后在对当前节点进行左旋转。

代码实现

代码

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;


/**
* @author Joker大雄
* @data 2022/11/18 - 9:26
**/
public class AVLTreeDemo {
public static void main(String[] args) {
// int[] arr = {4,3,6,5,7,8}; // 测试左旋转数组
// int[] arr = {10,12,8,9,7,6}; // 测试右旋转数组
int[] arr = {10,11,7,6,8,9}; // 测试双旋转数组
// 创建一个AVLTree
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());
}
}
// 创建AVLTree
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(){
// 统计出来左子树和右子树的高度,在+1;(即加上本身这个节点)
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);
}
}
// 当添加完一个节点后,如果(右子树高度-左子树高度)>1
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