AVL树的Java实现

leejan97 发布于2019-08-16 17:13 / 516人阅读

摘要：容忍不平衡红黑树的思路的核心是增大了可容忍的高度差，从而实现既保证查询效率，也保证了插入和删除后调整平衡的效率。红黑树的查询效率是略低于树的，但是红黑树通过牺牲了少许查询效率，使插入删除后的调整效率达到了常数级别。

定义

Wikipedia - AVL树

在计算机科学中，AVL树是最早被发明的自平衡二叉查找树。在AVL树中，任一节点对应的两棵子树的最大高度差为1，因此它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下的时间复杂度都是 {displaystyle O(log {n})} O(log{n})。增加和删除元素的操作则可能需要借由一次或多次树旋转，以实现树的重新平衡。AVL树得名于它的发明者G. M. Adelson-Velsky和Evgenii Landis，他们在1962年的论文《An algorithm for the organization of information》中公开了这一数据结构。

理论

实现AVL树的要点为：每次新增/删除节点后判断平衡性然后通过调整使整棵树重新平衡

判断平衡性：每次新增/删除节点后，刷新受到影响的节点的高度，即可通过任一节点的左右子树高度差判断其平衡性

调整：通过对部分节点的父子关系的改变使树重新平衡

实现 基本结构

public class Tree> {

    private static final int MAX_HEIGHT_DIFFERENCE = 1;

    private Node root;

    class Node {

        KT key;

        Node left;

        Node right;

        int height = 1;

        public Node(KT key, Node left, Node right) {
            this.key = key;
            this.left = left;
            this.right = right;
        }
    }
}

插入（insert） 四种不平衡范型

对于任意一次插入所造成的不平衡，都可以简化为下述四种范型之一：

下面四张图中的数字仅代表节点序号，为了后文方便展示调整过程
4、5、6、7号节点代表了四棵高度可以使不平衡成立的子树（遵循插入的规则）

LL型

LR型

RR型

RL型

总结得到判断范型的方法为：不平衡的节点（节点1）通往高度最大的子树的叶子节点时所途经的前两个节点（节点2、节点3）的方向

调整方法

LL型

5号节点作为1号节点的左孩子

1号节点作为2号节点的右孩子

例子（例子中的数字代表节点的值）：

插入节点5后造成节点9不平衡，其范型为LL型，按照固定步骤调整后全局重新达到平衡

LR型

6号节点作为2号节点的右孩子

7号节点作为1号节点的左孩子

2号节点作为3号节点的左孩子

1号节点作为3号节点的右孩子

例子（例子中的数字代表节点的值）：

插入节点8.5后造成节点9不平衡，其范型为LR型，按照固定步骤调整后全局重新达到平衡

RR型

5号节点作为1号节点的右孩子

1号节点作为2号节点的左孩子

例子（例子中的数字代表节点的值）：

插入节点10.5后造成节点7不平衡，其范型为RR型，按照固定步骤调整后全局重新达到平衡

RL型

7号节点作为2号节点的左孩子

6号节点作为1号节点的右孩子

2号节点作为3号节点的右孩子

1号节点作为3号节点的左孩子

例子（例子中的数字代表节点的值）：

插入节点7.5后造成节点7不平衡，其范型为RL型，按照固定步骤调整后全局重新达到平衡

代码实现

public void insert(T key) {
    if (key == null) {
        throw new NullPointerException();
    }
    root = insert(root, key);
}

private Node insert(Node node, T key) {
    if (node == null) {
        return new Node<>(key, null, null);
    }

    int cmp = key.compareTo(node.key);
    if (cmp == 0) {
        return node;
    }
    if (cmp < 0) {
        node.left = insert(node.left, key);
    } else {
        node.right = insert(node.right, key);
    }

    if (Math.abs(height(node.left) - height(node.right)) > MAX_HEIGHT_DIFFERENCE) {
        node = balance(node);
    }
    refreshHeight(node);
    return node;
}

private int height(Node node) {
    if (node == null) {
        return 0;
    }
    return node.height;
}

private void refreshHeight(Node node) {
    node.height = Math.max(height(node.left), height(node.right)) + 1;
}

/**
 * 此方法中的node, node1, node2分别代表上文范型中的1、2、3号节点
 */
private Node balance(Node node) {
    Node node1, node2;
    // ll
    if (height(node.left) > height(node.right) &&
            height(node.left.left) > height(node.left.right)) {
        node1 = node.left;
        node.left = node1.right;
        node1.right = node;

        refreshHeight(node);
        return node1;
    }
    // lr
    if (height(node.left) > height(node.right) &&
            height(node.left.right) > height(node.left.left)) {
        node1 = node.left;
        node2 = node.left.right;
        node.left = node2.right;
        node1.right = node2.left;
        node2.left = node1;
        node2.right = node;

        refreshHeight(node);
        refreshHeight(node1);
        return node2;
    }
    // rr
    if (height(node.right) > height(node.left) &&
            height(node.right.right) > height(node.right.left)) {
        node1 = node.right;
        node.right = node1.left;
        node1.left = node;

        refreshHeight(node);
        return node1;
    }
    // rl
    if (height(node.right) > height(node.left) &&
            height(node.right.left) > height(node.right.right)) {
        node1 = node.right;
        node2 = node.right.left;
        node.right = node2.left;
        node1.left = node2.right;
        node2.left = node;
        node2.right = node1;

        refreshHeight(node);
        refreshHeight(node1);
        return node2;
    }
    return node;
}

总结

由插入节点导致的局部不平衡均会符合上述四种范型之一，只需要按照固定的方式调整相关节点的父子关系即可使树恢复平衡

关于调整，很多博客或者书籍中将这种调整父子关系的过程称为旋转，这个就见仁见智了，个人觉得这种描述并不容易理解，故本文统一称为调整

删除（remove） 通常情况

对于删除节点这个操作来说，有两个要点：被删除节点的空缺应该如何填补以及删除后如何使树恢复平衡

被删除节点的空缺应该如何填补

如果被删除节点是叶子节点，则不需要填补空缺

而如果是枝干节点，则需要填补空缺，理想的情况是使用某个节点填补被删除节点的空缺后，整棵树仍然保持平衡
a) 如果节点的左右子树有一棵为空，则使用非空子树填补空缺
b) 如果节点的左右子树均为非空子树，则使用节点的左右子树中更高的那棵子树中的最大/最小节点来填补空缺（如果子树高度一致则哪边都可以）

例子：

假设待删除节点为节点9，则应当使用左子树中的最大值节点8来填补空缺

假设待删除节点为节点13，则应当使用右子树中的最小值节点14来填补空缺

假设待删除节点为节点2，则使用左子树中的最大值节点1.5或者右子树中的最小值节点2.5来填补空缺均可

按照上述方式来填补空缺，可以尽可能保证删除后整棵树仍然保持平衡

删除后如何使树恢复平衡

如图，叶子节点12为被删除节点，删除后不需要填补空缺，但是此时节点13产生了不平衡

不过节点13的不平衡满足上文所说的不平衡范型中的RR型，因此只需要对节点13做对应的调整即可，如图：

此时节点13所在的子树经过调整重新达到局部平衡

但是我们紧接着发现，节点11出现了不平衡，其左子树高度为4，右子树高度为2

如果此时按照插入情况下的不平衡范型判断方法去判断节点11的不平衡情况属于哪种范型，会发现无法满足四种范型的任一情况

特殊情况

由删除节点导致的不平衡，除了会出现插入中所说的四种范型之外，还会出现两种情况，如图：

整棵树初始状态为平衡状态，此时假设删除节点13或节点14，均会导致节点11产生不平衡（左子树高度3，右子树高度1）

但是如果仍然按照插入时的方法来判断不平衡，则会发现，节点4的左右子树高度一致，即在满足了L后，后续无法判断这种情况属于哪种范型

对于R方向也是一样

本文称它们为L型和R型

不过这两种情况的处理也很简单，实际上当出现这种情况时，使用LL型或LR型的调整方法均可以达到使树重新平衡的目的

如图：

两种调整方式均可使树重新平衡，对于R型也是一样，这里不再赘述

代码实现

public void remove(T key) {
    if (key == null) {
        throw new NullPointerException();
    }
    root = remove(root, key);
}

private Node remove(Node node, T key) {
    if (node == null) {
        return null;
    }

    int cmp = key.compareTo(node.key);
    if (cmp < 0) {
        node.left = remove(node.left, key);
    }
    if (cmp > 0){
        node.right = remove(node.right, key);
    }
    if (cmp == 0) {
        if (node.left == null || node.right == null) {
            return node.left == null ? node.right : node.left;
        }
        var successorKey = successorOf(node).key;
        node = remove(node, successorKey);
        node.key = successorKey;
    }

    if (Math.abs(height(node.left) - height(node.right)) > MAX_HEIGHT_DIFFERENCE) {
        node = balance(node);
    }
    refreshHeight(node);
    return node;
}

/**
 * 寻找被删除节点的继承者
 */
private Node successorOf(Node node) {
    if (node == null) {
        throw new NullPointerException();
    }
    if (node.left == null || node.right == null) {
        return node.left == null ? node.right : node.left;
    }

    return height(node.left) > height(node.right) ?
            findMax(node.left, node.left.right, node.left.right == null) :
            findMin(node.right, node.right.left, node.right.left == null);
}

private Node findMax(Node node, Node right, boolean rightIsNull) {
    if (rightIsNull) {
        return node;
    }
    return findMax((node = right), node.right, node.right == null);
}

private Node findMin(Node node, Node left, boolean leftIsNull) {
    if (leftIsNull) {
        return node;
    }
    return findMin((node = left), node.left, node.left == null);
}

其中用到的private Node balance(Node node)方法修改为：

private Node balance(Node node) {
    Node node1, node2;
    // ll & l
    if (height(node.left) > height(node.right) &&
            height(node.left.left) >= height(node.left.right)) {
        node1 = node.left;
        node.left = node1.right;
        node1.right = node;

        refreshHeight(node);
        return node1;
    }
    // lr
    if (height(node.left) > height(node.right) &&
            height(node.left.right) > height(node.left.left)) {
        node1 = node.left;
        node2 = node.left.right;
        node.left = node2.right;
        node1.right = node2.left;
        node2.left = node1;
        node2.right = node;

        refreshHeight(node);
        refreshHeight(node1);
        return node2;
    }
    // rr & r
    if (height(node.right) > height(node.left) &&
            height(node.right.right) >= height(node.right.left)) {
        node1 = node.right;
        node.right = node1.left;
        node1.left = node;

        refreshHeight(node);
        return node1;
    }
    // rl
    if (height(node.right) > height(node.left) &&
            height(node.right.left) > height(node.right.right)) {
        node1 = node.right;
        node2 = node.right.left;
        node.right = node2.left;
        node1.left = node2.right;
        node2.left = node;
        node2.right = node1;

        refreshHeight(node);
        refreshHeight(node1);
        return node2;
    }
    return node;
}

也就是将L型情况包含进了LL型，R型的情况包含进了RR型，因为这两种范式的调整要比对应的LR型/RL型的操作数少

总结

尽管删除节点时会出现特殊的情况，但是仍然可以通过简单的调整使树始终保持平衡

完整代码

/**
 * AVL-Tree
 *
 * @author Shinobu
 * @since 2019/5/7
 */
public class Tree> {

    private static final int MAX_HEIGHT_DIFFERENCE = 1;

    private Node root;

    class Node {

        KT key;

        Node left;

        Node right;

        int height = 1;

        public Node(KT key, Node left, Node right) {
            this.key = key;
            this.left = left;
            this.right = right;
        }
    }

    public Tree(T... keys) {
        if (keys == null || keys.length < 1) {
            throw new NullPointerException();
        }

        root = new Node<>(keys[0], null, null);
        for (int i = 1; i < keys.length && keys[i] != null; i++) {
            root = insert(root, keys[i]);
        }
    }

    public T find(T key) {
        if (key == null || root == null) {
            return null;
        }
        return find(root, key, key.compareTo(root.key));
    }

    private T find(Node node, T key, int cmp) {
        if (node == null) {
            return null;
        }

        if (cmp == 0) {
            return node.key;
        }

        return find(
                (node = cmp > 0 ? node.right : node.left),
                key,
                node == null ? 0 : key.compareTo(node.key));
    }

    public void insert(T key) {
        if (key == null) {
            throw new NullPointerException();
        }
        root = insert(root, key);
    }

    private Node insert(Node node, T key) {
        if (node == null) {
            return new Node<>(key, null, null);
        }

        int cmp = key.compareTo(node.key);
        if (cmp == 0) {
            return node;
        }
        if (cmp < 0) {
            node.left = insert(node.left, key);
        } else {
            node.right = insert(node.right, key);
        }

        if (Math.abs(height(node.left) - height(node.right)) > MAX_HEIGHT_DIFFERENCE) {
            node = balance(node);
        }
        refreshHeight(node);
        return node;
    }

    private int height(Node node) {
        if (node == null) {
            return 0;
        }
        return node.height;
    }

    private void refreshHeight(Node node) {
        node.height = Math.max(height(node.left), height(node.right)) + 1;
    }

    private Node balance(Node node) {
        Node node1, node2;
        // ll & l
        if (height(node.left) > height(node.right) &&
                height(node.left.left) >= height(node.left.right)) {
            node1 = node.left;
            node.left = node1.right;
            node1.right = node;

            refreshHeight(node);
            return node1;
        }
        // lr
        if (height(node.left) > height(node.right) &&
                height(node.left.right) > height(node.left.left)) {
            node1 = node.left;
            node2 = node.left.right;
            node.left = node2.right;
            node1.right = node2.left;
            node2.left = node1;
            node2.right = node;

            refreshHeight(node);
            refreshHeight(node1);
            return node2;
        }
        // rr & r
        if (height(node.right) > height(node.left) &&
                height(node.right.right) >= height(node.right.left)) {
            node1 = node.right;
            node.right = node1.left;
            node1.left = node;

            refreshHeight(node);
            return node1;
        }
        // rl
        if (height(node.right) > height(node.left) &&
                height(node.right.left) > height(node.right.right)) {
            node1 = node.right;
            node2 = node.right.left;
            node.right = node2.left;
            node1.left = node2.right;
            node2.left = node;
            node2.right = node1;

            refreshHeight(node);
            refreshHeight(node1);
            return node2;
        }
        return node;
    }

    public void remove(T key) {
        if (key == null) {
            throw new NullPointerException();
        }
        root = remove(root, key);
    }

    private Node remove(Node node, T key) {
        if (node == null) {
            return null;
        }

        int cmp = key.compareTo(node.key);
        if (cmp < 0) {
            node.left = remove(node.left, key);
        }
        if (cmp > 0){
            node.right = remove(node.right, key);
        }
        if (cmp == 0) {
            if (node.left == null || node.right == null) {
                return node.left == null ? node.right : node.left;
            }
            var successorKey = successorOf(node).key;
            node = remove(node, successorKey);
            node.key = successorKey;
        }

        if (Math.abs(height(node.left) - height(node.right)) > MAX_HEIGHT_DIFFERENCE) {
            node = balance(node);
        }
        refreshHeight(node);
        return node;
    }
    
    private Node successorOf(Node node) {
        if (node == null) {
            throw new NullPointerException();
        }
        if (node.left == null || node.right == null) {
            return node.left == null ? node.right : node.left;
        }

        return height(node.left) > height(node.right) ?
                findMax(node.left, node.left.right, node.left.right == null) :
                findMin(node.right, node.right.left, node.right.left == null);
    }

    private Node findMax(Node node, Node right, boolean rightIsNull) {
        if (rightIsNull) {
            return node;
        }
        return findMax((node = right), node.right, node.right == null);
    }

    private Node findMin(Node node, Node left, boolean leftIsNull) {
        if (leftIsNull) {
            return node;
        }
        return findMin((node = left), node.left, node.left == null);
    }

}

结语

AVL树的实现，在了解了不平衡的六种情况，以及对应的处理方式后，还是比较简单且逻辑清晰的

通过对AVL树的学习，可以发现它是一种“对不平衡非常敏感”的结构——可以容忍的高度差仅为1。这虽然可以让树尽可能的平衡，使查找效率尽可能高，但也付出了相应的代价：调整平衡。

它的插入元素引发的调整的最坏时间复杂度为O(1)，但是删除引发的最坏时间复杂度为O(logN)，这正是AVL树的弊端所在。

所以后来的2-3树、2-3-4树、红黑树都尝试对这种弊端进行了改进，改进的思路可以大概理解为两种：

使树完全平衡
这是2-3树和2-3-4树这两种结构尝试的方向。因为造成AVL树删除时“雪崩”的原因正是因为它所能容忍的这一点高度差，在高度差大量积累后，删除“薄弱”侧的节点，就会导致需要大量的调整才能恢复平衡。而如果完全消除高度差，就可以避免这种情况了。
然而实际的情况是这两种树的实现都算不上简单，而且反而使插入的调整行为的时间复杂度变为了O(logN)。

容忍不平衡
红黑树的思路的核心是增大了可容忍的高度差，从而实现既保证查询效率（O(logN)），也保证了插入和删除后调整平衡的效率（O(1)）。
红黑树的查询效率（2 * O(logN)）是略低于AVL树（O(logN)）的，但是红黑树通过牺牲了少许查询效率，使插入删除后的调整效率达到了常数级别。
红黑树算法中的着色策略、对于父节点、叔节点、祖父节点等等节点的颜色判断、以及相应的调整策略都是经过极度抽象后的结果，因此想要从头到尾彻底理解红黑树的设计思想其实还是有些难度的（理解设计思想并非照着抽象好的五条规则照本宣科）

以上，希望本文对读到的朋友能有所帮助

文章如果有谬误或疏漏，还请务必指正，感谢万分

GPU云服务器云服务器 java菜单树的实现 java二叉树的构建 java树的使用方法 AVL

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/74461.html

一文掌握关于Java数据结构所有知识点（欢迎一起完善）

摘要：是栈，它继承于。满二叉树除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树。没有键值相等的节点。这是数据库选用树的最主要原因。在我们学习Java的时候，很多人会面临我不知道继续学什么或者面试会问什么的尴尬情况（我本人之前就很迷茫）。所以，我决定通过这个开源平台来帮助一些有需要的人，通过下面的内容，你会掌握系统的Java学习以及面试的相关知识。本来是想通过Gitbook的...

keithxiaoy 2019-08-15 15:54 评论0 收藏0
Python数据结构——AVL树的基本概念

摘要：我们知道，当树变得不平衡时和操作会使二叉搜索树的性能降低到。树实现抽象数据类型就像一个普通的二叉搜索树，唯一不同的是这棵树的工作方式。我们通过比较每个节点的左右子树的高度完成比较。平衡二叉搜索树在上一节中我们讨论了建立一个二叉搜索树。我们知道，当树变得不平衡时get和put操作会使二叉搜索树的性能降低到O(n)。在这一节中我们将看到一种特殊的二叉搜索树，它可以自动进行调整，以确保树...

jiekechoo 2019-07-24 18:26 评论0 收藏0
学习JavaScript数据结构与算法 — AVL树

摘要：可以看到，一次左单旋将右侧子树的高度减小了，而左侧子树的高度增加了。如图，对进行右单旋，需要左子树的右子树的高度小于等于左子树的高度，否则不能达到平衡的效果，只是把不平衡性从左边转移到了右边。 AVL树普通二叉搜索树可能出现一条分支有多层，而其他分支却只有几层的情况，如图1所示，这会导致添加、移除和搜索树具有性能问题。因此提出了自平衡二叉树的概念，AVL树（阿德尔森-维尔斯和兰迪斯树...

impig33 2019-08-21 11:31 评论0 收藏0
树 - （二叉查找树，红黑树，B树）- 红黑树

摘要：需要执行的操作依次是首先，将红黑树当作一颗二叉查找树，将该节点从二叉查找树中删除然后，通过旋转和重新着色等一系列来修正该树，使之重新成为一棵红黑树。虽是读书笔记，但是如转载请注明出处 http://segmentfault.com/blog/exploring/ .. 拒绝伸手复制党关于二叉树的基本知识，可以参见：Java 实现基本数据结构 2(树) 以下是算法导论第13章的学...

yangrd 2019-08-14 12:05 评论0 收藏0
Python数据结构——AVL树的实现

摘要：一旦子树平衡因子为零，那么父节点的平衡因子不会发生改变。新根的父节点将成为旧根的父节点。因为其他操作都是移动整个子树，被移动的子树内的节点的平衡因子不受旋转的影响。让表示以为根节点的子树的高度。既然，我们已经证明，保持 AVL 树的平衡将会使性能得到很大的提升，那我们看看如何在程序中向树插入一个新的键值。因为所有的新键是作为叶节点插入树的，而新叶子的平衡因子为零，所以我们对新插入的节...

Pink 2019-07-31 12:22 评论0 收藏0