树 - 平衡二叉树 AVL

2023-10-18 10 Algorithm 数据结构 0 评论阅读时长: 26(分)

平衡二叉树（Balance Binary Tree）具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

平衡二叉树的常用实现方法有：红黑树、AVL、替罪羊树、Treap、伸展树等。最小二叉平衡树的节点公式：F(n) = F(n-1)+F(n-2)+1，1是根节点，F(n-1)是左子树节点数量，F(n-2)是右子树的节点数量

1.什么是AVL树

AVL树是高度平衡的二叉树，特点是：AVL树中任何节点的两个子树的高度最大差别为1。

上面两张图片：左边的是AVL树，它的任何节点的两个子树的高度差别都<=1；而右边的不是AVL树，因为7的两个子树的高度相差2

动画效果参考 AVL Tree

2. AVL 树的实现

2.1 节点

节点定义

定义： AVL Tree是AVL树的对应的类，而AVLTreeNode是AVL树节点，它是AVLTree的内部类，AVLTree包含了AVL树的根节点，基本操作页定义在AVL树中

AVLTreeNode包括的捷哥组成对象：

key: 关键字，用来AVL树的节点进行排序的
left: 左子树
right: 右子树
height: 高度

/**
 * @author xiaoyuge
 */
public class AVLTree<T extends Comparable<T>> {

    private AVLTreeNode<T> mRoot; //根节点

    class AVLTreeNode<T extends Comparable<T>> {
        T key; //关键字
        int height; //高度
        AVLTreeNode<T> left; //左子树
        AVLTreeNode<T> right; //右子树

        public AVLTreeNode(T key, AVLTreeNode<T> left, AVLTreeNode<T> right) {
            this.key = key;
            this.height = 0;
            this.left = left;
            this.right = right;
        }
    }

    public AVLTreeNode<T> getmRoot() {
        return mRoot;
    }

    public void setmRoot(AVLTreeNode<T> mRoot) {
        this.mRoot = mRoot;
    }
}

树的高度

树的高度为最大层次，即空的二叉树的高度为0，非空树的高度等于它的最大层次（根节点为1，根的子节点为2，依次类推）

/**
 * 获取树的高度
 */
private int height(AVLTreeNode<T> tree){
    if (tree != null){
        return tree.height;
    }
    return 0;
}
public int height(){
    return height(mRoot);
}

比较大小

/**
 * 比较大小
 */
private int max(int a, int b) {
    return a > b ? a : b;
}

2.2 旋转

如果在AVL树中进行插入或删除节点后，可能导致AVL树失去平衡，这种失去平衡可以概括为4种姿态： LL(左左)、LR(左右)、RR(右右)、RL(右左)

上面的4棵树中都是”失去平衡的AVL树”，从左到右分别是：LL、LR、RL、RR。除了上面的情况之外，还有其他失去平衡的AVL树，如下图：

总的来说：AVL树失去平衡是的情况一定是LL、LR、RL、RR中的一种，它们的定义为：

LL: 插入或删除一个节点后，根节点的左子树的左子树还有非空子节点，导致根的左子树的高度比根的右子树的高度大2，导致AVL树失去了平衡。

上面LL的情况，由于根节点8的左子树4的左子树2还有非空子节点，根节点8的右子树12没有子节点，导致根节点8的左子树4高度比根节点右子树12 高2
LR: 插入或删除一个节点后，根节点的左子树的右子树还有非空节点，导致根的左子树高度比根的右子树高度大2，导致AVL树失去平衡

上面LR的情况，由于根节点8的左子树4的右子树6还有非空节点，而根节点8的右子树12没哟子节点，导致根节点8的左子树4高度比根节8点右子树12 高2
RL: 插入或删除一个节点后，根节点的右子树的左子树还有非空节点，导致根的右子树高度比根的左子树高度大2，导致AVL树失去平衡

上面RL的情况，由于根节点8的右子树12的左子树10还有非空节点，而根节点8的左子树4没哟子节点，导致根节点8右子树12的高度比根节点8左子树4 高2

RR: 插入或删除一个节点后，根节点的右子树的右子树还有非空节点，导致根的右子树高度比根的左子树高度大2，导致AVL树失去平衡

上面RR的情况，由于根节点8的右子树12的右子树14还有非空节点，而根节点8的左子树4没哟子节点，导致根节点8右子树12的高度比根节点8左子树4 高2

LL 旋转

LL失去平衡的情况，可以通过依次旋转让AVL树恢复平衡。如下图

从上可以发现，旋转之后的树又变成了AVL树，而且该旋转只需要一次即可。对于LL旋转，可以理解为：LL旋转是围绕失去平衡的AVL根节点进行的，也就是k2，由于是LL的情况，就是用手抓着左子树k1使劲摇，将k1变成根节点， k2变成k1的右子树， k1的右子树变成k2的左子树

/**
 * LL : 左左对应的情况
 * @return 旋转后的根节点
 */
private AVLTreeNode<T> leftLeftRotation(AVLTreeNode<T> k2){
    AVLTreeNode<T> k1;
    k1 = k2.left;
    k2.left = k1.right;
    k1.right = k2;

    k2.height = max(height(k2.left), height(k2.right)) + 1;
    k1.height = max(height(k1.left), k2.height) + 1;
    return k1;
}

RR 旋转

理解了LL旋转之后，RR就比较容易理解了，RR恢复平衡的旋转方法如下：

RR旋转也只需要一次就可完成。

/**
 * RR : 右右对应的情况
 * @return 旋转后的根节点
 */
private AVLTreeNode<T> rightRightRotation(AVLTreeNode<T> k1){
    AVLTreeNode<T> k2;
    k2 = k1.right;
    k1.right = k2.left;
    k2.left = k1;

    k1.height = max(height(k1.left), height(k1.right)) + 1;
    k2.height = max(height(k2.left), k1.right.height) + 1;
    return k1;
}

LR 旋转

LR失去平衡的情况，需要经过两次旋转才能让AVL树祸福平衡。如下图：

第一旋转是围绕k1进行的RR旋转，第二次是围绕k3进行的LL旋转

/**
 * LR : 左右对应的情况
 * @return 旋转后的根节点
 */
private AVLTreeNode<T> leftRightRotation(AVLTreeNode<T> k3){
    k3.left = rightRightRotation(k3.left);
    return leftLeftRotation(k3);
}

RL 旋转

RL是与LR的对称情况！RL恢复平衡的旋转方法如下:

/*
 * RL: 右左对应的情况(右双旋转)
 * 返回值: 旋转后的根节点
 */
private AVLTreeNode<T> rightLeftRotation(AVLTreeNode<T> k1) {
    k1.right = leftLeftRotation(k1.right);

    return rightRightRotation(k1);
}

2.3 插入

插入节点的代码

/**
 * 将节点插入到AVL树中，并返回根节点
 *
 * @param tree AVL树的根节点
 * @param key  插入的节点的键值
 * @return 根节点
 */
private AVLTreeNode<T> insert(AVLTreeNode<T> tree, T key) {
    if (tree == null) {
        // 新建节点
        tree = new AVLTreeNode<T>(key, null, null);
    } else {
        int cmp = key.compareTo(tree.key);
        if (cmp < 0) {   //将key插入到tree的左子树
            tree.left = insert(tree.left, key);
            //插入节点后，若AVL树失去平衡，则进行相应的调节
            if (height(tree.left) - height(tree.left) == 2) {
                if (key.compareTo(tree.left.key) < 0) {
                    tree = leftLeftRotation(tree);
                } else {
                    tree = leftRightRotation(tree);
                }
            }
        } else if (cmp > 0) { //将 key 插入到tree的右子树
            tree.right = insert(tree.right, key);
            //插入节点后，若AVL树失去平衡，则进行相应的调节
            if (height(tree.right) - height(tree.left) == 2) {
                if (key.compareTo(tree.right.key) > 0) {
                    tree = rightRightRotation(tree);
                } else {
                    tree = rightLeftRotation(tree);
                }
            }
        } else {
            System.out.println("添加失败: 不允许添加相同的节点！");
        }
    }
    tree.height = max( height(tree.left), height(tree.right)) + 1;
    return tree;
}

public void insert(T key) {
    mRoot = insert(mRoot, key);
}

2.4 删除

/* 
 * 删除结点(z)，返回根节点
 *
 * 参数说明: 
 *     tree AVL树的根结点
 *     z 待删除的结点
 * 返回值: 
 *     根节点
 */
private AVLTreeNode<T> remove(AVLTreeNode<T> tree, AVLTreeNode<T> z) {
    // 根为空 或者 没有要删除的节点，直接返回null。
    if (tree==null || z==null)
        return null;

    int cmp = z.key.compareTo(tree.key);
    if (cmp < 0) {        // 待删除的节点在"tree的左子树"中
        tree.left = remove(tree.left, z);
        // 删除节点后，若AVL树失去平衡，则进行相应的调节。
        if (height(tree.right) - height(tree.left) == 2) {
            AVLTreeNode<T> r =  tree.right;
            if (height(r.left) > height(r.right))
                tree = rightLeftRotation(tree);
            else
                tree = rightRightRotation(tree);
        }
    } else if (cmp > 0) {    // 待删除的节点在"tree的右子树"中
        tree.right = remove(tree.right, z);
        // 删除节点后，若AVL树失去平衡，则进行相应的调节。
        if (height(tree.left) - height(tree.right) == 2) {
            AVLTreeNode<T> l =  tree.left;
            if (height(l.right) > height(l.left))
                tree = leftRightRotation(tree);
            else
                tree = leftLeftRotation(tree);
        }
    } else {    // tree是对应要删除的节点。
        // tree的左右孩子都非空
        if ((tree.left!=null) && (tree.right!=null)) {
            if (height(tree.left) > height(tree.right)) {
                // 如果tree的左子树比右子树高；
                // 则(01)找出tree的左子树中的最大节点
                //   (02)将该最大节点的值赋值给tree。
                //   (03)删除该最大节点。
                // 这类似于用"tree的左子树中最大节点"做"tree"的替身；
                // 采用这种方式的好处是: 删除"tree的左子树中最大节点"之后，AVL树仍然是平衡的。
                AVLTreeNode<T> max = maximum(tree.left);
                tree.key = max.key;
                tree.left = remove(tree.left, max);
            } else {
                // 如果tree的左子树不比右子树高(即它们相等，或右子树比左子树高1)
                // 则(01)找出tree的右子树中的最小节点
                //   (02)将该最小节点的值赋值给tree。
                //   (03)删除该最小节点。
                // 这类似于用"tree的右子树中最小节点"做"tree"的替身；
                // 采用这种方式的好处是: 删除"tree的右子树中最小节点"之后，AVL树仍然是平衡的。
                AVLTreeNode<T> min = maximum(tree.right);
                tree.key = min.key;
                tree.right = remove(tree.right, min);
            }
        } else {
            AVLTreeNode<T> tmp = tree;
            tree = (tree.left!=null) ? tree.left : tree.right;
            tmp = null;
        }
    }

    return tree;
}

public void remove(T key) {
    AVLTreeNode<T> z; 

    if ((z = search(mRoot, key)) != null)
        mRoot = remove(mRoot, z);
}

3. AVL树测试

3.1 添加节点

添加3,2 不会破坏AVL树的平衡性
添加1之后，AVL树失去平衡（LL）需要LL旋转
添加4不会破坏平衡性
添加5之后，AVL树失去了平衡（RR），需要RR旋转
添加6之后，AVL树失去了平衡（RR），RR旋转
添加7之后，AVL树失去了平衡（RR），RR旋转
添加16后，不会破坏AVL树的平衡性
添加15之后，AVL树失去了平衡（RR），RR旋转
添加14之后，AVL树失去平衡(RL)，RL双旋转
添加13后，AVL树失去了平衡（RR），RR旋转

添加12后，AVL树失去平衡(LL)，LL旋转

添加11后，AVL树失去平衡(LL)，LL旋转

添加10后，AVL树失去平衡(LL)，LL旋转
添加8后，不会破坏AVL树的平衡性
添加9后，AVL树失去平衡(LR)，LR旋转

概括：依次添加3,2,1,4,5,6,7,16,15,14,13,12,11,10,8,9到AVL树中，AVL树旋转过程如下图：

3.2 打印树信息

前序遍历: 7 4 2 1 3 6 5 13 11 9 8 10 12 15 14 16 
中序遍历: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 
后序遍历: 1 3 2 5 6 4 8 10 9 12 11 14 16 15 13 7 
高度: 5
最小值: 1
最大值: 16

3.3 删除节点

删除节点节点8（删除操作不会造成AVL树的不平衡）

删除节点8之后，再打印该AVL树的信息。

1 2	高度: 5 中序遍历: 1 2 3 4 5 6 7 9 10 11 12 13 14 15 16

4. 完成代码

4.1 AVL实现代码

package org.example;

/**
 * @author xiaoyuge
 */
public class AVLTree<T extends Comparable<T>> {

    private AVLTreeNode<T> mRoot; //根节点

    class AVLTreeNode<T extends Comparable<T>> {
        T key; //关键字
        int height; //高度
        AVLTreeNode<T> left; //左子树
        AVLTreeNode<T> right; //右子树

        public AVLTreeNode(T key, AVLTreeNode<T> left, AVLTreeNode<T> right) {
            this.key = key;
            this.height = 0;
            this.left = left;
            this.right = right;
        }

    }

    // 构造函数
    public AVLTree() {
        mRoot = null;
    }

    /*
     * 获取树的高度
     */
    private int height(AVLTreeNode<T> tree) {
        if (tree != null) {
            return tree.height;
        }
        return 0;
    }

    public int height() {
        return height(mRoot);
    }

    /*
     * 比较两个值的大小
     */
    private int max(int a, int b) {
        return a > b ? a : b;
    }

    /*
     * 前序遍历"AVL树"
     */
    private void preOrder(AVLTreeNode<T> tree) {
        if (tree != null) {
            System.out.print(tree.key + " ");
            preOrder(tree.left);
            preOrder(tree.right);
        }
    }

    public void preOrder() {
        preOrder(mRoot);
    }

    /*
     * 中序遍历"AVL树"
     */
    private void inOrder(AVLTreeNode<T> tree) {
        if (tree != null) {
            inOrder(tree.left);
            System.out.print(tree.key + " ");
            inOrder(tree.right);
        }
    }

    public void inOrder() {
        inOrder(mRoot);
    }

    /*
     * 后序遍历"AVL树"
     */
    private void postOrder(AVLTreeNode<T> tree) {
        if (tree != null) {
            postOrder(tree.left);
            postOrder(tree.right);
            System.out.print(tree.key + " ");
        }
    }

    public void postOrder() {
        postOrder(mRoot);
    }

    /*
     * (递归实现)查找"AVL树x"中键值为key的节点
     */
    private AVLTreeNode<T> search(AVLTreeNode<T> x, T key) {
        if (x == null) {
            return x;
        }
        int cmp = key.compareTo(x.key);
        if (cmp < 0) {
            return search(x.left, key);
        } else if (cmp > 0) {
            return search(x.right, key);
        } else {
            return x;
        }
    }

    public AVLTreeNode<T> search(T key) {
        return search(mRoot, key);
    }

    /*
     * (非递归实现)查找"AVL树x"中键值为key的节点
     */
    private AVLTreeNode<T> iterativeSearch(AVLTreeNode<T> x, T key) {
        while (x != null) {
            int cmp = key.compareTo(x.key);

            if (cmp < 0) {
                x = x.left;
            } else if (cmp > 0) {
                x = x.right;
            } else {
                return x;
            }
        }

        return x;
    }

    public AVLTreeNode<T> iterativeSearch(T key) {
        return iterativeSearch(mRoot, key);
    }

    /*
     * 查找最小结点: 返回tree为根结点的AVL树的最小结点。
     */
    private AVLTreeNode<T> minimum(AVLTreeNode<T> tree) {
        if (tree == null) {
            return null;
        }

        while (tree.left != null) {
            tree = tree.left;
        }
        return tree;
    }

    public T minimum() {
        AVLTreeNode<T> p = minimum(mRoot);
        if (p != null) {
            return p.key;
        }

        return null;
    }

    /*
     * 查找最大结点: 返回tree为根结点的AVL树的最大结点。
     */
    private AVLTreeNode<T> maximum(AVLTreeNode<T> tree) {
        if (tree == null) {
            return null;
        }
        while (tree.right != null) {
            tree = tree.right;
        }
        return tree;
    }

    public T maximum() {
        AVLTreeNode<T> p = maximum(mRoot);
        if (p != null) {
            return p.key;
        }

        return null;
    }

    /*
     * LL: 左左对应的情况(左单旋转)。
     *
     * 返回值: 旋转后的根节点
     */
    private AVLTreeNode<T> leftLeftRotation(AVLTreeNode<T> k2) {
        AVLTreeNode<T> k1;

        k1 = k2.left;
        k2.left = k1.right;
        k1.right = k2;

        k2.height = max(height(k2.left), height(k2.right)) + 1;
        k1.height = max(height(k1.left), k2.height) + 1;

        return k1;
    }

    /*
     * RR: 右右对应的情况(右单旋转)。
     *
     * 返回值: 旋转后的根节点
     */
    private AVLTreeNode<T> rightRightRotation(AVLTreeNode<T> k1) {
        AVLTreeNode<T> k2;

        k2 = k1.right;
        k1.right = k2.left;
        k2.left = k1;

        k1.height = max(height(k1.left), height(k1.right)) + 1;
        k2.height = max(height(k2.right), k1.height) + 1;

        return k2;
    }

    /*
     * LR: 左右对应的情况(左双旋转)。
     *
     * 返回值: 旋转后的根节点
     */
    private AVLTreeNode<T> leftRightRotation(AVLTreeNode<T> k3) {
        k3.left = rightRightRotation(k3.left);

        return leftLeftRotation(k3);
    }

    /*
     * RL: 右左对应的情况(右双旋转)。
     *
     * 返回值: 旋转后的根节点
     */
    private AVLTreeNode<T> rightLeftRotation(AVLTreeNode<T> k1) {
        k1.right = leftLeftRotation(k1.right);

        return rightRightRotation(k1);
    }

    /*
     * 将结点插入到AVL树中，并返回根节点
     *
     * 参数说明:
     *     tree AVL树的根结点
     *     key 插入的结点的键值
     * 返回值:
     *     根节点
     */
    private AVLTreeNode<T> insert(AVLTreeNode<T> tree, T key) {
        if (tree == null) {
            // 新建节点
            tree = new AVLTreeNode<T>(key, null, null);
            if (tree == null) {
                System.out.println("ERROR: create avltree node failed!");
                return null;
            }
        } else {
            int cmp = key.compareTo(tree.key);

            if (cmp < 0) {    // 应该将key插入到"tree的左子树"的情况
                tree.left = insert(tree.left, key);
                // 插入节点后，若AVL树失去平衡，则进行相应的调节。
                if (height(tree.left) - height(tree.right) == 2) {
                    if (key.compareTo(tree.left.key) < 0) {
                        tree = leftLeftRotation(tree);
                    } else {
                        tree = leftRightRotation(tree);
                    }
                }
            } else if (cmp > 0) {    // 应该将key插入到"tree的右子树"的情况
                tree.right = insert(tree.right, key);
                // 插入节点后，若AVL树失去平衡，则进行相应的调节。
                if (height(tree.right) - height(tree.left) == 2) {
                    if (key.compareTo(tree.right.key) > 0) {
                        tree = rightRightRotation(tree);
                    } else {
                        tree = rightLeftRotation(tree);
                    }
                }
            } else {    // cmp==0
                System.out.println("添加失败: 不允许添加相同的节点！");
            }
        }

        tree.height = max(height(tree.left), height(tree.right)) + 1;

        return tree;
    }

    public void insert(T key) {
        mRoot = insert(mRoot, key);
    }

    /*
     * 删除结点(z)，返回根节点
     *
     * 参数说明:
     *     tree AVL树的根结点
     *     z 待删除的结点
     * 返回值:
     *     根节点
     */
    private AVLTreeNode<T> remove(AVLTreeNode<T> tree, AVLTreeNode<T> z) {
        // 根为空 或者 没有要删除的节点，直接返回null。
        if (tree == null || z == null) {
            return null;
        }

        int cmp = z.key.compareTo(tree.key);
        if (cmp < 0) {        // 待删除的节点在"tree的左子树"中
            tree.left = remove(tree.left, z);
            // 删除节点后，若AVL树失去平衡，则进行相应的调节。
            if (height(tree.right) - height(tree.left) == 2) {
                AVLTreeNode<T> r = tree.right;
                if (height(r.left) > height(r.right)) {
                    tree = rightLeftRotation(tree);
                } else {
                    tree = rightRightRotation(tree);
                }
            }
        } else if (cmp > 0) {    // 待删除的节点在"tree的右子树"中
            tree.right = remove(tree.right, z);
            // 删除节点后，若AVL树失去平衡，则进行相应的调节。
            if (height(tree.left) - height(tree.right) == 2) {
                AVLTreeNode<T> l = tree.left;
                if (height(l.right) > height(l.left)) {
                    tree = leftRightRotation(tree);
                } else {
                    tree = leftLeftRotation(tree);
                }
            }
        } else {    // tree是对应要删除的节点。
            // tree的左右孩子都非空
            if ((tree.left != null) && (tree.right != null)) {
                if (height(tree.left) > height(tree.right)) {
                    // 如果tree的左子树比右子树高；
                    // 则(01)找出tree的左子树中的最大节点
                    //   (02)将该最大节点的值赋值给tree。
                    //   (03)删除该最大节点。
                    // 这类似于用"tree的左子树中最大节点"做"tree"的替身；
                    // 采用这种方式的好处是: 删除"tree的左子树中最大节点"之后，AVL树仍然是平衡的。
                    AVLTreeNode<T> max = maximum(tree.left);
                    tree.key = max.key;
                    tree.left = remove(tree.left, max);
                } else {
                    // 如果tree的左子树不比右子树高(即它们相等，或右子树比左子树高1)
                    // 则(01)找出tree的右子树中的最小节点
                    //   (02)将该最小节点的值赋值给tree。
                    //   (03)删除该最小节点。
                    // 这类似于用"tree的右子树中最小节点"做"tree"的替身；
                    // 采用这种方式的好处是: 删除"tree的右子树中最小节点"之后，AVL树仍然是平衡的。
                    AVLTreeNode<T> min = minimum(tree.right);
                    tree.key = min.key;
                    tree.right = remove(tree.right, min);
                }
            } else {
                AVLTreeNode<T> tmp = tree;
                tree = (tree.left != null) ? tree.left : tree.right;
                tmp = null;
            }
        }

        tree.height = max(height(tree.left), height(tree.right)) + 1;

        return tree;
    }

    public void remove(T key) {
        AVLTreeNode<T> z;

        if ((z = search(mRoot, key)) != null) {
            mRoot = remove(mRoot, z);
        }
    }

    /*
     * 销毁AVL树
     */
    private void destroy(AVLTreeNode<T> tree) {
        if (tree == null) {
            return;
        }
        if (tree.left != null) {
            destroy(tree.left);
        }
        if (tree.right != null) {
            destroy(tree.right);
        }
        tree = null;
    }

    public void destroy() {
        destroy(mRoot);
    }

    /*
     * 打印"二叉查找树"
     *
     * key        -- 节点的键值
     * direction  --  0，表示该节点是根节点;
     *               -1，表示该节点是它的父结点的左孩子;
     *                1，表示该节点是它的父结点的右孩子。
     */
    private void print(AVLTreeNode<T> tree, T key, int direction) {
        if (tree != null) {
            if (direction == 0)    // tree是根节点
            {
                System.out.printf("%2d is root\n", tree.key, key);
            } else                // tree是分支节点
            {
                System.out.printf("%2d is %2d's %6s child\n", tree.key, key, direction == 1 ? "right" : "left");
            }

            print(tree.left, tree.key, -1);
            print(tree.right, tree.key, 1);
        }
    }

    public void print() {
        if (mRoot != null) {
            print(mRoot, mRoot.key, 0);
        }
    }
}

4.2 AVL 测试代码

/**
 * @author xiaoyuge
 */
public class AVLTreeTest {

    private static final int[] arr = {3, 2, 1, 4, 5, 6, 7, 16, 15, 14, 13, 12, 11, 10, 8, 9};

    public static void main(String[] args) {
        int i;
        AVLTree<Integer> tree = new AVLTree<>();

        System.out.print("== 依次添加: ");
        for(i=0; i<arr.length; i++) {
            System.out.printf("%d ", arr[i]);
            tree.insert(arr[i]);
        }

        System.out.print("\n== 前序遍历: ");
        tree.preOrder();

        System.out.print("\n== 中序遍历: ");
        tree.inOrder();

        System.out.print("\n== 后序遍历: ");
        tree.postOrder();
        System.out.print("\n");

        System.out.printf("== 高度: %d\n", tree.height());
        System.out.printf("== 最小值: %d\n", tree.minimum());
        System.out.printf("== 最大值: %d\n", tree.maximum());
        System.out.print("== 树的详细信息: \n");
        tree.print();

        i = 8;
        System.out.printf("\n== 删除根节点: %d", i);
        tree.remove(i);

        System.out.printf("\n== 高度: %d", tree.height());
        System.out.print("\n== 中序遍历: ");
        tree.inOrder();
        System.out.print("\n== 树的详细信息: \n");
        tree.print();

        // 销毁二叉树
        tree.destroy();
    }
}

== 依次添加: 3 2 1 4 5 6 7 16 15 14 13 12 11 10 8 9 
== 前序遍历: 7 4 2 1 3 6 5 13 11 9 8 10 12 15 14 16 
== 中序遍历: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 
== 后序遍历: 1 3 2 5 6 4 8 10 9 12 11 14 16 15 13 7 
== 高度: 5
== 最小值: 1
== 最大值: 16
== 树的详细信息: 
 7 is root
 4 is  7's   left child
 2 is  4's   left child
 1 is  2's   left child
 3 is  2's  right child
 6 is  4's  right child
 5 is  6's   left child
13 is  7's  right child
11 is 13's   left child
 9 is 11's   left child
 8 is  9's   left child
10 is  9's  right child
12 is 11's  right child
15 is 13's  right child
14 is 15's   left child
16 is 15's  right child

== 删除根节点: 8
== 高度: 5
== 中序遍历: 1 2 3 4 5 6 7 9 10 11 12 13 14 15 16 
== 树的详细信息: 
 7 is root
 4 is  7's   left child
 2 is  4's   left child
 1 is  2's   left child
 3 is  2's  right child
 6 is  4's  right child
 5 is  6's   left child
13 is  7's  right child
11 is 13's   left child
 9 is 11's   left child
10 is  9's  right child
12 is 11's  right child
15 is 13's  right child
14 is 15's   left child
16 is 15's  right child

5. 参考文章

本文主要来源于pdai的https://pdai.tech/md/algorithm/alg-basic-tree-balance.html，在此基础上重新组织和增加了内容。

本文链接： http://xiaoyuge.work/avl/index.html

版权声明： 本博客所有文章除特别声明外，均采用 CC BY 4.0 CN协议许可协议。转载请注明出处！本博客如有侵权，请联系删除！

小余哥xiaoyouge

分享一些技术教程与实践，以及日常踩坑记录。