记录生活中的点点滴滴

0%

平衡二叉树

平衡二叉搜索树(Self-balancing binary search tree)又被称为AVL树(有别于AVL算法),且具有以下性质:它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。

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

把它构造完成之后,左子树全部为空,从形式上看,更像一个单链表,查询速度明显降低。

解决方案:平衡二叉树(AVL)

我们的AVL相关代码可以直接从二叉排序树那边复制过来(下面我再列出来),下面我主要写插入的问题,因为平衡二叉树插入有时候可能需要旋转才能使其满足条件。

我们先写一个Node节点类:

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
class Node{
int data;
Node left;
Node right;
public Node(int data){
this.data = data;
}

@Override
public String toString() {
return "Node{" +
"data=" + data +
'}';
}
//添加方法
public void add(Node node){
if(node==null)
return;
if(node.data < this.data){//向左添加
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);
}
}
}
}

它有对应的添加方法,接下来是AVL树 AVLTree 类:

1
2
3
4
5
6
7
8
9
10
11
class AVLTree{
//根节点
Node root;
//添加节点的方法
public void add(Node node){
if(root==null)
root = node;
else
root.add(node);
}
}

树的高度

其实我们判断是否需要旋转的依据就是左子树和右子树的高度,我们要在Node类中完成三个方法,分别返回这棵树的高度、它的左子树的高度、它的右子树的高度。

先写以它自己为根节点的树的高度,其实很简单,就是递归调用下去:

1
2
3
4
//返回树的高度,以当前节点为根节点
public int height(){
return Math.max(this.left==null ? 0 : this.left.height(),this.right==null ? 0 : this.right.height())+1;
}

有了这个方法,那么要想返回其左子树和右子树的高度就很简单了,如下:

1
2
3
4
5
6
7
8
//返回左子树的高度
public int leftHeight(){
return this.left==null ? 0 : this.left.height();
}
//返回右子树的高度
public int rightHeight(){
return this.right==null ? 0 : this.right.height();
}

左旋转

这种情况就需要左旋转,步骤如下:

  1. 以当前节点的值创建新节点

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

  3. 新节点右子树为当前右子树的左子树

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

  5. 当前节点右子树为右子树的右子树

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

具体代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//左旋转方法
public void leftRotate(){
//以当前节点的值创建新节点
Node newNode = new Node(data);
//新节点左子树设置为当前左子树
newNode.left = left;
//新节点右子树为当前右子树的左子树
newNode.right = right.left;
//当前节点值替换为右子节点的值
data = right.data;
//当前节点右子树为右子树的右子树
right = right.right;
//当前节点的左子树设置为新节点
left = newNode;
}

右旋转

代码如下:

1
2
3
4
5
6
7
8
9
//右旋转
public void rightRotate(){
Node newNode = new Node(data);
newNode.right = right;
newNode.left = left.right;
data = left.data;
left = left.left;
right = newNode;
}

左右双旋转

一些时候进行进行单旋转(即一次旋转)就可以将非平衡二叉树转成平衡二叉树,但是在某些情况下,单旋转不能完成平衡二叉树的转换,如下图所示,需要进行两次旋转:

这样两种情况:

  1. 如果左子树的右子树的高度大于左子树的左子树的高度
  2. 如果右子树的左子树的高度大于右子树的右子树的高度

这种情况下,我们要进行两次旋转。

添加节点的方法

虽然旋转的方法不是很难写,但是我们怎样才能构造这样的平衡二叉树呢?

我们的节点是一个一个添加的,我们肯定得防微杜渐,从刚开始不满足就开始旋转,否则等全部建立起来了,可能左右子树高度都相差10000了,还调整个毛。所以我们可以修改我们Node节点的add添加方法,在后面判断是否需要旋转,如果高度相差大于1就对其旋转,这样就可以了,add方法代码如下:

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
//添加方法
public void add(Node node){
if(node==null)
return;
if(node.data < this.data){//向左添加
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);
}
}
//递归看高度旋转使其满足AVL树条件
if(leftHeight()-rightHeight()>1){
//如果左子树的右子树的高度大于左子树的左子树的高度
if(left!=null && left.rightHeight()>left.leftHeight()){
//先对当前结点的左结点(左子树)->左旋转
left.leftRotate();
}
//再进行右旋转
rightRotate();
return;
}
if(rightHeight()-leftHeight()>1){
if(right!=null && right.leftHeight()>right.rightHeight()){
right.rightRotate();
}
leftRotate();
}
}