主要完成了平衡二叉树插入的过程 LL,RR,LR,RL四种旋转方式
注意右旋是指结点左孩子向右旋转 左旋是结点的右孩子向左旋转

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
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
package 二叉树;

/**
 * @作者 Brown
 * @日期 2022/8/29 19:57
 */
public class AVLTree {
    public AVLNode root;

    public static class AVLNode {
        public int val;
        public int height = 1;
        public AVLNode left, right;

        public AVLNode(int val) {
            this.val = val;
        }

        public AVLNode(int val, AVLNode left, AVLNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
        //这里有一个show函数是为了更清晰的观察树的结构 但不是重点就放在最下面了
    }


    //得到当前结点的高度
    private static int getHeight(AVLNode avlNode) {
        if (avlNode == null) return 0;
        int l = (avlNode.left == null ? 0 : avlNode.left.height);
        int r = (avlNode.right == null ? 0 : avlNode.right.height);
        return 1 + Math.max(l, r);
    }

    // 辅助函数：获得节点的平衡因子
    private static int getBalanceFactor(AVLNode avlNode) {
        return (avlNode.left == null ? 0 : avlNode.left.height) - (avlNode.right == null ? 0 : avlNode.right.height);
    }

    // 右旋
    private AVLNode rightRotate(AVLNode y) {
       /* 树结构示意图：
                y                   x
               / \                 / \
              x   C      ->       A   y
             / \                     / \
            A   B                   B   C
       传入y 右旋左孩子x  更新深度且返回x
       旋转过程中B C的高度不变和原来一样 所以可以用B,C去更新y的高度
       A的高度也不变 y的已经更新完成所以可以根据 A y更新x的高度
     */
        AVLNode x = y.left;
        AVLNode xr = x.right;
        // 旋转
        x.right = y;
        y.left = xr;
        // 更新节点的高度
        y.height = getHeight(y);
        x.height = getHeight(x);
        return x;// 返回旋转后的根节点
    }

    // 左旋
    private AVLNode leftRotate(AVLNode y) {
        /* 树结构示意图：
                y                     x
               / \                   / \
              A   x        ->       y   C
                 / \               / \
                B   C             A   B
         传入y 左旋右孩子x  更新深度且返回x
         旋转过程中A B的高度不变和原来一样 所以可以用A,B去更新y的高度
         C的高度也不变 y的已经更新完成所以可以根据 y C更新x的高度
        */
        AVLNode x = y.right;
        AVLNode xl = x.left;
        // 旋转
        x.left = y;
        y.right = xl;
        // 更新节点的高度
        y.height = getHeight(y);
        x.height = getHeight(x);

        return x;    // 返回旋转后的根节点
    }


    public void insert(int data) {
        root = insert(root, data);
    }

    //添加结点
    private AVLNode insert(AVLNode root, int data) {
        //递归插入结点
        if (root == null) return new AVLNode(data);
        if (data < root.val) root.left = insert(root.left, data);
        else if (data > root.val) root.right = insert(root.right, data);
        else return root;

        //刷新高度
        root.height = getHeight(root);
        // 根据平衡因子判断需要旋转类型
        int bf = getBalanceFactor(root);

        //1. LL 型 右旋转
        if (bf == 2) {
            if (getBalanceFactor(root.left) == -1) {//2. LR 型 先左旋转
                root.left = leftRotate(root.left);
            }
            root = rightRotate(root);
        }
        //3. RR型 左旋转
        if (bf == -2) {
            if (getBalanceFactor(root.right) == 1) {//4. RL 型 先右旋转
                root.right = rightRotate(root.right);
            }
            root = leftRotate(root);
        }
        return root;
    }


    @Override
    public String toString() {
        return root.toString();
    }

    public static void main(String[] args) {
        AVLTree tree = new AVLTree();
        int[] nums = {15, 3, 7, 10, 9, 8, 16};

        for (int num : nums) {
            tree.insert(num);
        }
        System.out.println(tree);

    }
}

完整的AVLNode 为 多了一个show 函数可以更方便的打印树的结构 但是不要添加太多结点

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
public static class AVLNode {
    public int val;
    public int height = 1;
    public AVLNode left, right;

    public AVLNode(int val) {
        this.val = val;
    }

    public AVLNode(int val, AVLNode left, AVLNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }


    //方便观察 最好不要添加太多
    public static String show(AVLNode root) {
        return show(root, false);
    }

    public static String show(AVLNode root, boolean showDepth) {
        if (root == null) return "EMPTY!";
        // 得到树的深度
        int treeDepth = root.height;//在旋转过程中可能深度还没更新从而导致错误 所以最好递归去找一遍 而且不会影响中间过程
        // 最后一行的宽度为2的（n - 1）次方乘3，再加1
        // 作为整个二维数组的宽度
        int arrayHeight = treeDepth * 2 - 1;
        int arrayWidth = (2 << (treeDepth - 2)) * 3 + 1;
        // 用一个字符串数组来存储每个位置应显示的元素
        String[][] tree = new String[arrayHeight][arrayWidth];
        // 对数组进行初始化，默认为一个空格
        for (int i = 0; i < arrayHeight; i++) {
            for (int j = 0; j < arrayWidth; j++) {
                tree[i][j] = " ";
            }
        }
        // 从根节点开始，递归处理整个树
        writeArray(root, 0, arrayWidth / 2, tree, treeDepth, showDepth);

        // 此时，已经将所有需要显示的元素储存到了二维数组中，将其拼接并打印即可
        StringBuilder res = new StringBuilder();
        for (String[] line : tree) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < line.length; i++) {
                sb.append(line[i]);
                if (line[i].length() > 1 && i <= line.length - 1) {
                    i += line[i].length() > 4 ? 2 : line[i].length() - 1;
                }
            }
            res.append(sb).append("\n");
        }
        return res.delete(res.length() - 1, res.length()).toString();
    }

    private static void writeArray(AVLNode node, int rowIndex, int columnIndex, String[][] res, int treeDepth, boolean showDepth) {
        // 保证输入的树不为空
        if (node == null) return;
        // 先将当前节点保存到二维数组中

        if (showDepth) res[rowIndex][columnIndex] = node.val + "(" + node.height + ")"; //打印当前深度
        else res[rowIndex][columnIndex] = String.valueOf(node.val);

        // 计算当前位于树的第几层
        int currLevel = ((rowIndex + 1) / 2);
        // 若到了最后一层，则返回
        if (currLevel == treeDepth) return;
        // 计算当前行到下一行，每个元素之间的间隔（下一行的列索引与当前元素的列索引之间的间隔）
        int gap = treeDepth - currLevel - 1;

        // 对左儿子进行判断，若有左儿子，则记录相应的"/"与左儿子的值
        if (node.left != null) {
            res[rowIndex + 1][columnIndex - gap] = "/";
            writeArray(node.left, rowIndex + 2, columnIndex - gap * 2, res, treeDepth, showDepth);
        }

        // 对右儿子进行判断，若有右儿子，则记录相应的"\"与右儿子的值
        if (node.right != null) {
            res[rowIndex + 1][columnIndex + gap] = "\\";
            writeArray(node.right, rowIndex + 2, columnIndex + gap * 2, res, treeDepth, showDepth);
        }
    }

    @Override
    public String toString() {
        return show(this);
    }
}