【Java数据结构】平衡二叉树_二叉平衡树的数据结构 java

二叉排序树的不足

关于之前就介绍过的二叉排序树，我们设下一下以下的情景：
如果有一组数字：｛1，2，3，4，5，6，7，8｝，我们用这组数字来构建一个二叉排序树，则会构建出下图所示的一棵树：

这颗树长得很别致，长得很像链表，可是它也的确是一颗二叉排序树，但是这么看来，它完全没有发挥出二叉排序树的优势，查找效率和单链表差不多。

为了保持二叉排序树的优势（高效查找），那么我们可以引出一个新的数据结构，平衡二叉树。

平衡二叉树

所谓平衡二叉树，实际上就是指**对任何一颗子树而言，左子树和右子树的高度差的绝对值不超过1，并且左子树和右子树也是平衡二叉树。**若将上图所示的二叉排序树转化成平衡二叉树，则如下图：

那么，是如何将一颗二叉排序树转化成平衡二叉树的呢？

构建二叉排序树

平衡因子

平衡因子实际上指的就是左子树和右子树的高度差的绝对值。只要这颗二叉树的每个子树的平衡因子小于等于1，那么这颗树便是二叉平衡树。由此可见，平衡因子是衡量是否是二叉平衡树的条件。

返回当前节点的高度

// 返回当前节点的高度
public int height(){
    if (left == null && right!=null)
        return Math.max(0, right.height()) + 1;
    if (right == null && left!= null)
        return Math.max(left.height(), 0) + 1;
    if (right != null && left != null)
    return Math.max(left.height(), right.height());
    else return 1;
}
1
2
3
4
5
6
7
8
9
10

上述代码判断的条件过多，实际上利用三目运算法只需下面一行代码即可。

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

判断左旋转还是右旋转

// 获取左子树的高度
public int leftHeight(){
    if (left == null)
        return 0;
    return left.height();
}
// 获取右子树的高度
public int rightHeight(){
    if (right == null)
        return 0;
    return right.height();
}
------------------------------------------------------------------------------------
// 查询是否平衡
// 左左，进行右旋转
if (leftHeight() - rightHeight() >= 2){
    rightRotate();
}
// 右右，进行左旋转
if (leftHeight() - rightHeight() <= -2){
    leftRotate();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

左左(右旋转)

右旋转图解

右旋转大致可以分成以下三种由简单到复杂的情况，实际上它们右旋转的步骤都是相同的。

以上是最简单的一种右旋转；

以上是稍微复杂的右旋转；

我们以最复杂的情况来举例描述旋转的步骤。

右旋转的步骤：

• 创建一个新的节点，值等于当前节点的值
• Node newRight = new Node(this.value);
  
• 把新节点的右子树设置为当前节点的右子树
• newRight.right = this.right;
  
• 把新节点的左子树设置为当前节点的左子树的右子树
• newRight .left = this.left.right;
  
• 把当前节点的值换为左子节点的值
• this.value = this.left.value;
  
• 把当前节点的左子树设置为左子树的左子树
• this.left = this.left.left;
  
• 把当前节点的右子树设置为新节点
• this.right = newRight;
  

右旋转代码实现

// 右旋转
public void rightRotate() {
    // 创建一个新的节点，值等于当前节点的值
    Node newRight = new Node(value);
    // 把新节点的右子树设置为当前节点的右子树
    newRight.right = right;
    // 把新节点的左子树设置为当前节点的左子树的右子树
    newRight.left = left.right;
    // 把当前节点的值换为左子节点的值
    value = left.value;
    // 把当前节点的左子树设置为左子树的左子树
    left = left.left;
    // 把当前节点的右子树设置为新节点
    right = newRight;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

左旋转示例完整代码

平衡二叉树类 BalancedBinaryTree

public class BalancedBinaryTree {
    Node root;
   // 向二叉排序树中添加节点
    public void add(Node node){
        if (root == null){ // 如果是一颗空树
            root = node; // 则添加结点为根结点
        }else{
            root.add(node);
        }
    }

}
1
2
3
4
5
6
7
8
9
10
11
12

平衡二叉树节点类 Node

package com.yusael.BalancedBinaryTree;

public class Node {
    int value;
    Node left;
    Node right;
    public Node(int value){
        this.value = 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();
    }
    // 向子树中添加节点
    public void add(Node node) {
        if (node == null){ // 传入空结点，什么也不做
            return;
        }
        // 判断传入的节点的值比当前子树的根结点的值大还是小
        if (node.value < this.value){ // 要添加的结点比当前节点的值更小，往左
            if (left == null){ // 如果左节点为空，则直接添加
                left = node;
            }else{ // 如果不为空，递归添加
                left.add(node);
            }
        }else{
            if (right == null) { // 如果右节点为空，则直接添加
                right = node;
            }else{ // 如果不为空，递归添加
                right.add(node);
            }
        }
        // 查询是否平衡
        // 进行右旋转
        if (leftHeight() - rightHeight() >= 2){
            rightRotate();
        }
        // 左旋转
        if (leftHeight() - rightHeight() <= -2){
            leftRotate();
        }
    }
    // 左旋转
    private void leftRotate() {
        // 创建一个新的节点，值等于当前节点的值
        Node newLeft = new Node(value);
        // 把新节点的左子树设置为当前节点的左子树
        newLeft.left = left;
        // 把新节点的右子树设置为当前节点的右子树的左子树
        newLeft.right = right.left;
        // 把当前节点的值换为右子节点的值
        value = right.value;
        // 把当前节点的右子树设置为右子树的右子树
        right = right.right;
        // 把当前节点的左子树设置为新节点
        left = newLeft;
    }
    // 右旋转
    public void rightRotate() {
        // 创建一个新的节点，值等于当前节点的值
        Node newRight = new Node(value);
        // 把新节点的右子树设置为当前节点的右子树
        newRight.right = right;
        // 把新节点的左子树设置为当前节点的左子树的右子树
        newRight.left = left.right;
        // 把当前节点的值换为左子节点的值
        value = left.value;
        // 把当前节点的左子树设置为左子树的左子树
        left = left.left;
        // 把当前节点的右子树设置为新节点
        right = newRight;
    }

}
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

测试案例

我们创建的二叉排序树如图所示：

    public static void main(String[] args) {
        int [] arr = new int[] {8, 9, 6, 7, 5, 4};
        BinarySortTree bst = new BinarySortTree(); // 创建一颗二叉排序树
        for (int i : arr){// 循环添加
            bst.add(new Node(i));
        }
        System.out.print("二叉树的高度：");
        System.out.println(bst.root.height());
        System.out.print("根结点的值：");
        System.out.println(bst.root.value);
    }
1
2
3
4
5
6
7
8
9
10
11

运行效果：

二叉树的高度：3
根结点的值：6
1
2

右右(左旋转)

右旋转和左旋转完全相反，只需要把所有的左右对调即可。

左旋转图解

由于左旋转与右旋转完全相反，上面看懂了这里必然也会了。

左旋转代码实现

// 左旋转
private void leftRotate() {
    // 创建一个新的节点，值等于当前节点的值
    Node newLeft = new Node(value);
    // 把新节点的左子树设置为当前节点的左子树
    newLeft.left = left;
    // 把新节点的右子树设置为当前节点的右子树的左子树
    newLeft.right = right.left;
    // 把当前节点的值换为右子节点的值
    value = right.value;
    // 把当前节点的右子树设置为右子树的右子树
    right = right.right;
    // 把当前节点的左子树设置为新节点
    left = newLeft;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

左右(双旋转)

双旋转图解

有时候会遇到单旋转无法解决的情况，这时候就需要双旋转，如下图

我们首先以5为当前节点进行左旋转，然后再以8位当前节点进行右旋转。

双旋转代码实现

双旋转是建立在单旋转的基础上，如果是左右的情况则进行双旋转。

if (leftHeight() - rightHeight() >= 2){
    if(left!= null && left.leftHeight() < left.rightHeight()){ // 左右，进行双旋转
        left.leftRotate(); // 先左旋转
        rightRotate(); // 再右旋转
    }else{ // 单旋转
        rightRotate();
    }
}
1
2
3
4
5
6
7
8

如果是右左的情况，与上面情况正好相反。

if (leftHeight() - rightHeight() <= -2){
    if (right != null && right.rightHeight() < right.leftHeight()){ // 右左，进行双旋转
        right.rightRotate(); // 先右旋转
        leftRotate(); // 再左旋转
    }else{ // 单旋转
        leftRotate();
    }
}
1
2
3
4
5
6
7
8

测试案例：通过｛8，9，5，4，6，7｝构造平衡二叉树，会产生双旋转的情况，最终构造的平衡二叉树高度为3，根节点为6。

public static void main(String[] args) {
    int [] arr = new int[] {8, 9, 5, 4, 6, 7};
    BalancedBinaryTree bst = new BalancedBinaryTree(); // 创建一颗二叉排序树
    for (int i : arr){// 循环添加
        bst.add(new Node(i));
    }
    System.out.print("二叉树的高度：");
    System.out.println(bst.root.height());
    System.out.print("根结点的值：");
    System.out.println(bst.root.value);
}
1
2
3
4
5
6
7
8
9
10
11

运行效果：

二叉树的高度：3
根结点的值：6
1
2