什么是平衡二叉树？
平衡二叉树 ：（Balanced Binary Tree）又被称为AVL树（有别于AVL算法），且具有以下性质：
它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。这个方案很好的解决了二叉查找树退化成链表的问题，把插入，查找，删除的时间复杂度最好情况和最坏情况都维持在O(logN)。但是频繁旋转会使插入和删除牺牲掉O(logN)左右的时间，不过相对二叉查找树来说，时间上稳定了很多。
在讲解平衡二叉树之前我们先了解以下树的高度以及层的概念
（图片引用于网络）
查询树的高度
思路：
通过递归实现查询当前节点的左右子树的最大高度，然后再 + 1（加上节点本身），此时就是树的最大高度
1
2
3
4
|
public int height(){
return Math.max(left == null ? 0:left.height(),right == null ? 0:right.height()) + 1;
}
|
查询左右子树的高度
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
public int leftHeight(){
if(left == null){
return 0;
}
return left.height();
}
public int rightHeight(){
if(right == null){
return 0;
}
return right.height();
}
|
平衡二叉树实现
左旋转
节点的左子树的高度即h(左) 和 右子树即h(右)的差值大于1 。
具体来说就是 h(右) - h(左) > 1
当满足这个情况时我们就需要进行左旋转
思路
- new 一个新的节点newNode ，value 为当前节点的value
- 设置newNode的left节点 为当前节点的left
- 设置newNode 的right节点 为当前节点的right的left节点
- 将当前节点的value设置为 当前节点的right的value
- 把当前节点的right 设置为 当前节点的right 的right
- 把当前节点的left设置为 newNode
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
public void leftRotate(){
Node newNode = new Node(this.val);
newNode.left = this.left;
newNode.right = this.right.left;
this.val = this.right.val;
this.left = newNode;
this.right = this.right.right;
}
|
右旋转
当前节点的左子树的高度，即h(左) 和 右子树即h(右)的差值大于1 。
具体来说就是 h(左) - h(右) > 1
当满足这个情况时我们就需要进行右旋转
思路
- new 一个新的节点newNode ，value 为当前节点的value
- 设置newNode的right节点 为当前节点的right
- 设置newNode 的left节点 为当前节点的left的right节点
- 将当前节点的value设置为 当前节点的left的value
- 把当前节点的left设置为 当前节点的left 的left
- 把当前节点的right设置为 newNode
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| public void rightRotate(){
Node newNode = new Node(this.val);
newNode.right = this.right;
newNode.left = this.left.right;
this.val = this.left.val;
this.left = this.left.left;
this.right = newNode;
}
|
双旋转
双旋转出现的原因
以数组【10，11，7，6，8，9】为例
如下图可以看到，以节点8为根节点的right树高度 - left树的高度 > 1
这样如果我们还是按照之前的做法势必无法得到平衡二叉树。所以我们就需要先将以节点8 为根节点的二叉树进行左旋转使它成为平衡二叉树之后，再对整棵树进行右旋转， 这样我们才能使整棵树都是平衡二叉树
(图片引用于csdn博主菜鸟要翱翔)
解决思路
如果当前树需要进行左旋转（即(rightHeight() - leftHeight() > 1)）
那么就需要判断右节点的rightHeight 是否 < rightHeight
如果满足， 那么就先将以right节点为根节点的树进行右旋转 ，然后再将整个树进行左旋转
同理
当前树需要进行右旋转（即(leftHeight() - rightHeight() > 1)）
那么就需要判断左节点的rightHeight 是否 > leftHeight
如果满足， 那么就先将以left节点为根节点的树进行左旋转 ，然后再将整个树进行右旋转
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| if (rightHeight() - leftHeight() > 1){
if (right != null && right.rightHeight() < right.leftHeight()){
right.rightRotate();
leftRotate();
}else {
leftRotate();
}
}
else if (leftHeight() - rightHeight() > 1){
if (left != null && left.leftHeight() < left.rightHeight()){
left.leftRotate();
rightRotate();
}else {
rightRotate();
}
}
}
|
代码实现
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
| public class Node {
public int val;
public Node right;
public Node left;
public void leftRotate(){
Node newNode = new Node(this.val);
newNode.left = this.left;
newNode.right = this.right.left;
this.val = this.right.val;
this.left = newNode;
this.right = this.right.right;
}
public void rightRotate(){
Node newNode = new Node(this.val);
newNode.right = this.right;
newNode.left = this.left.right;
this.val = this.left.val;
this.left = this.left.left;
this.right = newNode;
}
public void add(Node node){
if(node == null){
return;
}
if(node.val < this.val){
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.rightHeight() < right.leftHeight()){
right.rightRotate();
leftRotate();
}else {
leftRotate();
}
}
else if (leftHeight() - rightHeight() > 1){
if (left != null && left.leftHeight() < left.rightHeight()){
left.leftRotate();
rightRotate();
}else {
rightRotate();
}
}
}
public int leftHeight(){
if(left == null){
return 0;
}
return left.height();
}
public int rightHeight(){
if(right == null){
return 0;
}
return right.height();
}
public int height(){
return Math.max(left == null ? 0:left.height(),right == null ? 0:right.height()) + 1;
}
public void infix(){
if(this.left != null){
this.left.infix();
}
System.out.println(this);
if (this.right != null){
this.right.infix();
}
}
public Node(int val) {
this.val = val;
}
@Override
public String toString() {
return "Node[" +
"val=" + val +
']';
}
}
|
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
| public class AVLTree {
public Node root;
public static void main(String[] args) {
int[] arr = {10,11,7,6,8,9,12,33,14,1,22,0,3,33,23,44,55,54,34};
AVLTree avl = new AVLTree();
for (int i=0;i<arr.length;i++){
avl.add(new Node(arr[i]));
}
avl.root.infix();
System.out.println("树的高度 :" + avl.root.height());
System.out.println("树的左子树高度 :" + avl.root.leftHeight());
System.out.println("树的右子树高度 :" + avl.root.rightHeight());
}
public void add(Node node){
if (root == null){
root = node;
}else{
root.add(node);
}
}
}
|
运行结果
Node[val=0]
Node[val=1]
Node[val=3]
Node[val=6]
Node[val=7]
Node[val=8]
Node[val=9]
Node[val=10]
Node[val=11]
Node[val=12]
Node[val=14]
Node[val=22]
Node[val=23]
Node[val=33]
Node[val=33]
Node[val=34]
Node[val=44]
Node[val=54]
Node[val=55]
树的高度 :5
树的左子树高度 :3
树的右子树高度 :4
进程已结束,退出代码0
