AVL树的Java实现

Java基础

浏览数:202

2019-5-11

定义

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型

  • LR型

  • RR型

  • RL型

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

调整方法

  • LL型

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

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

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

  • LR型

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

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

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

  • RR型

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

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

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

  • RL型

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

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

插入节点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) 如果节点的左右子树均为非空子树，则使用节点的左右子树中更高的那棵子树中的最大/最小节点来填补空缺（如果子树高度一致则哪边都可以）

例子：

  1. 假设待删除节点为节点9，则应当使用左子树中的最大值节点8来填补空缺
  2. 假设待删除节点为节点13，则应当使用右子树中的最小值节点14来填补空缺
  3. 假设待删除节点为节点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<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树的增删查三种操作，全部基于递归的算法模式，考虑到在树足够大时递归的效率问题，本人尝试进行了一些尾递归优化，希望这能使操作效率更高一些

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

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

作者：ShinobuChyan

原文地址：https://segmentfault.com/a/1190000019101902

FavoriteLoading收藏
喜欢 0

相关推荐

© 2012-2019 jqhtml.com · 湘ICP备16001111号-1