目录

一、AVL树的概念

二、平衡调整

1、自平衡原理

例子一：

例子二：

2、LL旋转

3、RL旋转

4、RR旋转

5、LR旋转

三、插入结点和删除结点

1、插入结点

2、删除结点

四、完整代码

1、AVL树结点

2、AVL树相关方法

3、测试方法

---

一、AVL树的概念

       AVL树本质上是一棵二叉搜索树，即它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉搜索树。另外，AVL树每个结点的左右子树的高度之差，即平衡因子的绝对值不超过1，以实现查询操作的时间复杂度从传统二叉搜索树的O(N)降为O(logN)。

二、平衡调整

        首先，为什么AVL树需要有“自平衡”的功能？其实从AVL树的特点就可以看出来，因为AVL树每个结点的平衡因子的绝对值不超过1，所以在插入结点和删除结点后，要检查整棵树是否仍然平衡，如果不是则进行调整，使其恢复平衡。可以用以下Java代码来表示AVL树的结点：

public class AVLNode {
    public int key; // 结点的键，用于标识结点在AVL树中的位置
    public Object value; // 结点的值，用于存储数据
    public int height; // 结点的高度
    public AVLNode left; // 结点的左指针
    public AVLNode right; // 结点的右指针

    public AVLNode(int key, Object value) {
        this.key = key;
        this.value = value;
        height = 1;
    }
}

其中，结点高度（height）不是固定的，会随着结点数量的变化而变化，以下是更新结点高度的代码：

private void resetHeight(AVLNode avlNode) {
    avlNode.height = Math.max(
            avlNode.left == null ? 0 : avlNode.left.height,
            avlNode.right == null ? 0 : avlNode.right.height
    ) + 1;
}

1、自平衡原理

下面用两个例子来探讨自平衡的实现原理。

例子一：

 

图2.1.1

如图2.1.1所示，可以看出结点1的平衡因子为-2，整棵树处于不平衡状态，如果想让其恢复平衡，需要结点1的右子树“让”一些结点给左子树，因此，不难看出，可以对结点1进行左旋转来达到目的，以下是左旋转步骤：

private AVLNode leftRevolve(AVLNode avlNode) {
    // 先保存avlNode的右子树
    AVLNode right = avlNode.right;

    // avlNode的右指针指向right的左子树
    avlNode.right = right.left;

    // right的左指针指向avlNode
    right.left = avlNode;

    // 先更新avlNode的高度
    resetHeight(avlNode);

    // 再更新right的高度
    resetHeight(right);

    // 返回right作为调整后的root
    return right;
}

经过一次左旋转之后，整棵树变为：

图2.1.2

要注意的是，在旋转完成后，必须先更新结点1的高度，再更新结点3的高度，因为结点3的高度来自于结点1的高度和结点4的高度，而结点4没有参与旋转，因此不需要更新其高度。

例子二：

        

图2.1.3

如图2.1.3所示，与例子1的区别是，结点3的左子树多了结点2。此时结点1的平衡因子为-2，同例子1，也要进行左旋转来达到平衡，以下是旋转结果：

图2.1.4

可以看出，与例子1的旋转结果几乎一致，只不过结点1的右子树多了结点2，这是这行代码完成的：

// avlNode的右指针指向right的左子树
avlNode.right = right.left;

右旋转同理，不再赘述，以下是右旋转的代码：

private AVLNode rightRevolve(AVLNode avlNode) {
    // 保存avlNode的左子树
    AVLNode left = avlNode.left;

    // avlNode的左指针指向left的右子树
    avlNode.left = left.right;

    // left的右指针指向avlNode
    left.right = avlNode;

    // 先更新avlNode的高度
    resetHeight(avlNode);

    // 再更新left的高度
    resetHeight(left);

    // 返回left作为调整后的root
    return left;
}

下面，开始讨论复杂一点的情况，以下图示中以"key-height"的形式展示每个结点。

2、LL旋转

图2.2.1

如图2.2.1所示，可以看出结点4的平衡因子为-3，为不平衡状态，而除了结点4以外，其它所有结点都处于平衡状态，因此，只需要对结点4进行左旋转，以下是旋转结果：

图2.2.2

 可以看出，整棵树已经平衡，实际上只经历了一次左旋转，因此，不要被LL的字面含义所误导。

3、RL旋转

 

图2.3.1

如图2.2.3所示，同样只有结点4不平衡（平衡因子-3），而如果仍然按照LL旋转中的方法，只对结点4进行一次左旋转，会发生什么？

图2.3.2

可以看到，不仅结点4没有恢复平衡（平衡因子-2），还多了一个不平衡的结点8 （平衡因子2），

其实，这也是这行代码导致的：

// avlNode的右指针指向right的左子树
avlNode.right = right.left;

不难看出，只要有一种办法能让结点5和结点7不再拥有共同的父结点，并且父结点属于兄弟关系，就能让整棵树平衡，而这个办法就是RL旋转，顾名思义，就是先右旋转，再左旋转，那么，对于图2.2.3，先将结点8右旋转（即使结点8已经处于平衡状态），以让结点5和结点7不再处于同一个父结点下，旋转结果如下：

图2.3.3

如图2.3.3所示，结点5和结点7已经不再拥有共同的父结点，但它们的父结点还不属于兄弟关系，因此，再对结点4进行一次左旋转：

图2.3.4

此时，结点5的父结点和结点7的父结点成为兄弟关系，整棵树达到平衡状态。

4、RR旋转

原理同LL旋转，因此直接展示旋转前后对比图：

图2.4.1

 

图2.4.2

5、LR旋转

原理同RL旋转，因此直接展示旋转过程：

图2.5.1

 

图2.5.2

 

图2.5.3

以上四种旋转的Java代码实现如下：

private AVLNode reBalance(AVLNode avlNode) {
    // 获取avlNode的平衡因子
    int altitudeDiff = getAltitudeDiff(avlNode);

    if (Math.abs(altitudeDiff) > 1) {
        if (altitudeDiff < 0) { // LL旋转或者RL旋转
            // avlNode的右子树的平衡因子只可能为-1|0|1
            if (getAltitudeDiff(avlNode.right) == 1) {
                // avlNode的右子树右旋
                avlNode.right = rightRevolve(avlNode.right);
            }
            // avlNode左旋
            return leftRevolve(avlNode);
        } else { // RR旋转或者LR旋转
            // avlNode的左子树的平衡因子只可能为-1|0|1
            if (getAltitudeDiff(avlNode.left) == -1) {
                // avlNode的左子树左旋
                avlNode.left = leftRevolve(avlNode.left);
            }
            // avlNode右旋
            return rightRevolve(avlNode);
        }
    }
    return avlNode;
}

获取结点高度差（平衡因子）：

private int getAltitudeDiff(AVLNode avlNode) {
    return (avlNode.left != null ? avlNode.left.height : 0) -
            (avlNode.right != null ? avlNode.right.height : 0);
}

三、插入结点和删除结点

1、插入结点

AVL树插入结点的步骤与传统二叉搜索树一致，只不过在返回之前会调整平衡，具体代码如下：

private AVLNode insert(AVLNode newNode, AVLNode root) {
    if (root == null) {
        // 找到了正确的位置，直接返回新节点
        return newNode;
    }
    if (root.key > newNode.key) {
        // 新节点的key比当前节点的小，因此向当前节点的左子树递归
        root.left = insert(newNode, root.left);
    } else if (root.key < newNode.key) {
        // 新节点的key比当前节点的大，因此向当前节点的右子树递归
        root.right = insert(newNode, root.right);
    } else {
        // 两个节点的key相同，因此直接更新value并返回
        root.value = newNode.value;
        return root;
    }
    resetHeight(root); // 在调整之前，更新当前节点的高度
    return reBalance(root); // 调整并返回
}

方法参数中的newNode为待插入的新结点，root为原AVL树的根结点。

插入结点12：

 图3.1.1

 

 图3.1.2

图3.1.3

2、删除结点

AVL树删除结点涉及到的情况较为复杂，以下是实现代码：

private AVLNode delete(int key, AVLNode avlNode) {
    if (avlNode == null) { // 待删除的结点不存在
        return null;
    }
    if (avlNode.key > key) {
        // 对avlNode的左子树递归调用方法
        avlNode.left = delete(key, avlNode.left);
    } else if (avlNode.key < key) {
        // 对avlNode的右子树递归调用方法
        avlNode.right = delete(key, avlNode.right);
    } else {
        if (avlNode.left == null && avlNode.right == null) { // 待删除的结点没有左右子树
            // 返回空表示删除当前结点（avlNode）
            return null;
        } else if (avlNode.right == null) { // 待删除的结点只有左子树
            // 保存avlNode的左子树
            AVLNode left = avlNode.left;

            // 清空avlNode的左指针
            avlNode.left = null;

            // 用avlNode的左子树接替avlNode
            return left;
        } else if (avlNode.left == null) { // 待删除的结点只有右子树
            // 保存avlNode的右子树
            AVLNode right = avlNode.right;

            // 清空avlNode的右指针
            avlNode.right = null;

            // 用avlNode的右子树接替avlNode
            return right;
        } else { // 待删除的结点有左右子树
            // 获取左子树的最右结点
            AVLNode mostRightNodeOfLeftTree = getMostRightNode(avlNode.left);

            // 删除待删除结点的左子树的最右结点，由于此时最右结点没有右子树，因此只涉及两种返回情况：
            // 1、只有左子树
            // 2、没有左右子树
            // 由于可能会发生旋转，因此newRoot不一定等于avlNode
            AVLNode newRoot = delete(mostRightNodeOfLeftTree.key, avlNode);

            // 将avlNode的数据更新为左子树的最右结点的数据，此时avlNode的高度已在上一步更新
            avlNode.key = mostRightNodeOfLeftTree.key;
            avlNode.value = mostRightNodeOfLeftTree.value;

            // 返回调整之后的以原待删除结点为根结点的AVL树的根结点
            return newRoot;
        }
    }
    resetHeight(avlNode); // 在调整之前，更新当前结点的高度
    return reBalance(avlNode); // 调整并返回
}

方法参数中的key为待删除结点的key，avlNode为原AVL树的根结点。需要注意的是，当待删除的结点有左右子树时，用数据转移来代替指针动作，具体过程为：先删除待删除结点的左子树的最右结点，再将待删除结点的数据更新为其左子树的最右结点的数据（在这里是key和value），即达到了删除结点的效果，而此过程没有移动指针（除了平衡调整）。

例子1，删除结点40：

图3.2.1

图3.2.2

以上是不涉及平衡调整的例子，下面来看一个涉及RR旋转的例子。

例子二，删除结点34：

 图3.2.3

 图3.2.4

  图3.2.5

注意，以上步骤只是逻辑顺序，在实际编写代码时，应先删除结点33并调整平衡，再将已被删除的结点33的数据转移给结点34，如果先转移数据，会造成死循环。

接着来看一个涉及RL旋转的例子。

例子三，删除结点76：

图3.2.6

 图3.2.7

 图3.2.8

再来看一个涉及多次旋转的例子。

例子四，删除结点94：

 图3.2.9

 图3.2.10

 图3.2.11

 图3.2.12

四、完整代码

1、AVL树结点

public class AVLNode {
    public int key; // 结点的键，用于标识结点在AVL树中的位置
    public Object value; // 结点的值，用于存储数据
    public int height; // 结点的高度
    public AVLNode left; // 结点的左指针
    public AVLNode right; // 结点的右指针

    public AVLNode(int key, Object value) {
        this.key = key;
        this.value = value;
        height = 1;
    }
}

2、AVL树相关方法

public class AVLTree {
    private AVLNode root;
    private final StringBuilder visualizeBuilder; // 二叉树图形化解析的builder

    public AVLTree() {
        visualizeBuilder = new StringBuilder();
    }

    
    private AVLNode reBalance(AVLNode avlNode) {
        // 获取avlNode的平衡因子
        int altitudeDiff = getAltitudeDiff(avlNode);

        if (Math.abs(altitudeDiff) > 1) {
            if (altitudeDiff < 0) { // LL旋转或者RL旋转
                // avlNode的右子树的平衡因子只可能为-1|0|1
                if (getAltitudeDiff(avlNode.right) == 1) {
                    // avlNode的右子树右旋
                    avlNode.right = rightRevolve(avlNode.right);
                }
                // avlNode左旋
                return leftRevolve(avlNode);
            } else { // RR旋转或者LR旋转
                // avlNode的左子树的平衡因子只可能为-1|0|1
                if (getAltitudeDiff(avlNode.left) == -1) {
                    // avlNode的左子树左旋
                    avlNode.left = leftRevolve(avlNode.left);
                }
                // avlNode右旋
                return rightRevolve(avlNode);
            }
        }
        return avlNode;
    }

    
    private AVLNode leftRevolve(AVLNode avlNode) {
        // 先保存avlNode的右子树
        AVLNode right = avlNode.right;

        // avlNode的右指针指向right的左子树
        avlNode.right = right.left;

        // right的左指针指向avlNode
        right.left = avlNode;

        // 先更新avlNode的高度
        resetHeight(avlNode);

        // 再更新right的高度
        resetHeight(right);

        // 返回right作为调整后的root
        return right;
    }

    
    private AVLNode rightRevolve(AVLNode avlNode) {
        // 保存avlNode的左子树
        AVLNode left = avlNode.left;

        // avlNode的左指针指向left的右子树
        avlNode.left = left.right;

        // left的右指针指向avlNode
        left.right = avlNode;

        // 先更新avlNode的高度
        resetHeight(avlNode);

        // 再更新left的高度
        resetHeight(left);

        // 返回left作为调整后的root
        return left;
    }

    
    private int getAltitudeDiff(AVLNode avlNode) {
        return (avlNode.left != null ? avlNode.left.height : 0) -
                (avlNode.right != null ? avlNode.right.height : 0);
    }

    
    public void insert(AVLNode newNode) {
        root = insert(newNode, root);
    }

    private AVLNode insert(AVLNode newNode, AVLNode root) {
        if (root == null) {
            // 找到了正确的位置，直接返回新结点
            return newNode;
        }
        if (root.key > newNode.key) {
            // 新结点的key比当前结点的小，因此向当前结点的左子树递归
            root.left = insert(newNode, root.left);
        } else if (root.key < newNode.key) {
            // 新结点的key比当前结点的大，因此向当前结点的右子树递归
            root.right = insert(newNode, root.right);
        } else {
            // 两个结点的key相同，因此直接更新value并返回
            root.value = newNode.value;
            return root;
        }
        resetHeight(root); // 在调整之前，更新当前结点的高度
        return reBalance(root); // 调整并返回
    }

    
    public boolean delete(int key) {
        if (root == null) {
            return false;
        }

        // delete方法返回null的情况：待删除的是唯一一个结点
        AVLNode delete = delete(key, root);

        // 待删除的结点存在
        if (delete != null || root.left == null && root.right == null && key == root.key) {
            root = delete;
            return true;
        }

        // 待删除的结点不存在
        return false;
    }

    private AVLNode delete(int key, AVLNode avlNode) {
        if (avlNode == null) { // 待删除的结点不存在
            return null;
        }
        if (avlNode.key > key) {
            // 对avlNode的左子树递归调用方法
            avlNode.left = delete(key, avlNode.left);
        } else if (avlNode.key < key) {
            // 对avlNode的右子树递归调用方法
            avlNode.right = delete(key, avlNode.right);
        } else {
            if (avlNode.left == null && avlNode.right == null) { // 待删除的结点没有左右子树
                // 返回空表示删除当前结点（avlNode）
                return null;
            } else if (avlNode.right == null) { // 待删除的结点只有左子树
                // 保存avlNode的左子树
                AVLNode left = avlNode.left;

                // 清空avlNode的左指针
                avlNode.left = null;

                // 用avlNode的左子树接替avlNode
                return left;
            } else if (avlNode.left == null) { // 待删除的结点只有右子树
                // 保存avlNode的右子树
                AVLNode right = avlNode.right;

                // 清空avlNode的右指针
                avlNode.right = null;

                // 用avlNode的右子树接替avlNode
                return right;
            } else { // 待删除的结点有左右子树
                // 获取左子树的最右结点
                AVLNode mostRightNodeOfLeftTree = getMostRightNode(avlNode.left);

                // 删除待删除结点的左子树的最右结点，由于此时最右结点没有右子树，因此只涉及两种返回情况：
                // 1、只有左子树
                // 2、没有左右子树
                // 由于可能会发生旋转，因此newRoot不一定等于avlNode
                AVLNode newRoot = delete(mostRightNodeOfLeftTree.key, avlNode);

                // 将avlNode的数据更新为左子树的最右结点的数据，此时avlNode的高度已在上一步更新
                avlNode.key = mostRightNodeOfLeftTree.key;
                avlNode.value = mostRightNodeOfLeftTree.value;

                // 返回调整之后的以原待删除结点为根结点的AVL树的根结点
                return newRoot;
            }
        }
        resetHeight(avlNode); // 在调整之前，更新当前结点的高度
        return reBalance(avlNode); // 调整并返回
    }

    
    private void resetHeight(AVLNode avlNode) {
        avlNode.height = Math.max(
                avlNode.left == null ? 0 : avlNode.left.height,
                avlNode.right == null ? 0 : avlNode.right.height
        ) + 1;
    }

    
    private AVLNode getMostRightNode(AVLNode avlNode) {
        return avlNode.right == null ? avlNode : getMostRightNode(avlNode.right);
    }

    
    public boolean checkBalance() {
        if (root != null) {
            if (Math.abs(getAltitudeDiff(root)) > 1) {
                return false;
            }
            return checkBalance(root.left) && checkBalance(root.right);
        }
        return true;
    }

    private boolean checkBalance(AVLNode root) {
        if (root != null) {
            if (Math.abs(getAltitudeDiff(root)) > 1) {
                return false;
            }
            return checkBalance(root.left) && checkBalance(root.right);
        }
        return true;
    }

    
    public String getVisualizeString() {
        visualizeBuilder.setLength(0);
        setVisualizeBuilder(root, visualizeBuilder);
        return visualizeBuilder.toString();
    }

    private void setVisualizeBuilder(AVLNode avlNode, StringBuilder builder) {
        if (avlNode == null) {
            builder.append("[null]");
            return;
        }
        builder.append("[").append(avlNode.key).append("-").append(avlNode.height);
        setVisualizeBuilder(avlNode.left, builder);
        setVisualizeBuilder(avlNode.right, builder);
        builder.append("]");
    }

    
    public int countNodes() {
        return countNodes(root);
    }

    private int countNodes(AVLNode avlNode) {
        if (avlNode == null) {
            return 0;
        }
        return 1 + countNodes(avlNode.left) + countNodes(avlNode.right);
    }

    
    public Object get(int key) {
        return get(key, root);
    }

    private Object get(int key, AVLNode root) {
        if (root == null) {
            return null;
        }
        if (root.key < key) {
            return get(key, root.right);
        }
        if (root.key > key) {
            return get(key, root.left);
        }
        return root.value;
    }
}

3、测试方法

public class ATest {
    public static void main(String[] args) {
        HashSet keySet = new HashSet<>();
        for (int i = 0; i < 100; ++i) {
            keySet.add(getRandomKey());
        }
        AVLTree avlTree = new AVLTree(); // add
        Integer[] keyArray = new Integer[keySet.size()];
        keyArray = keySet.toArray(keyArray);
        List keyList = Arrays.asList(keyArray);
        System.out.println("keyArray总长度：" + keyArray.length);
        System.out.println("~~~~~~~~~~~~~~开始插入节点：");
        for (Object integer : keyArray) {
            System.out.println("-----------当前节点总数：" + avlTree.countNodes());
            System.out.println("-----------本次将插入节点：" + integer);
            avlTree.insert(new AVLNode((Integer) integer, null));
            System.out.println("-----------插入后AVL树字符串描述：");
            System.out.println(avlTree.getVisualizeString());
            System.out.println();
        }

        System.out.println(avlTree.getVisualizeString());
        System.out.println("~~~~~~~~~~~~~~开始删除节点：");
        while (true) {
            int index = (int) (Math.random() * keyList.size());
            Integer key = keyArray[index];
            if (key != -1) {
                System.out.println("-----------当前节点总数：" + avlTree.countNodes());
                System.out.println("-----------本次将删除节点：" + key);
                if (!avlTree.delete(key)) {
                    break;
                }
                System.out.println("-----------删除结果：" + avlTree.checkBalance());
                System.out.println("-----------删除后AVL树字符串描述：");
                System.out.println(avlTree.getVisualizeString());
                System.out.println();
                keyArray[index] = -1;
            }
            boolean b = Arrays.stream(keyArray).allMatch(temp -> {
                return temp == -1;
            });
            if (b) {
                break;
            }
        }
    }

    public static Integer getRandomKey() {
        return (int) (Math.random() * 100);
    }
}

以上所有图示由此网站生成：http://mshang.ca/syntree，可以将指定格式的字符串解析为N叉树图形，非常实用，强烈推荐！