记录生活中的点点滴滴

0%

平衡二叉树

发表于 Valine：

平衡二叉搜索树（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();
    }
}