• 0

  • 0

用java写一棵AVL树吧

1星期前

什么是AVL树

什么是二叉搜索树

  二分搜索法可以算是基础算法中应用最广的算法之一, 对于有序的数列, 二分法能够将时间复杂度从O(n)优化到O(logn), 能够大幅度提高程序运行速度。
  采用二分搜索的思想, 我们可以构建一棵二叉搜索树, 让这颗树的每个结点大于它的左子节点而小于它的右子结点。像这样:

  在这种理想情况下, 整个树比较均匀, 每次操作的理想时间复杂度都是O(logN)。

什么是平衡树

  在现实中我们要考虑极端情况。 比如同一组数据可能生成这样一棵树:

  这种情况的确少见, 然而一旦出现结果是致命的。而且,在一般情况下, 二叉树不平衡的概率还不小, 而一旦不平衡操作的效率就会下降。 比如在这种极端情况下, 整个二叉树就退化成了链表, 二分搜索也退化成了线性搜索。
  为了解决这个问题, 人们设计出了许多平衡树。 平衡树每次操作后都会维持自身的平衡, 能够维持二分搜索的高效性。   

什么是AVL树

  在所有平衡树中, 最基础的一种就是AVL树, 所以从AVL树开始学习平衡树是个不错的选择。

树和结点的定义

  定义一个节点还是很简单的, 这里我将节点设计成树内部类, 然后用了点泛型的知识。

public class AVLTree<T extends Comparable<? super T>>
    class Node {
        int height;
        Node left;
        Node right;
        T key;
        Node (T key, Node l, Node r, int h) {
            left = l;
            right = r;
            this.key = key;
            height = h;
        }
    }
}
复制代码

  这里要做一些说明, left和right很明显就是左右子树, 然后key就是关键字, 用来比较大小。因为这是最简单的AVL树, 所以并没有与key相对应的value, 不过原理都是一样的。
  然后是height, 对于高度的定义, 不同的资料都有所不同。我在这里将叶子节点的高度定义为0, null的高度定义为-1, 其他节点的高度定义为 max{left.height, right.height} 在这个基础上我给出平衡的定义:

∀ p ( p ∈ t r e e ∧ p ≠ n u l l ) → ( ∣ p . l e f t . h e i g h t − p . r i g h t . h e i g h t ∣ ≤ 1 ) \forall p (p \in tree \wedge p \ne null) \rightarrow (|p.left.height - p.right.height| \le 1)

  这个定义的理由是明确的, 如果左右子树的高度完全一致, 那么就不能增加结点, 也不能删除结点了(对于单个结点来说, 修改了就不平衡了), 而维持高度差小于等于1可以完成各项操作, 并且整个树能保持良好的平衡效果。
  为了消除获取高度时的null判断, 定义一个辅助方法

private int getHeight(Node p) {
        if (p == null)
            return -1;
        else
            return p.height;
}
复制代码

  在这个基础上定义判断平衡的函数(p不为null)

private boolean isBalance(Node p) {
    return Math.abs(getHeight(p.left) - getHeight(p.right)) <= 1;
}
复制代码

  现在分别考虑增加和删除操作。

如何增加节点

  考虑增加节点前后的的状态, 由于这是一棵平衡树, 这棵树必须在每一个时刻保持平衡。这棵树的初始状态是空树, 根据定义, 空树是一棵平衡树。 现在要做的工作就是像数学归纳法一样, 确保向一棵平衡树增加节点后, 这棵树仍然是平衡树。
  现在先定义插入的方法:

private Node insert(Node p, T key) {}
复制代码

  现在说明这个方法的行为, 对于某个结点p(p可以为空), 插入值为key的结点(key 不能为 null)

  1. 如果key已经存在于p树中, 这个方法不会改变p树的结构。
  2. 如果这个key不存在, 将新节点插入以p树中。
  3. 维持p树的平衡, 返回平衡后的p树根(平衡后树根可能改变, 后面有详细操作)。
  4. 将p树的高度更新。
      现在要用到一点递归的思想, 我们向当前结点的操作可以是这样(这里直接以p作为返回值来修改):
if (p == null) {
    p = new Node(key, null, null, 0);
} else {
    int cmp = key.CompareTo(p.key);
}
复制代码

  在这里定义了一个变量cmp来表示大小关系, 如果cmp等于0, 那么这个这个key已经存在, 就不用插入了。我们重点要处理的是cmp不等于0的状态, 忽略平衡操作可以这么写:

    if (cmp < 0)
        p.left = insert(p.left, key);
    else if (cmp > 0)
        p.right = insert(p.right, key);
    if (!isBalance(p))
        p = keepBalance(p);
    p.height = Math.max(p.left.height, p.right.height);

复制代码

  那么如何保持平衡呢?

如何保持平衡

明确保持平衡的定义

  这个操作的初始状态是左右子树都平衡, 但是p树不平衡(左右子树高度相差2), 结束状态是左右子树都平衡, p树也平衡, 所以这个维持平衡的操作在删除结点时也能用到。

LL旋转

  在左子树的高度高于右子树的况下, 只有向左子树中添加节点才可能使整个树不平衡(一个节点最多只能让树的高度+1), 现在考虑向a的左子树, 也就是b添加节点(根据方法定义, 添加后b仍然是平衡树), 然后当b的高度+1, 以a为根的树就不平衡了。

  很明显,这种情况下b一定不为null, 现在分析b子树情况, 第一种:

  这种情况左子树高度确定了, 右子树h2的取值只可能是, h0, h0 + 1, 然后我们用一种巧妙的变换方法(不要问我这东西是怎么想出来的), 称为LL旋转, 将整个树调整成这样:

  这时我们分析高度情况:

已知 h e = h 0 或 h 0 + 1 , h c = h 0 , h d = h 0 + 1 对于 a 的两棵子树 ∣ h e − h c ∣ ≤ 1 ,所以 a 平衡 对于 a 来说 h a = m a x ( h e , h c ) = h 0 + 1 或 h 0 + 2 对于 b 的两棵子树同样有 ∣ h d − h a ∣ ≤ 1 , 所以 b 平衡 \begin{aligned} &已知h_e = h_0 或 h_0 + 1, h_c = h_0, h_d = h_0 + 1 \\ &对于a的两棵子树 |h_e - h_c| \le 1 , 所以a平衡\\ &对于a来说h_a = max(h_e, h_c) = h_0 + 1 或 h_0 + 2 \\ &对于b的两棵子树同样有 |h_d - h_a| \le 1 , 所以 b平衡\\ \end{aligned}

  现在整颗子树已经重新平衡了, 最重要的是中序遍历并没有改变, exciting!。
   我们可以将这个方法用java写出来:

//p != null && p.left != null 进行旋转操作, 返回新的根, 同时修改高度
private Node rotateLL(Node p) {
    Node p1 = p.left;
    p.left = p1.right;
    p1.right = p;

    p.height = Math.max(getHeight(p.left), getHeight(p.right)) + 1;
    p1.height = Math.max(getHeight(p1.left), getHeight(p1.right)) + 1;
    return p1;
}
复制代码

  并且类似的可以写出RR的方法:

private Node rotateRR(Node p) {
    Node p1 = p.right;
    p.right = p1.left;
    p1.left = p;

    p.height = Math.max(getHeight(p.left), getHeight(p.right)) + 1;
    p1.height = Math.max(getHeight(p1.left), getHeight(p1.right)) + 1;
    return p1;
}
复制代码

  上面两种方法调用时都是符合条件的, 比如对于LL操作, 调用时b显然不为null(比c高)
  接着分析另一种情况;

LR旋转


  现在讨论的情况是h1与h0+1不相等, 也就是h1 = h0, 在维持中序遍历不变的情况下, 我们同样可以做出一个巧妙的调整, 这里先给出结论然后证明。 我们只需要先对b结点做RR变换(这时b结点同样显然不为null, e比d高也不是null), 然后对a结点做LL变换, 结果图如下(设e的左右子结点为el, er):
  对b做RR旋转:

  然后对a做LL旋转:
  现在分析平衡情况:

现在已知 h d = h 0 , h e = h 0 + 1 , h c = h 0 ; 先分析 b 由于以 e 为根的子树是平衡树,所以 h e l , h e r = h 0 或 h 0 − 1 ; 所以 ∣ h d − h e l ∣ ≤ 1 , 所以 b 平衡且 h b = h 0 + 1 ; 再分析 a 同样的 ∣ h c − h e r ∣ ≤ 1 , 所以 a 平衡,且 h a = h 0 + 1 ; 于是 h a = h b ; 所以 e 平衡。 \begin{aligned} &现在已知 h_d = h_0, h_e = h_0 + 1, h_c = h_0;\\ &先分析b\\ &由于以e为根的子树是平衡树, 所以 h_{el}, h_{er} = h_0 或 h_0 - 1;\\ &所以 |h_d - h_{el}| \le 1, 所以 b平衡 且 h_b = h_0 + 1;\\ &再分析a \\ &同样的 |h_c - h_{er}| \le 1, 所以 a平衡, 且 h_a = h_0 + 1;\\ &于是 h_a = h_b; 所以e平衡。 \end{aligned}

  至于中序遍历, 很容易验证并没有变化, 至此向左边插入时两种情况讨论完毕, 由于对称性, 向右边插入结点完全对称, 我们可以将维持平衡的方法写出来了:
  首先是LR:

private Node rotateLR(Node p) {
    p.left = rotateRR(p.left);
    return rotateLL(p);
}
&emsp;&emsp;然后是保持平衡:
复制代码
//当p不平衡时且左右子树高度相差2时可以调用, 返回新的根, 同时更新高度
private Node keepBalance(Node p) {
    int dh = getHeight(p.left) - getHeight(p.right);
    if (dh > 0) {
        if (getHeight(p.left) == getHeight(p.left.left) + 1)
            p = rotateLL(p);
        else
            p = rotateLR(p);
    } else {
        if (getHeight(p.right) == getHeight(p.right.right) + 1)
            p = rotateRR(p);
        else
            p = rotateRL(p);
    }
    return p;
}
复制代码

  完整插入方法如下:

private Node insert(Node p, T key) {
    if (p == null) {
        p = new Node(key, null, null, 0);
    } else {
        int cmp = key.compareTo(p.key);
        if (cmp < 0)
            p.left = insert(p.left, key);
        else if (cmp > 0)
            p.right = insert(p.right, key);
        if (!isBalance(p))
            p = keepBalance(p);
        p.height = Math.max(getHeight(p.left), getHeight(p.right)) + 1;
    }
    return p;
}
复制代码

插入最多高度加一

  之前说明了保持平衡方法的调用条件, 现在来证明:

对于空树来说 , 插入结点后高度从 − 1 变成 0 ,高度 + 1 对于任意一棵非空的树,如果向两棵子树插入结点,子树高度最多 + 1 这时候如果没有调用平衡方法, p 树的高度最多 + 1 , 如果调用平衡方法(当然符合条件), 根据上面分析, p 树高度最多 + 1 而且通过这种左右子树构造方法,可以构造出任何一棵 A V L 树,所以命题成立 \begin{aligned} &对于空树来说, 插入结点后高度从-1变成0, 高度+1\\ &对于任意一棵非空的树, 如果向两棵子树插入结点, 子树高度最多+1 \\ &这时候如果没有调用平衡方法, p树的高度最多+1,\\ &如果调用平衡方法(当然符合条件),\\ &根据上面分析,p树高度最多+1\\ &而且通过这种左右子树构造方法, 可以构造出任何一棵AVL树, 所以命题成立 \end{aligned}

删除

  删除是插入的反向操作, 原理其实差不多, 我们同样用递归来实现, 先定义这个方法的行为:

private Node delete(Node p, T key){}
复制代码
  1. 在以p为根的子树中删除值为key的结点, 返回新的根节点。
  2. p可以为空, key不能为空
  3. 更新子树的高度, 并使子树保持平衡。

  先将简单的部分实现:

if (p != null) {
        int cmp = key.compareTo(p.key);
        if (cmp != 0) {
            if (cmp < 0)
                p.left = delete(p.left, key);
            else if (cmp > 0)
                p.right = delete(p.right, key); 
            if (!isBalance(p))
                p = keepBalance(p);
        }
}
复制代码

  然后就是考虑删除的结点就是当前结点, 在这种情况下, 如果左右子树有一个为空或者两者都为空, 那么很容易处理, 像链表一样删除就行, 同时整个树的高度减一。
  在两个子树都不为空的情况下, 如果左子树的高度更高, 从左子树中选最大的结点来替换当前结点, 否则从右子树中选择最小结点来替换当前结点。操作顺序是先删除找到的结点, 然后替换p结点的值, 而且操作完毕后整颗树还是平衡的, 证明如下:

  证明:将某个结点从树删除,树的高度最多减少 1 当这棵树为空树时显然成立(高度不变),现在假设对某棵树的左右子树成立, 考虑四种情况 1. 从左子树删除,显然 p 树的高度最多减少 1 2. 从右子树删除,显然 p 树的高度最多减少 1 3. 删除当前结点,但是当前结点至少有一个子树为空,显然 p 树高度减 1 4. 删除当前结点,且左右子树都不为空 当左子树更高时,从左子树中删除最大结点,左子树最多高度减 1 如果左子树高度减 1 , p 树的高度减 1 当左子树不比右子树高时,删除右子树的最小结点 右子树的高度最多减 1 ,所以 p 树的高度最多减 1   综上命题成立,同时可以看到删除操作的正确性 \begin{aligned} &\ \ 证明:将某个结点从树删除, 树的高度最多减少1\\ &当这棵树为空树时显然成立(高度不变), 现在假设对某棵树的左右子树成立,\\ &考虑四种情况\\ &1.从左子树删除, 显然p树的高度最多减少1\\ &2.从右子树删除, 显然p树的高度最多减少1\\ &3.删除当前结点, 但是当前结点至少有一个子树为空, 显然p树高度减1\\ &4.删除当前结点, 且左右子树都不为空\\ &当左子树更高时, 从左子树中删除最大结点, 左子树最多高度减1\\ &如果左子树高度减1, p树的高度减1 \\ &当左子树不比右子树高时, 删除右子树的最小结点\\ &右子树的高度最多减1, 所以p树的高度最多减1 \\ &\ \ 综上命题成立, 同时可以看到删除操作的正确性 \end{aligned}

  现在将删除操作用代码写出来, 首先是查找最大最小值方法:

private T findMin(Node p) { //p should not be null
    T ret = p.key;
    if (p.left != null)
        ret = findMin(p.left);
    return ret;
}

private T findMax(Node p) { // p should not be null
    T ret = p.key;
    if (p.right != null)
        ret = findMax(p.right);
    return ret;
} 
复制代码

  在这个基础上可以很容易写出删除操作:

private Node delete(Node p, T key) {
    if (p != null) {
        int cmp = key.compareTo(p.key);
        if (cmp != 0) {
            if (cmp < 0)
                p.left = delete(p.left, key);
            else
                p.right = delete(p.right, key);
            if (!isBalance(p))
                p = keepBalance(p);
        }
        else {
            if (p.left == null && p.right == null)
                p = null;
            else if (p.right == null) {
                p = p.left;
            } else if (p.left == null) {
                p = p.right;
            } else {
                if (getHeight(p.left) > getHeight(p.right)) {
                    T maxKey = findMax(p.left);
                    p.left = delete(p.left, maxKey);
                    p.key = maxKey;
                } else {
                    T minKey = findMin(p.right);
                    p.right = delete(p.right, minKey);
                    p.key = minKey;
                }
            }
            if (p != null)
                p.height = Math.max(getHeight(p.left), getHeight(p.right)) + 1;
        }
    }
    return p;
}
复制代码

剩下的操作

  剩下的无非就是查找和遍历, 这两种操作不涉及元素的修改, 因此和普通的二叉查找树方法是通用的, 实现如下:

@Override
public String toString() {
    builder.delete(0, builder.length());//使用了StringBuilder
    walk(root);
    return builder.toString();
}

private void walk(Node p) { // p can be null.
    if (p != null) {
        walk(p.left);
        builder.append(p.key).append(' ');
        walk(p.right);
    }
}

private boolean contain(Node p, T key) { // p can be null, but key should not be null
    boolean ret = false;
    if (p != null) {
        int cmp = key.compareTo(p.key);
        if (cmp < 0) {
            ret = contain(p.left, key);
        } else if (cmp > 0) {
            ret = contain(p.right, key);
        } else {
            ret = true;
        }
    }
    return ret;
}
复制代码

封装

  最后一步就是给之前的递归方法套个壳, 使外部只能对根操作:

public void add(T key) {
    root = insert(root, key);
}

public void remove(T key) {
    root = delete(root, key);
}

public boolean contain(T key) {
    return contain(root, key);
}
复制代码

总结

  比较详细地写出了AVL的保持平衡方法, 并在此基础上实现了插入删除元素操作, 进而完成整颗AVL树。在图和代码兼备的情况下, 加了少许证明, 让文章严谨了许多。 当然不足的地方也不少, 发现了一定改正。

免责声明:文章版权归原作者所有,其内容与观点不代表Unitimes立场,亦不构成任何投资意见或建议。

java

0

相关文章推荐

未登录头像

暂无评论