乐趣区

关于数据结构与算法:『数据结构与算法』AVL树平衡二叉树

jiezi

GitHub 源码分享

微信搜寻：码农 StayUp
主页地址：https://gozhuyinglong.github.io
源码分享：https://github.com/gozhuyinglong/blog-demos

1. AVL 树

AVL（Adelson-Velskii 和 Landis）树是带有平衡条件的二叉查找树，又叫做均衡二叉树。在 AVL 树中任何节点的两个子树高度差最多为 1，所以它又被称为高度均衡树。

如下图中能够清晰的看出，右边的树其根节点左子树高度为 3，右子树高度为 2，合乎 AVL 树的特点；而左边的树其根节点左子树高度为 3，右子树高度为 1，不合乎 AVL 树的特点。因而右边的树为 AVL 树，左边的树不是 AVL 树。

那么怎样才能放弃这种均衡呢？

答案便是在插入或删除节点时，通过对树进行简略的修改来保持平衡，咱们称之为 旋转。

2. 旋转（rotation）

旋转分为单旋转（single rotation）和双旋转（double rotation）。

  • 当左右子树的高度差超过 1，并且最高的叶子节点在“外边”时，应用单旋转。
  • 当左右子树的高度差超过 1，并且最高的叶子节点在“外面”时，应用双旋转。

而单旋转又分为：

  • 左旋转，即向左旋转。当右子树的高度大于左子树时，进行左旋转。
  • 右旋转，即向右旋转。当左子树的高度大于右子树时，进行右旋转。

双旋转又分为：

  • 左 - 右双旋转，即先向左旋转（左子节点），再向右旋转。当左子树的高度大小右子树，并且左子树最高的叶子节点为其父节点的右子节点，那么须要左 - 右双旋转。
  • 右 - 左双旋转，即先向右旋转（右子节点），再向左旋转。当右子树的高度大小左子树，并且右子树最高的叶子节点为其父节点的左子节点，那么须要右 - 左双旋转。

单看这些名词概念是不容易了解的，上面咱们通过图例来一一介绍。

3. 左旋转

看下图中右边的树，该树是一棵二叉查找树，但是否满足 AVL 的个性呢？能够发现其根节点的左子树的高度为 1，而右子树的高度为 3，所以其不一棵 AVL 树。

通过察看，其右子树高于左子树，并且最高的叶子节点也在左边，那么咱们应用左旋转进行均衡。

具体旋转过程：

  • 将根节点 4 复制出一个新的节点，其左子节点为 3 放弃不变，将其右子节点指向 5（即原根节点的右子节点的左子节点）。
  • 将原根节点的右子节点 6 的左子节点指向新节点 4，其右子节点为 7 放弃不变，那么 6 便成了新的根节点。

哈哈，是不是有点绕，其实也能够简略了解为：既然右子树比左子树高，那么将树根 4 向左下移，将树根的右子节点 6 向上移，成为新的树根，这样便使左右子树的高度均衡了。联合上图，重复练习几次吧。

4. 右旋转

右旋转与左旋转正好是对称的，看下图中右边的树，该二叉查找树的左子树高度为 3，而右子树高度为 1，不满足 AVL 树的旋转。

因其左子树高于右子树，并且最高的叶子节点在右边，所以咱们应用右旋转。

具体旋转过程：

  • 将根节点 7 复制出一个新的节点，其右子节点为 9 放弃不变，左子节点指向 5（即原根节点的左子节点的右子节点）。
  • 将原根节点的左节点降级为新的根节点，即其左子树为 3 放弃不变，右子节点指向新的根节点 7。

左旋转与右旋转肯定要了解，不然上面的双旋转就更容易晕菜了！

5. 双旋转

在介绍双旋转之前，先来看下图，其根节点的左子树高度为 3，右子树高度为 9，那么咱们先应用右旋转的形式，看能不能达均衡的成果。

通过观察右旋转后的成果，是不满足 AVL 树的个性的。这便须要应用双旋转了。

咱们应用左 - 右旋转来均衡上图中的树，即先进行左旋转，再进行右旋转，但其平衡点不同，如下图所示。

具体旋转过程：

  • 先将根节点的左子树（5 节点）进行左旋转，升高其（5 节点）右子树的高度。
  • 再将根节点进行右旋转，便达到了均衡成果。

那么反过来，右 - 左双旋转的具体过程：

  • 先将根节点的右子树进行右旋转，升高其右子树的高度。
  • 再将根节点进行左旋转。

6. 代码实现

AVL 树的实现是在二叉查找树的根底上增加了均衡操作。

6.1 求节点高度

在 Node 类中增加节点高度办法 height、leftHeight 和rightHeight，若节点为空则高度为 0。

// 以后节点高度
public int height() {return Math.max(left == null ? 0 : left.height(), right == null ? 0 : right.height()) + 1;
}

// 左子节点高度
public int leftHeight() {if (left == null) {return 0;}
    return left.height();}

// 右子节点高度
public int rightHeight() {if (right == null) {return 0;}
    return right.height();}

6.2 左旋转

在 Node 类中减少左旋转办法leftRotate。

public void leftRotate() {
    // 将以后节点向左下移，成为新的左节点
    Node newLeftNode = new Node(element);
    newLeftNode.left = left;
    // 将右子节点设为原根节点右子树的左子树
    newLeftNode.right = right.left;

    // 将右节点上移，成为新的树根（以后节点）element = right.element;
    // 将左子节点设为新的左子节点（原树根）left = newLeftNode;
    right = right.right;
}

6.3 右旋转

在 Node 类中减少右旋转办法rightRotate。

public void rightRotate() {
    // 将以后节点向右下移，成为新的右子节点
    Node newRightNode = new Node(element);
    // 将左子节点指向原根节点的左子树的右子树
    newRightNode.left = left.right;
    newRightNode.right = right;

    // 将左子节点上移，成为新的树根（以后节点）element = left.element;
    left = left.left;
    // 将右子节点设为新的右子节点（原树根）right = newRightNode;
}

6.4 均衡办法

在 AVLTree 类中增加均衡办法balance，该办法用于判断是须要单旋转还是双旋转。

public void balance(Node node) {if (node == null) {return;}

    if (node.leftHeight() - node.rightHeight() > 1) {if (node.left.rightHeight() > node.left.leftHeight()) {node.left.leftRotate();
        }
        node.rightRotate();} else if (node.rightHeight() - node.leftHeight() > 1) {if (node.right.leftHeight() > node.right.rightHeight()) {node.right.rightHeight();
        }
        node.leftRotate();}
}

6.5 增加节点

在 AVLTree 类中减少增加节点办法，当增加完一个节点后，进行调用 balance 办法，来维持均衡。

private void add(Node node, int element) {if (node.compareTo(element) < 0) {if (node.left == null) {node.left = new Node(element);
        } else {add(node.left, element);
        }
    } else if (node.compareTo(element) > 0) {if (node.right == null) {node.right = new Node(element);
        } else {add(node.right, element);
        }
    }
    balance(node);
}

6.6 删除节点

在 AVLTree 类中减少删除节点办法，当删除完一个节点后，也进行调用 balance 办法，来保护均衡。

private void remove(Node parentNode, Node node, int element) {if (node == null) {return;}
    // 先找到指标元素
    int compareResult = node.compareTo(element);
    if (compareResult < 0) {remove(node, node.left, element);
    } else if (compareResult > 0) {remove(node, node.right, element);
    } else {
        // 找到指标元素，判断该节点是父节点的左子树还是右子树
        boolean isLeftOfParent = false;
        if (parentNode.left != null && parentNode.left.compareTo(element) == 0) {isLeftOfParent = true;}

        // 删除指标元素
        if (node.left == null && node.right == null) { //（1）指标元素为叶子节点，间接删除
            if (isLeftOfParent) {parentNode.left = null;} else {parentNode.right = null;}
        } else if (node.left != null && node.right != null) { //（2）指标元素即有左子树，也有右子树
            // 找到右子树最小值（叶子节点），并将其删除
            Node minNode = findMin(node.right);
            remove(minNode.element);
            // 将该最小值替换要删除的指标节点
            minNode.left = node.left;
            minNode.right = node.right;
            if (isLeftOfParent) {parentNode.left = minNode;} else {parentNode.right = minNode;}

        } else { //（3）指标元素只有左子树，或只有右子树
            if (isLeftOfParent) {parentNode.left = node.left != null ? node.left : node.right;} else {parentNode.right = node.left != null ? node.left : node.right;}
        }
    }
    balance(node);
}

6.7 残缺代码

因为残缺代码篇幅过长，这里就不展现了，能够通过 GitHub 进行拜访，地址如下：
https://github.com/gozhuyinglong/blog-demos/blob/main/java-data-structures/src/main/java/io/github/gozhuyinglong/datastructures/tree/AVLTreeDemo.java

7. 总结

总结一句话来示意 AVL 树：AVL 树是一棵其均衡因子（左右子树的高度差）的绝对值小于 1 的二叉查找树，其能够通过单旋转或双旋转来保持平衡。

退出移动版