[toc]
AVL平衡二叉树
给你一个数列{1,2,3,4,5,6}，要求创建一颗二叉排序树(BST), 问题所在：
- 左子树全部为空，从形式上看，更像一个单链表.
- 插入速度没有影响
- 查询速度明显降低(因为需要依次比较), 不能发挥 BST的优势，因为每次还需要比较左子树，其查询速度比单链表还慢
解决方案–平衡二叉树(AVL)
1. 基本介绍
平衡二叉树也叫平衡 二叉搜索树（**Self-balancing binary search tree**）又被称为 AVL 树， 可以保证查询效率较高。
具有以下特点：
- 它是一 棵空树或 它的左右两个子树的高度差的绝对值不超过 1，并且 左右两个子树都是一棵平衡二叉树。平衡二叉树的常用实现方法有红黑树、AVL、替罪羊树、**
Treap、伸展树**等。
- 举例说明, 看看下面哪些 AVL 树, 为什么?
2. 准备过程
平衡二叉树，与二叉排序树基本思想是相同的，不同的是通过二叉树的左旋和右旋使二叉树根节点左右子树尽量保持一致的一个二叉树。
创建**Node类和AVLTree**类
- **
public int height();**以该节点为根节点的树的高度
- **
public int leftHeight();**返回左子树的高度
public int rightHeight(); 返回右子树的高度
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
|
class AVLTree{
}
class Node{
int value;
Node left;
Node right;
public Node(int value) {
this.value = value;
}
@Override
public String toString() {
return "Node [value=" + value + "]";
}
public void add(Node node) {
}
public void infixOrder() {
}
public Node search(int value) {
}
public Node searchParent(int value) {
}
public int height() {
return Math.max(left == null ?0:left.height(),right == null?0:right.height())+1;
}
public int leftHeight() {
if(left == null) {
return 0;
}
return left.height();
}
public int rightHeight() {
if(right == null) {
return 0;
}
return right.height();
}
}
|
3. 单旋转(左旋转)
给你一个数列，创建出对应的平衡二叉树.数列 {4,3,6,5,7,8}
代码实现
在Node类中添加该方法，同时在add()方法中通过**rightHeight() - leftHeight() > 1**,进行左旋转调用。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
public void leftRotate() {
Node newNode = new Node(this.value);
newNode.left = this.left;
newNode.right = this.right.left;
this.value = this.right.value;
this.right = this.right.right;
this.left = newNode;
}
|
4. 单旋转(右旋转)
给你一个数列，创建出对应的平衡二叉树.数列 {10,12, 8, 9, 7, 6}
代码实现
在Node类中添加该方法，同时在add()方法中通过**leftHeight() - rightHeight() > 1**,进行右旋转调用。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
public void rightRotate() {
Node newNode = new Node(this.value);
newNode.right = this.right;
newNode.left = this.left.right;
this.value = this.left.value;
this.left = this.left.left;
this.right = newNode;
}
|
5. 双旋转
- 前面的两个数列，进行单旋转(即一次旋转)就可以将非平衡二叉树转成平衡二叉树,但是在某些情况下，单旋转
不能完成平衡二叉树的转换。
- 比如数列
- int[] arr = { 10, 11, 7, 6, 8, 9 }; 运行原来的代码可以看到，并没有转成 AVL 树.
- int[] arr = {2,1,6,5,7,3}; 运行原来的代码可以看到，并没有转成 AVL 树
解决方案
- 当符号右旋转的条件时
- 如果它的左子树的右子树高度大于它的左子树的高度
- 先对当前这个结点的左节点进行左旋转
- 在对当前结点进行右旋转的操作即可
- 在Node类add()中修改成一下代码就OK，就是最后两个if判断。
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
|
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(this.rightHeight() - this.leftHeight() > 1) {
if(this.right != null && this.right.leftHeight() > this.right.rightHeight()) {
this.right.rightRotate();
leftRotate();
}else {
leftRotate();
}
}
if(this.leftHeight() - rightHeight() >1) {
if(this.left != null && this.left.leftHeight() < this.left.rightHeight()) {
this.left.leftRotate();
rightRotate();
}else {
rightRotate();
}
}
}
|
☆
