数据结构与算法笔记目录： 《恋上数据结构》 笔记目录

想加深 Java 基础推荐看这个： Java 强化笔记目录

我的《恋上数据结构》源码（第1季 + 第2季）：https://github.com/szluyu99/Data_Structure_Note

AVL 树是在 二叉搜索树 的基础上学习的。

二叉搜索树缺点分析

• 当 n 比较大时，两者的性能差异比较大
• 比如 n = 1000000 时，二叉搜索树的最低高度是 20，最高高度是 1000000；

由此可见，二叉搜索树添加节点时可能会导致二叉搜索树退化成链表；
而删除节点时也可能会导致二叉搜索树退化成链表；

有没有办法防止二叉搜索树退化成链表？让添加、删除、搜索的复杂度维持在 O(logn)？

改进二叉搜索树

平衡（Balance）

平衡：当节点数量固定时，左右子树的高度越接近，这棵二叉树就越平衡（高度越低）

理想平衡

最理想的平衡，就是像完全二叉树、满二叉树那样，高度是最小的；

如何改进二叉搜索树？

首先，节点的添加、删除顺序是无法限制的，可以认为是随机的：

• 所以，改进方案是：在节点的添加、删除操作之后，想办法让二叉搜索树恢复平衡（减小树的高度）

如果接着继续调整节点的位置，完全可以达到理想平衡，但是付出的代价可能会比较大；

• 比如调整的次数会比较多，反而增加了时间复杂度；
• 总结来说，比较合理的改进方案是：用尽量少的调整次数达到适度平衡即可；

一棵达到适度平衡的二叉搜索树，可以称之为：平衡二叉搜索树

平衡二叉搜索树（Balanced Binary Search Tree）

英文简称为：BBST

经典常见的平衡二叉搜索树有：

• AVL树
  Windows NT 内核中广泛使用
• 红黑树
  C++ STL（比如 map、set ）
  Java 的 TreeMap、TreeSet、HashMap、HashSet
  Linux 的进程调度
  Ngix 的 timer 管理

一般也称它们为：自平衡的二叉搜索树（Self-balancing Binary Search Tree）

AVL树

AVL 树是最早发明的自平衡二叉搜索树之—

平衡因子（Balance Factor）：某结点的左右子树的高度差

AVL树的特点：

• 每个节点的平衡因子只可能是 1、0、-1

(绝对值 ≤ 1，如果超过 1，称之为 “失衡")

• 每个节点的左右子树高度差不超过1
• 搜索、添加、删除的时间复杂度是 $O(logn)$

BST 对比 AVLTree

输入数据：35, 37, 34, 56, 25, 62, 57, 9, 74, 32, 94, 80, 75, 100, 16, 82

继承 BST

这里 AVLTree 要继承的 BST，与之前学习的 二叉搜索树 几乎一样，有点小区别；

• 在添加节点之后增加了 afterAdd() 用于调整平衡；
• 在删除节点之后增加了 afterRemove() 用于调整平衡；

注意：BST 要继承 BinaryTree；

import java.util.Comparator;

/**
 * 二叉搜索树
 */
@SuppressWarnings("unchecked")
public class BST<E> extends BinaryTree<E> {

    // 比较器，根据传入的比较器实现 compareTo() 方法
    private Comparator<E> comparator;

    public BST(Comparator<E> comparator) { // 可以传一个比较器
        this.comparator = comparator;
    }

    public BST() { // 不传比较器，相当于传入一个 null
        this(null); //
    }

    /**
     * 添加元素
     */
    public void add(E element) {
        elementNotNullCheck(element); // 不能传入空节点

        // 传入第一个节点, 若根节点为null, 则该节点为根节点
        if (root == null) {
            root = createNode(element, null);
            size++;
            // 新添加节点之后的处理
            afterAdd(root);
            return;
        }
        // 添加的不是第一个节点, 找到父节点
        Node<E> parent = root;
        Node<E> node = root;
        int cmp = 0;
        do {
            // 比较【传入节点的元素值】与【父节点的元素值】
            cmp = compareTo(element, node.element); // 方向
            parent = node; // 父节点
            if (cmp > 0) { // 传入节点比父节点要大, 往右
                node = node.right;
            } else if (cmp < 0) { // 传入节点比父节点要小, 往左
                node = node.left;
            } else { // 相等，最好是覆盖掉, 也可以采取其他操作, 看具体需求
                node.element = element;
                return;
            }
        } while (node != null);

        // 上面只是找到了要添加位置的父节点, 下面要将元素添加进去
        Node<E> newNode = createNode(element, parent);
        if (cmp > 0) {
            parent.right = newNode;
        } else {
            parent.left = newNode;
        }
        size++;

        // 新添加节点之后的处理
        afterAdd(newNode);
    }

    /**
     * 根据传入的值删除元素
     */
    public void remove(E element) {
        remove(node(element));
    }
    // 根据节点删除元素
    private void remove(Node<E> node) {
        if (node == null) return;

        size--;

        if (node.hasTwoChildren()) { // 度为2的节点
            // 找到后继节点
            Node<E> s = successor(node);
            // 用后继节点的值覆盖度为2的节点的值
            node.element = s.element;
            // 删除后继节点
            node = s;
        }

        // 删除node节点(node的度必然是1或者0)
        Node<E> replacement = node.left != null ? node.left : node.right;

        if (replacement != null) { // node是度为1的节点
            // 更改parent
            replacement.parent = node.parent;
            // 更改parent的left、right的指向
            if (node.parent == null) { // node是度为1的节点并且是根节点
                root = replacement;
            } else if (node == node.parent.left) {
                node.parent.left = replacement;
            } else { // node == node.parent.right
                node.parent.right = replacement;
            }

            // 删除节点后的调整
            afterRemove(node);
        } else if (node.parent == null) { // node是叶子节点并且是根节点
            root = null;

            // 删除节点后的调整
            afterRemove(node);
        } else { // node是叶子节点，但不是根节点
            if (node == node.parent.left) {
                node.parent.left = null;
            } else { // node == node.parent.right
                node.parent.right = null;
            }

            // 删除节点后的调整
            afterRemove(node);
        }
    }

    /**
     * 添加node之后的调整
     */
    protected void afterAdd(Node<E> node) {}

    /**
     * 删除node之后的调整
     */
    protected void afterRemove(Node<E> node) {}

    // 根据元素值获取节点元素
    private Node<E> node(E element) {
        elementNotNullCheck(element);

        Node<E> node = root;
        while (node != null) {
            int cmp = compareTo(element, node.element);
            if (cmp < 0) {
                node = node.left;
            } else if (cmp > 0) {
                node = node.right;
            } else { // cmp == 0
                return node;
            }
        }
        return null;
    }

    // 节点元素比较
    private int compareTo(E e1, E e2) {
        if (comparator != null) { // 传入比较器则通过比较器比较
            return comparator.compare(e1, e2);
        }
        // 没传比较器，元素内部必须自行实现了 Comparable 接口
        return ((Comparable<E>) e1).compareTo(e2);
    }

    // 检测传入的节点是否为空
    private void elementNotNullCheck(E element) {
        if (element == null) { // 不能传入空节点
            throw new IllegalArgumentException("element must not null");
        }
    }

}

AVL树基础

public class AVLTree<E> extends BST<E> {

    public AVLTree(Comparator<E> comparator) {
        super(comparator);
    }

    public AVLTree() {
        this(null);
    }

    // AVL树的节点，需要计算平衡因子，因此比普通二叉树多维护一个height属性(将height放入普通二叉树里没有用处，浪费空间)
    private static class AVLNode<E> extends Node<E> {
        int height = 1;

        public AVLNode(E element, Node<E> parent) {
            super(element, parent);
        }

        public int balanceFactor() { // 获取该节点平衡因子(左子树高度 - 右子树高度)
            int leftHeight = left == null ? 0 : ((AVLNode<E>) left).height;
            int rightHeight = right == null ? 0 : ((AVLNode<E>) right).height;
            return leftHeight - rightHeight;
        }

        public void updateHeight() { // 更新高度
            int leftHeight = left == null ? 0 : ((AVLNode<E>) left).height;
            int rightHeight = right == null ? 0 : ((AVLNode<E>) right).height;
            height = 1 + Math.max(leftHeight, rightHeight);
        }

        public Node<E> tallerChild() {
            int leftHeight = left == null ? 0 : ((AVLNode<E>) left).height;
            int rightHeight = right == null ? 0 : ((AVLNode<E>) right).height;
            if (leftHeight > rightHeight) return left;
            if (rightHeight > leftHeight) return right;
            // 高度一样则返回同方向的，左子节点则返回左，否则返回右
            return isLeftChild() ? left : right;
        }

        @Override
        public String toString() {
            String parentString = "null";
            if (parent != null) {
                parentString = parent.element.toString();
            }
            return element + "_p(" + parentString + ")_h(" + height + ")";
        }
    }
    
    /**
     * 重写父类中的 createNode
     * 返回 AVLNode
     */
    @Override
    protected Node<E> createNode(E element, Node<E> parent) {
        return new AVLNode<>(element, parent);
    }

    /**
     * 判断传入节点是否平衡（平衡因子的绝对值 <= 1）
     */
    private boolean isBalanced(Node<E> node) {
        return Math.abs(((AVLNode<E>) node).balanceFactor()) <= 1;
    }

    /**
     * 更新高度
     */
    private void updateHeight(Node<E> node) {
        ((AVLNode<E>) node).updateHeight();
    }
}

添加节点导致的失衡

示例：往下面这棵子树中添加 13

• 最坏情况：可能会导致所有祖先节点都失衡
• 父节点、非祖先节点，都不可能失衡

修复平衡的操作：

• LL – 右旋转（单旋）
• RR – 左旋转（单旋）
• LR – 先左旋，再右旋（双旋）
• RL – 先右旋，再左旋（双旋）

有些教程里面：

• 把右旋转叫做 zig，旋转之后的状态叫做 zigged
• 把左旋转叫做 zag，旋转之后的状态叫做 zagged

LL – 右旋转（单旋）

让 p 成为这颗子树的根节点

• g.left = p.right
• p.right = g

旋转后仍然是一颗 二叉搜索树：T0 < n < T1 < p < T2 < g < T3

还需要注意维护的内容

• T2、p、g 的 parent 属性
• 先后更新 g、p 的高度

/**
 * 右旋转
 */
private void rotateRight(Node<E> grand) {
    Node<E> parent = grand.left;
    Node<E> child = parent.right;
    grand.left = child;
    parent.right = grand;

    afterRotate(grand, parent, child);
}

RR – 左旋转（单旋）

让 p 成为这颗子树的根节点

• g.right = p.left
• p.left = g

旋转后仍然是一颗 二叉搜索树：T0 < g < T1 < o < T2 < n < T3

还需要注意维护的内容

• T1、p、g 的 parent 属性
• 先后更新 g、p 的高度

/**
 * 左旋转
 */
private void rotateLeft(Node<E> grand) {
    Node<E> parent = grand.right;
    Node<E> child = parent.left;
    grand.right = child;
    parent.left = grand;
    
    afterRotate(grand, parent, child);
}

LR – 先左旋，再右旋（双旋）

LR 就是 先进行 左旋转 – RR、再进行 右旋转 – LL；

• 先左旋转：p.right = n.left、n.left = p
• 再右旋转：g.left = n.right、n.right = g

旋转后仍然是一颗 二叉搜索树：T0 < p < T1 < n < T2 < g < T3

RL – 先右旋，再左旋（双旋）

RL 就是 先进行 右旋转 – LL、再进行 左旋转 – RR；

• 先右旋转：p.left = n.right、n.right = p
• 再左旋转：g.right = n.left、n.left = g

旋转后仍然是一颗 二叉搜索树：T0 < g < T1 < n < T2 < p < T3

旋转之后维护的内容

/**
 * 公共代码：不管是左旋转、右旋转，都要执行的
 * @param grand 失衡节点
 * @param parent 失衡节点的tallerChild
 * @param child child g和p需要交换的子树(本来是p的子树, 后面会变成g的子树)
 */
private void afterRotate(Node<E> grand, Node<E> parent, Node<E> child) {
    // 让parent成为子树的根节点
    parent.parent = grand.parent;
    if (grand.isLeftChild()) {
        grand.parent.left = parent;
    } else if (grand.isRightChild()) {
        grand.parent.right = parent;
    } else {// grand是root节点
        root = parent;
    }

    // 更新child的parent
    if (child != null) {
        child.parent = grand;
    }

    // 更新grand的parent
    grand.parent = parent;

    // 更新高度
    updateHeight(grand);
    updateHeight(parent);
}

添加之后的修复图解

输入数据：13, 14, 15, 12, 11, 17, 16, 8, 9, 1

输入13：正常
输入14：正常
输入15：==13失衡==，RR，左旋转

输入12：正常
输入11：==13失衡==，LL，右旋转

输入17：正常
输入16：==15失衡==，RL，先右选择、再左旋转

输入8：正常
输入9：==11失衡==，LR，先左旋转、再右旋转

输入1：==12失衡==，LL，右旋转

添加之后的修复 - 代码实现

/**
 * 增加节点后的调整
 */
@Override
protected void afterAdd(Node<E> node) {
    while ((node = node.parent) != null) {
        if (isBalanced(node)) { // 如果平衡
            // 更新高度
            updateHeight(node);
        } else { // 如果不平衡
            // 恢复平衡
            rebalance(node);
            // 只要恢复了最下面的子树的平衡, 则整棵树恢复平衡
            break;
        }
    }
}

/**
 * 恢复平衡
 * @param grand 高度最低的那个不平衡节点
 */
private void rebalance(Node<E> grand) {
    Node<E> parent = ((AVLNode<E>) grand).tallerChild();
    Node<E> node = ((AVLNode<E>) parent).tallerChild();
    if (parent.isLeftChild()) {//L
        if (node.isLeftChild()) {//LL
            rotateRight(grand);//LL则右旋
        } else {//LR
            rotateLeft(parent);
            rotateRight(grand);
        }
    } else {//R
        if (node.isLeftChild()) {//RL
            rotateRight(parent);
            rotateLeft(grand);
        } else {//RR
            rotateLeft(grand);//RR则左旋
        }
    }
}

统一所有的旋转操作

/**
 * 统一旋转
 */
private void rotate(
    Node<E> r, // 子树的根节点
    Node<E> b, Node<E> c,
    Node<E> d,
    Node<E> e, Node<E> f) {
    // 让d成为这颗子树的根结点
    d.parent = r.parent;
    if (r.isLeftChild()) {
        r.parent.left = d;
    } else if (r.isRightChild()) {
        r.parent.right = d;
    } else {
        root = d;
    }
    // b-c
    b.right = c;
    if (c != null) {
        c.parent = b;
    }
    updateHeight(b);

    // e-f
    f.left = e;
    if (e != null) {
        e.parent = f;
    }
    updateHeight(f);

    // b-d-f
    d.left = b;
    d.right = f;
    b.parent = d;
    f.parent = d;
    updateHeight(d);
}

private void rebalance(Node<E> grand) {
    Node<E> parent = ((AVLNode<E>) grand).tallerChild();
    Node<E> node = ((AVLNode<E>) parent).tallerChild();
    if (parent.isLeftChild()) {//L
        if (node.isLeftChild()) {//LL
            rotate(grand, node, node.right, parent, parent.right, grand);
        } else {//LR
            rotate(grand, parent, node.left, node, node.right, grand);
        }
    } else {//R
        if (node.isLeftChild()) {//RL
            rotate(grand, grand, node.left, node, node.right, parent);
        } else {//RR
            rotate(grand, grand, parent.left, parent, node.left, node);
        }
    }
}

删除节点导致的失衡

示例：删除子树中的 16

• 可能会导致父节点或祖先节点失衡（只有1个节点会失衡），其他节点，都不可能失衡

LL – 右旋转（单旋）

• 如果绿色节点不存在，更高层的祖先节点可能也会失衡，需要再次恢复平衡，然后又可能导致更高层的祖先节点失衡...
• 极端情况下，所有祖先节点都需要进行恢复平衡的操作，共 O(logn) 次调整

RR – 左旋转（单旋）

LR – RR左旋转，LL右旋转（双旋）

RL – LL右旋转，RR左旋转（双旋）

删除之后的修复

/**
 * 删除节点后的调整
 */
@Override
protected void afterRemove(Node<E> node) {
    while ((node = node.parent) != null) {
        if (isBalanced(node)) {
            // 更新高度
            updateHeight(node);
        } else {
            // 恢复平衡
            rebalance(node);
        }
    }
}

AVL树总结

添加

• 可能会导致所有祖先节点都失衡
• 只要让高度最低的失衡节点恢复平衡，整棵树就恢复平衡【仅需 O(1) 次调整】

删除

• 可能会导致父节点或祖先节点失衡（只有1个节点会失衡）
• 恢复平衡后，可能会导致更高层的祖先节点失衡【最多需要 O(logn) 次调整】

平均时间复杂度

• 搜索：O(logn)
• 添加：O(logn)，仅需 O(1) 次的旋转操作
• 删除：O(logn)，最多需要 O(logn) 次的旋转操作

AVL树完整源码

package com.mj.tree;

import java.util.Comparator;

public class AVLTree<E> extends BST<E> {

    public AVLTree(Comparator<E> comparator) {
        super(comparator);
    }

    public AVLTree() {
        this(null);
    }

    // AVL树的节点，需要计算平衡因子，因此比普通二叉树多维护一个height属性(将height放入普通二叉树里没有用处，浪费空间)
    private static class AVLNode<E> extends Node<E> {
        int height = 1;

        public AVLNode(E element, Node<E> parent) {
            super(element, parent);
        }

        public int balanceFactor() { // 获取该节点平衡因子(左子树高度 - 右子树高度)
            int leftHeight = left == null ? 0 : ((AVLNode<E>) left).height;
            int rightHeight = right == null ? 0 : ((AVLNode<E>) right).height;
            return leftHeight - rightHeight;
        }

        public void updateHeight() { // 更新高度
            int leftHeight = left == null ? 0 : ((AVLNode<E>) left).height;
            int rightHeight = right == null ? 0 : ((AVLNode<E>) right).height;
            height = 1 + Math.max(leftHeight, rightHeight);
        }

        public Node<E> tallerChild() {
            int leftHeight = left == null ? 0 : ((AVLNode<E>) left).height;
            int rightHeight = right == null ? 0 : ((AVLNode<E>) right).height;
            if (leftHeight > rightHeight) return left;
            if (rightHeight > leftHeight) return right;
            // 高度一样则返回同方向的，左子节点则返回左，否则返回右
            return isLeftChild() ? left : right;
        }

        @Override
        public String toString() {
            String parentString = "null";
            if (parent != null) {
                parentString = parent.element.toString();
            }
            return element + "_p(" + parentString + ")_h(" + height + ")";
        }
    }

    /**
     * 增加节点后的调整
     */
    @Override
    protected void afterAdd(Node<E> node) {
        while ((node = node.parent) != null) {
            if (isBalanced(node)) { // 如果平衡
                // 更新高度
                updateHeight(node);
            } else { // 如果不平衡
                // 恢复平衡
                rebalance(node);
                // AVL树中, 只要恢复了最下面的子树的平衡, 则整棵树恢复平衡
                break;
            }
        }
    }

    /**
     * 删除节点后的调整
     */
    @Override
    protected void afterRemove(Node<E> node) {
        while ((node = node.parent) != null) {
            if (isBalanced(node)) {
                // 更新高度
                updateHeight(node);
            } else {
                // 恢复平衡
                rebalance(node);
            }
        }
    }

    /**
     * 重写父类中的 createNode
     * 返回 AVLNode
     */
    @Override
    protected Node<E> createNode(E element, Node<E> parent) {
        return new AVLNode<>(element, parent);
    }

    /**
     * 判断传入节点是否平衡（平衡因子的绝对值 <= 1）
     */
    private boolean isBalanced(Node<E> node) {
        return Math.abs(((AVLNode<E>) node).balanceFactor()) <= 1;
    }

    /**
     * 更新高度
     */
    private void updateHeight(Node<E> node) {
        ((AVLNode<E>) node).updateHeight();
    }

    /**
     * 恢复平衡
     * @param grand 高度最低的那个不平衡节点
     */
    private void rebalance2(Node<E> grand) {
        Node<E> parent = ((AVLNode<E>) grand).tallerChild();
        Node<E> node = ((AVLNode<E>) parent).tallerChild();
        if (parent.isLeftChild()) { // L
            if (node.isLeftChild()) { // LL
                rotateRight(grand); // LL则右旋
            } else { // LR
                rotateLeft(parent);
                rotateRight(grand);
            }
        } else { // R
            if (node.isLeftChild()) { // RL
                rotateRight(parent);
                rotateLeft(grand);
            } else { // RR
                rotateLeft(grand); // RR则左旋
            }
        }
    }

    private void rebalance(Node<E> grand) {
        Node<E> parent = ((AVLNode<E>) grand).tallerChild();
        Node<E> node = ((AVLNode<E>) parent).tallerChild();
        if (parent.isLeftChild()) {//L
            if (node.isLeftChild()) {//LL
                rotate(grand, node, node.right, parent, parent.right, grand);
            } else {//LR
                rotate(grand, parent, node.left, node, node.right, grand);
            }
        } else {//R
            if (node.isLeftChild()) {//RL
                rotate(grand, grand, node.left, node, node.right, parent);
            } else {//RR
                rotate(grand, grand, parent.left, parent, node.left, node);
            }
        }
    }

    /**
     * 统一旋转
     */
    private void rotate(
            Node<E> r, // 子树的根节点
            Node<E> b, Node<E> c,
            Node<E> d,
            Node<E> e, Node<E> f) {
        // 让d成为这颗子树的根结点
        d.parent = r.parent;
        if (r.isLeftChild()) {
            r.parent.left = d;
        } else if (r.isRightChild()) {
            r.parent.right = d;
        } else {
            root = d;
        }
        // b-c
        b.right = c;
        if (c != null) {
            c.parent = b;
        }
        updateHeight(b);

        // e-f
        f.left = e;
        if (e != null) {
            e.parent = f;
        }
        updateHeight(f);

        // b-d-f
        d.left = b;
        d.right = f;
        b.parent = d;
        f.parent = d;
        updateHeight(d);
    }
    /*private void rotate(
            Node<E> r, // 子树的根节点
            Node<E> a, Node<E> b, Node<E> c,
            Node<E> d,
            Node<E> e, Node<E> f, Node<E> g) {
        // 让d成为这颗子树的根结点
        d.parent = r.parent;
        if(r.isLeftChild()){
            r.parent.left = d;
        }else if(r.isRightChild()){
            r.parent.right = d;
        }else{
            root = d;
        }
        // a-b-c
        b.left = a;
        if(a!=null){
            a.parent = b;
        }
        b.right = c;
        if(c!=null){
            c.parent = b;
        }
        updateHeight(b);
        
        // e-f-g
        f.left = e;
        if(e != null){
            e.parent = f;
        }
        f.right = g;
        if(g != null){
            g.parent = f;
        }
        updateHeight(f);
        
        // b-d-f
        d.left = b;
        d.right = f;
        b.parent = d;
        f.parent = d;
        updateHeight(d);
    }*/

    /**
     * 左旋转
     */
    private void rotateLeft(Node<E> grand) {
        Node<E> parent = grand.right;
        Node<E> child = parent.left;
        grand.right = child;
        parent.left = grand;

        afterRotate(grand, parent, child);
    }

    /**
     * 右旋转
     */
    private void rotateRight(Node<E> grand) {
        Node<E> parent = grand.left;
        Node<E> child = parent.right;
        grand.left = child;
        parent.right = grand;

        afterRotate(grand, parent, child);
    }

    /**
     * 公共代码：不管是左旋转、右旋转，都要执行的
     * @param grand 失衡节点
     * @param parent 失衡节点的tallerChild
     * @param child child g和p需要交换的子树(本来是p的子树, 后面会变成g的子树)
     */
    private void afterRotate(Node<E> grand, Node<E> parent, Node<E> child) {
        // 让parent成为子树的根节点
        parent.parent = grand.parent;
        if (grand.isLeftChild()) {
            grand.parent.left = parent;
        } else if (grand.isRightChild()) {
            grand.parent.right = parent;
        } else {// grand是root节点
            root = parent;
        }

        // 更新child的parent
        if (child != null) {
            child.parent = grand;
        }

        // 更新grand的parent
        grand.parent = parent;

        // 更新高度
        updateHeight(grand);
        updateHeight(parent);
    }

}

测试

package com.mj;

import com.mj.printer.BinaryTrees;
import com.mj.tree.AVLTree;

public class Main {
    // Integer类型的数据
    public static void test1(){
        Integer date[] = new Integer[] {
            75, 94, 21, 7, 93, 31, 83, 65, 43, 50, 57, 56
            };
        AVLTree<Integer> avl = new AVLTree<>();
        for (int i = 0; i < date.length; i++) {
            avl.add(date[i]);
            System.out.println("【" + date[i] + "】");
            BinaryTrees.println(avl);
            System.out.println("-----------------------------------------");
        }
    }

    // 删除
    public static void test2(){
        Integer data[] = new Integer[] {
                35, 37, 34, 56, 25, 62, 57, 9, 74, 32, 94, 80, 75, 100, 16, 82
        };
        
        AVLTree<Integer> avl = new AVLTree<>();
        for (int i = 0; i < data.length; i++) {
            avl.add(data[i]);
//            System.out.println("【" + data[i] + "】");
//            BinaryTrees.println(avl);
//            System.out.println("---------------------------------------");
        }
        
        for (int i = 0; i < data.length; i++) {
            avl.remove(data[i]);
            System.out.println("【" + data[i] + "】");
            BinaryTrees.println(avl);
            System.out.println("---------------------------------------");
        }
        
        
        BinaryTrees.println(avl);
    }
    public static void main(String[] args) {
        // test1();
        test2();
    }
}

【35】
             ┌──────────37_p(null)──────────┐
             │                              │
   ┌─────25_p(37)─────┐         ┌────────62_p(37)────────┐
   │                  │         │                        │
9_p(25)─┐        ┌─34_p(25) 56_p(62)─┐         ┌──────80_p(62)─────┐
        │        │                   │         │                   │
     16_p(9) 32_p(34)             57_p(56) 74_p(80)─┐         ┌─94_p(80)─┐
                                                    │         │          │
                                                 75_p(74) 82_p(94)   100_p(94)
---------------------------------------
【37】
             ┌───────────56_p(null)──────────┐
             │                               │
   ┌─────25_p(56)─────┐           ┌───────80_p(56)──────┐
   │                  │           │                     │
9_p(25)─┐        ┌─34_p(25) ┌─62_p(80)─┐           ┌─94_p(80)─┐
        │        │          │          │           │          │
     16_p(9) 32_p(34)   57_p(62)    74_p(62)─┐ 82_p(94)   100_p(94)
                                             │
                                          75_p(74)
---------------------------------------
【34】
         ┌─────────56_p(null)────────┐
         │                           │
   ┌─25_p(56)─┐           ┌───────80_p(56)──────┐
   │          │           │                     │
9_p(25)─┐  32_p(25) ┌─62_p(80)─┐           ┌─94_p(80)─┐
        │           │          │           │          │
     16_p(9)    57_p(62)    74_p(62)─┐ 82_p(94)   100_p(94)
                                     │
                                  75_p(74)
---------------------------------------
【56】
         ┌────────57_p(null)────────┐
         │                          │
   ┌─25_p(57)─┐           ┌──────80_p(57)─────┐
   │          │           │                   │
9_p(25)─┐  32_p(25) ┌─74_p(80)─┐         ┌─94_p(80)─┐
        │           │          │         │          │
     16_p(9)    62_p(74)    75_p(74) 82_p(94)   100_p(94)
---------------------------------------
【25】
         ┌────────57_p(null)────────┐
         │                          │
   ┌─16_p(57)─┐           ┌──────80_p(57)─────┐
   │          │           │                   │
9_p(16)    32_p(16) ┌─74_p(80)─┐         ┌─94_p(80)─┐
                    │          │         │          │
                62_p(74)    75_p(74) 82_p(94)   100_p(94)
---------------------------------------
【62】
         ┌───────57_p(null)───────┐
         │                        │
   ┌─16_p(57)─┐         ┌──────80_p(57)─────┐
   │          │         │                   │
9_p(16)    32_p(16) 74_p(80)─┐         ┌─94_p(80)─┐
                             │         │          │
                          75_p(74) 82_p(94)   100_p(94)
---------------------------------------
【57】
         ┌─────74_p(null)────┐
         │                   │
   ┌─16_p(74)─┐         ┌─80_p(74)─┐
   │          │         │          │
9_p(16)    32_p(16) 75_p(80)  ┌─94_p(80)─┐
                              │          │
                          82_p(94)   100_p(94)
---------------------------------------
【9】
    ┌─────74_p(null)────┐
    │                   │
16_p(74)─┐         ┌─80_p(74)─┐
         │         │          │
      32_p(16) 75_p(80)  ┌─94_p(80)─┐
                         │          │
                     82_p(94)   100_p(94)
---------------------------------------
【74】
    ┌─────75_p(null)────┐
    │                   │
16_p(75)─┐         ┌─94_p(75)─┐
         │         │          │
      32_p(16) 80_p(94)─┐ 100_p(94)
                        │
                     82_p(80)
---------------------------------------
【32】
          ┌─80_p(null)─┐
          │            │
    ┌─75_p(80)    ┌─94_p(80)─┐
    │             │          │
16_p(75)      82_p(94)   100_p(94)
---------------------------------------
【94】
          ┌─80_p(null)─┐
          │            │
    ┌─75_p(80)   ┌─100_p(80)
    │            │
16_p(75)     82_p(100)
---------------------------------------
【80】
          ┌─82_p(null)─┐
          │            │
    ┌─75_p(82)     100_p(82)
    │
16_p(75)
---------------------------------------
【75】
    ┌─82_p(null)─┐
    │            │
16_p(82)     100_p(82)
---------------------------------------
【100】
    ┌─82_p(null)
    │
16_p(82)
---------------------------------------
【16】
82_p(null)
---------------------------------------
【82】
---------------------------------------