AVL树的Java实现

栏目: 数据库 · 发布时间: 7年前

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

定义

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<T extends Comparable<T>> {

    private static final int MAX_HEIGHT_DIFFERENCE = 1;

    private Node<T> root;

    class Node<KT> {

        KT key;

        Node<KT> left;

        Node<KT> right;

        int height = 1;

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

插入（insert）

四种不平衡范型

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

下面四张图中的数字仅代表节点序号，为了后文方便展示调整过程

4、5、6、7号节点代表了四棵高度可以使不平衡成立的子树（遵循插入的规则）

  • LL型

AVL树的 <a href='https://www.codercto.com/topics/22013.html'>Java</a> 实现

  • LR型

AVL树的Java实现

  • RR型

AVL树的Java实现

  • RL型

AVL树的Java实现

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

调整方法

  • LL型

AVL树的Java实现

  1. 5号节点 作为 1号节点 的左孩子
  2. 1号节点 作为 2号节点 的右孩子

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

AVL树的Java实现

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

  • LR型

AVL树的Java实现

  1. 6号节点 作为 2号节点 的右孩子
  2. 7号节点 作为 1号节点 的左孩子
  3. 2号节点 作为 3号节点 的左孩子
  4. 1号节点 作为 3号节点 的右孩子

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

AVL树的Java实现

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

  • RR型

AVL树的Java实现

  1. 5号节点 作为 1号节点 的右孩子
  2. 1号节点 作为 2号节点 的左孩子

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

AVL树的Java实现

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

  • RL型

AVL树的Java实现

  1. 7号节点 作为 2号节点 的左孩子
  2. 6号节点 作为 1号节点 的右孩子
  3. 2号节点 作为 3号节点 的右孩子
  4. 1号节点 作为 3号节点 的左孩子

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

AVL树的Java实现

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

代码实现 

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

private Node<T> insert(Node<T> 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<T> node) {
    if (node == null) {
        return 0;
    }
    return node.height;
}

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

/**
 * 此方法中的node, node1, node2分别代表上文范型中的1、2、3号节点
 */
private Node<T> balance(Node<T> node) {
    Node<T> 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）

通常情况

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

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

例子：

AVL树的Java实现

  1. 假设待删除节点为 节点9 ，则应当使用 左子树中的最大值 节点8 来填补空缺
  2. 假设待删除节点为 节点13 ，则应当使用 右子树中的最小值 节点14 来填补空缺
  3. 假设待删除节点为 节点2 ，则使用 左子树中的最大值 节点1.5 或者 右子树中的最小值 节点2.5 来填补空缺均可

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

  • 删除后如何使树恢复平衡

AVL树的Java实现

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

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

AVL树的Java实现

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

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

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

特殊情况

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

AVL树的Java实现

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

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

对于 R 方向也是一样

本文称它们为 L型 和 R型

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

如图：

AVL树的Java实现

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

代码实现 

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

private Node<T> remove(Node<T> 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<T> successorOf(Node<T> 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<T> findMax(Node<T> node, Node<T> right, boolean rightIsNull) {
    if (rightIsNull) {
        return node;
    }
    return findMax((node = right), node.right, node.right == null);
}

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

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

private Node<T> balance(Node<T> node) {
    Node<T> 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<T extends Comparable<T>> {

    private static final int MAX_HEIGHT_DIFFERENCE = 1;

    private Node<T> root;

    class Node<KT> {

        KT key;

        Node<KT> left;

        Node<KT> right;

        int height = 1;

        public Node(KT key, Node<KT> left, Node<KT> 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<T> 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<T> insert(Node<T> 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<T> node) {
        if (node == null) {
            return 0;
        }
        return node.height;
    }

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

    private Node<T> balance(Node<T> node) {
        Node<T> 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<T> remove(Node<T> 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<T> successorOf(Node<T> 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<T> findMax(Node<T> node, Node<T> right, boolean rightIsNull) {
        if (rightIsNull) {
            return node;
        }
        return findMax((node = right), node.right, node.right == null);
    }

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

}

结语

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

本文实现的AVL树的增删查三种操作，全部基于递归的算法模式，考虑到在树足够大时递归的效率问题，本人尝试进行了一些尾递归优化，希望这能使操作效率更高一些

后续

也许

会学习并尝试实现一下红黑树，然后对比一下二者的效率

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


以上所述就是小编给大家介绍的《AVL树的Java实现》，希望对大家有所帮助，如果大家有任何疑问请给我留言，小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持！

查看所有标签

本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。

码农书籍
Hit Refresh

Hit Refresh

Satya Nadella、Greg Shaw / HarperBusiness / 2017-9-26 / USD 20.37

Hit Refresh is about individual change, about the transformation happening inside of Microsoft and the technology that will soon impact all of our lives—the arrival of the most exciting and disruptive......一起来看看 《Hit Refresh》 这本书的介绍吧!

码农工具
JS 压缩/解压工具
JS 压缩/解压工具

在线压缩/解压 JS 代码

正则表达式在线测试
正则表达式在线测试

正则表达式在线测试

HEX HSV 转换工具
HEX HSV 转换工具

HEX HSV 互换工具

  • New
  • 文章
  • 话题
  • 教程
    • 关注 码农网 公众号
    版权所有，保留一切权利！© 2018-2026 码农网 粤ICP备17054400号-3