AVL 树旋转及 JS 实现，平衡树支棱起来~

玖柒的小窝

发布于 2021-11-28 20:17:37

2K0

发布于 2021-11-28 20:17:37

文章被收录于专栏：各类技术文章~各类技术文章~

AVL旋转

在 AVL 树中，增加和删除元素的操作则可能需要借由一次或多次 树旋转，以实现树的重新平衡。

所以，AVL树最核心操作就是“AVL 旋转”！

以下 GIF 演示了不断将节点插入AVL树时的情况，包含:

左旋（Left Rotation）
右旋（Right Rotation）
右左旋转（Right-Left Rotation）
左右旋转（Left-Right Rotation）
以及带子树的右旋（Right Rotation with children）

安利一个在线动态演示 VAL 树的旋转的网站：www.cs.usfca.edu/~galles/vis… 👍👍👍

png 示意：

（图片来源：wikipedia）

AVL 的操作代价分析：

查找代价：查找效率很好，最坏情况都是O(logN)数量级；
插入代价： AVL必须要保证严格平衡(|bf|<=1)，那么每一次插入数据使得AVL中某些结点的平衡因子超过1就必须进行旋转操作。事实上，AVL的每一次插入结点操作最多只需要旋转1次(单旋转或双旋转)。因此，总体上插入操作的代价仍然在O(logN)级别(插入结点需要首先查找插入的位置)；
删除代价：删除必须检查从删除结点开始到根结点路径上的所有结点的平衡因子。因此删除的代价稍微要大一些。每一次删除操作最多需要O(logN)次旋转。因此，删除操作的时间复杂度为O(logN)+O(logN)=O(2logN)；

JS 实现

左单旋：

function roateLeft(AvlNode) {
        var node = AvlNode.right; // 保存右子节点
        AvlNode.right = node.left; // node的左子节点连接到AvlNode成为其右子节点
        node.left = AvlNode; // AvlNode连接到node成为其左子节点
        return node; // 返回node，连接到AvlNode最初的父节点
}
复制代码

右单旋：

function roateRight(AvlNode) {
        var node = AvlNode.left; // 保存左子节点
        AvlNode.left = node.right; // 将node的右子节点连接到AvlNode成为其左子节点
        node.right = AvlNode; // AvlNode连接到node，成为其右子节点
        return node; // 返回node连接到AvlNode最初的父节点
}
复制代码

左-右双旋：

function roateLeftRight(AvlNode) {
        AvlNode.right = roateLeft(AvlNode.right); // 对右子节点做左单旋
        return roateRight(AvlNode); // 做右单旋
}
复制代码

右-左双旋：

function roateRightLeft(AvlNode) {
        AvlNode.left = roateRight(AvlNode.left); // 对左子节点做右单旋
        return roateLeft(AvlNode); // 做左单旋
}
复制代码

获取树高度的函数：

function getAvlTreeHeight(node) {
        if (node == null) {
            // node不存在返回0
            return 0;
        } else {
            var leftHeight = getAvlTreeHeight(node.left);
            var rightHeight = getAvlTreeHeight(node.right);
            // 返回左子树、右子树中的最大高度
            return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
        }
}
复制代码

实现平衡树的函数：

function balance(node) {
    if (node == null) {
        return node;
    }
    // 左子树高度比右子树高度大1以上
    if (getAvlTreeHeight(node.left) - getAvlTreeHeight(node.right) > 1) {
        if (getAvlTreeHeight(node.left.left) >= getAvlTreeHeight(node.left.right)) {
            // 如果左子树的左子树高度大于等于左子树的右子树高度
            // 直接进行右单旋
            node = roateRight(node);
        } else {
            // 否则需要右-左双旋
            node = roateRightLeft(node);
        }
        // 右子树高度比左子树高度大1以上
    } else if (getAvlTreeHeight(node.right) - getAvlTreeHeight(node.left) > 1) {
        if (getAvlTreeHeight(node.right.right) >= getAvlTreeHeight(node.right.left)) {
            // 如果右子树的右子树高度大于等于右子树的左子树高度
            // 直接进行左单旋
            node = roateLeft(node);
        } else {
            // 否则需要左-右双旋
            node = roateLeftRight(node);
        }
    }
    return node;
}
复制代码

每次插入节点，都需要做一次树的平衡处理：

var insertNode = function(node, newNode){
    if (newNode.key < node.key){
        if (node.left === null){
            node.left = newNode;
            // 插入节点后，做树的平衡处理
            node.left = balance(node.left);
        } else {
            insertNode(node.left, newNode);
        }
    } else {
        if (node.right === null){
            node.right = newNode;
            // 插入节点后，做树的平衡处理
            node.right = balance(node.right);
        } else {
            insertNode(node.right, newNode);
        }
    }
}
复制代码

u1s1，当树开始旋转，脑袋也有点晕眩了╮(╯▽╰)╭

啃不下来，就先收藏慢慢啃吧~~

不慌，后续还会带来更多关于平衡二叉树的练习，以及前端少有接触的红黑树等等。。。

OK，以上就是本篇分享~ 撰文不易，点赞鼓励👍👍👍

本文系转载，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

children