AVL树 - Dreams

AVL树是一种自平衡二叉搜索树，它在每次插入或删除节点时通过旋转操作来保持树的平衡。

比如：如果一个节点的左右孩子，高度差超过1，则此节点失衡，需要旋转。

先创建AVLTree类

public class AVLTree {

    static class AVLNode {
        int key;
        Object value;
        AVLNode left;
        AVLNode right;
        int height = 1; // 高度

        public AVLNode(int key, Object value) {
            this.key = key;
            this.value = value;
        }

        public AVLNode(int key) {
            this.key = key;
        }

        public AVLNode(int key, Object value, AVLNode left, AVLNode right) {
            this.key = key;
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }
}

AVL树想要知道节点高度，所以需要一个获取节点高度的函数，注意要避免空节点。

// 求节点的高度
private int height(AVLNode node) {
    return node == null ? 0 : node.height;
}

在新增、删除、旋转后需要更新节点高度

// 更新节点高度 (新增、删除、旋转)
private void updateHeight(AVLNode node) {
    node.height = Integer.max(height(node.left), height(node.right)) + 1;
}

AVL树的平衡是通过节点上的平衡因子进行维护的，平衡因子是指左子树高度减去右子树高度的值。

在AVL树中，每个节点都有一个平衡因子，其取值可以是-1、0或1，表示左右子树高度的差别。当插入或删除节点导致某个节点的平衡因子超过了这个范围时，就需要进行旋转操作来调整树的结构，以使其重新达到平衡状态。

平衡因子 > 1 时，表示左边太高。

平衡因子<1 时，表示右边太高。

所以需要一个获取平衡因子的函数

// 平衡因子 (balance factor) = 左子树高度-右子树高度 1 -1 0
private int bf(AVLNode node) {
    return height(node.left) - height(node.right);
}

在AVL树中，有四种可能的失衡情况，它们分别对应着四种旋转操作，以恢复树的平衡状态。这些失衡情况是：

左子树的左子树失衡（LL失衡）：
当在一个节点的左子树的左子树上插入节点后，导致该节点的平衡因子大于1时，就发生了LL失衡。
左子树的右子树失衡（LR失衡）：
当在一个节点的左子树的右子树上插入节点后，导致该节点的平衡因子小于-1时，就发生了LR失衡。
右子树的右子树失衡（RR失衡）：
当在一个节点的右子树的右子树上插入节点后，导致该节点的平衡因子小于-1时，就发生了RR失衡。
右子树的左子树失衡（RL失衡）：
当在一个节点的右子树的左子树上插入节点后，导致该节点的平衡因子大于1时，就发生了RL失衡。

针对每种失衡情况，AVL树都有相应的旋转操作来进行调整，以恢复树的平衡状态。

解决AVL树的失衡问题，需要使用旋转操作来调整树的结构，以恢复平衡状态。下面是对应每种失衡情况的解决方法：

LL失衡（左子树的左子树失衡）：
解决方法是进行右旋操作。将失衡节点的左子节点变为该树的根节点，失衡节点变为该树的右子节点，失衡节点的原左子节点的右子节点成为失衡节点的左子节点。
LR失衡（左子树的右子树失衡）：
解决方法是先对失衡节点的左子节点进行左旋操作，然后再对失衡节点进行右旋操作。先左旋后右旋。
RR失衡（右子树的右子树失衡）：
解决方法是进行左旋操作。将失衡节点的右子节点变为根节点，失衡节点变为该树的左子节点，失衡节点的原右子节点的左子节点成为失衡节点的右子节点。
RL失衡（右子树的左子树失衡）：
解决方法是先对失衡节点的右子节点进行右旋操作，然后再对失衡节点进行左旋操作。先右旋后左旋。

右旋操作函数

将失衡节点的左子节点变为该树的根节点，失衡节点变为该树的右子节点，失衡节点的原左子节点的右子节点成为失衡节点的左子节点。

右旋前

右旋后

代码如下

注意高度有一个属性记录，所以需要更新高度

// 参数：要旋转的节点, 返回值：新的根节点
private AVLNode rightRotate(AVLNode red) {
    AVLNode yellow = red.left;
    AVLNode green = yellow.right;
    yellow.right = red; // 上位
    red.left = green; // 换父
    updateHeight(red);
    updateHeight(yellow);
    return yellow;
}

同理，左旋

将失衡节点的右子节点变为根节点，失衡节点变为该树的左子节点，失衡节点的原右子节点的左子节点成为失衡节点的右子节点。

左旋前

左旋后

代码如下

// 参数：要旋转的节点, 返回值：新的根节点
private AVLNode leftRotate(AVLNode red) {
    AVLNode yellow = red.right;
    AVLNode green = yellow.left;
    yellow.left = red;
    red.right = green;
    updateHeight(red);
    updateHeight(yellow);
    return yellow;
}

解决LR

// 先左旋左子树, 再右旋根节点
private AVLNode leftRightRotate(AVLNode node) {
    node.left = leftRotate(node.left);
    return rightRotate(node);
}

解决RL

// 先右旋右子树, 再左旋根节点
private AVLNode rightLeftRotate(AVLNode node) {
    node.right = rightRotate(node.right);
    return leftRotate(node);
}

检查节点是否失衡, 重新平衡代码

private AVLNode balance(AVLNode node) {
    if (node == null) {
        return null;
    }
    int bf = bf(node);
    if (bf > 1 && bf(node.left) >= 0) { // LL
        return rightRotate(node);
    } else if (bf > 1 && bf(node.left) < 0) { // LR
        return leftRightRotate(node);
    } else if (bf < -1 && bf(node.right) > 0) { // RL
        return rightLeftRotate(node);
    } else if (bf < -1 && bf(node.right) <= 0) { // RR
        return leftRotate(node);
    }
    return node;
}

在AVL树中进行添加（插入）操作时，需要按照二叉搜索树的规则找到合适的位置插入新节点，然后通过旋转操作来保持树的平衡。

AVLNode root;

public void put(int key, Object value) {
    root = doPut(root, key, value);
}

private AVLNode doPut(AVLNode node, int key, Object value) {
    // 1. 找到空位, 创建新节点
    if (node == null) {
        return new AVLNode(key, value);
    }
    // 2. key 已存在, 更新
    if (key == node.key) {
        node.value = value;
        return node;
    }
    // 3. 继续查找
    if (key < node.key) {
        node.left = doPut(node.left, key, value); // 向左
    } else {
        node.right = doPut(node.right, key, value); // 向右
    }
    updateHeight(node);
    return balance(node);
}

在AVL树中进行删除操作时，同样需要保持树的平衡状态。

处理删除节点：

如果要删除的节点是叶子节点（没有子节点），可以直接删除该节点。
如果要删除的节点有一个子节点，可以用子节点替换该节点。
如果要删除的节点有两个子节点，则选择后继节点来替换该节点。逻辑就是先找到其后继节点，就是在删除的节点的右子树最小的一个，然后使用同样逻辑在删除的节点的右子树中删除该后继节点，将后继节点的右子树赋为原删除的节点的右子树，后继节点的左子树赋为原删除的节点的左子树。然后就可以替换掉要删除的节点了。

public void remove(int key) {
    root = doRemove(root, key);
}

private AVLNode doRemove(AVLNode node, int key) {
    // 1. node == null
    if (node == null) {
        return null;
    }
    // 2. 没找到 key
    if (key < node.key) {
        node.left = doRemove(node.left, key);
    } else if (node.key < key) {
        node.right = doRemove(node.right, key);
    } else {
        // 3. 找到 key 1) 没有孩子 2) 只有一个孩子 3) 有两个孩子
        if (node.left == null && node.right == null) {
            return null;
        } else if (node.left == null) {
            node = node.right;
        } else if (node.right == null) {
            node = node.left;
        } else {
            AVLNode s = node.right;
            while (s.left != null) {
                s = s.left;
            }
            // s 后继节点
            s.right = doRemove(node.right, s.key);
            s.left = node.left;
            node = s;
        }
    }
    // 4. 更新高度
    updateHeight(node);
    // 5. balance
    return balance(node);
}

参考

黑马数据结构

发送评论 编辑评论

推荐文章

发送评论编辑评论