图解AVL树

2024-02-22 08:42:46

1：AVL树简介

二叉搜索树在一般情况下其搜索的时间复杂度为O(logn)，但某些特殊情况下会退化为链表，导致树的高度变大且搜索的时间复杂度变为O(n)，发挥不出树这种数据结构的优势，因此平衡二叉树便应运而生，通过保证树的高度来保证查询的时间复杂度为O(logn)，想想人类实在是太聪明了！

2：构造AVL树

在构造一棵AVL树的时候如何保持平衡呢？其手段便是通过各种旋转变换来调整以此保证整棵树的高度，调整的原则是左右子树的高度不能大于1的绝对值(平衡因子)先来介绍下旋转的方法吧。

2.1：LL型

当插入元素后构成LL型，如下图所示，则以2为支，高右转，把3右旋下来保证平衡。

2.2：RR型

当插入元素后构成RR型，如下图所示，则以2为支，高左转，把1左旋转下来保证平衡。

2.3：LR型

当插入元素后构成LR型，如下图所示，先2,3整体左旋，在根据LL型进行右旋转来保证平衡。

2.4：RL型

当插入元素后构成RL型，如下图所示，先将5右转，在与6进行交换，在根据RR型进行旋转来保证平衡。

2.5：其他情况

当因为插入一个元素而导致出现两个不平衡点，应该调整距离插入节点最近的不平衡点

2.6：自测题

测试题：以关键字序列{16、3、7、11、9、26、18、14、15}构造一颗AVL树

2.7：java实现AVL的构造

package AVL;

/**
 * @author admin
 * @version 1.0.0
 * @ClassName AVLTree.java
 * @Description TODO
 * @createTime 2020年03月30日 18:28:00
 */
public class AVLTree {


    /**
     * 获取左右节点的高度差,即平衡因子
     * @param root
     * @return
     */
    public int getBalance(Node root) {
        return root==null?0:getHeight(root.left)-getHeight(root.right);
    }

    /**
     * 获取节点的高度
     * @param root
     * @return
     */
    public int getHeight(Node root) {
        return root == null ? 0 : root.height;
    }

    /**
     * 更新节点的高度
     * @param root
     * @return
     */
    private  int updateHeight(Node root) {
        if (root == null)
            return 0;
        return Math.max(updateHeight(root.left), updateHeight(root.right)) + 1;
    }

    /**
     * LL型，右旋操作
     *
     * @param root
     * @return
     */
    public Node rightRotate(Node root) {
        Node node = root.left;
        root.left = node.right;
        node.right = root;
        root.height = updateHeight(root);
        node.height = updateHeight(node);
        return node;
    }

    /**
     * RR型，左旋操作
     * @param root
     * @return
     */
    public Node leftRotate(Node root) {
        Node node = root.right;
        root.right = node.left;
        node.left = root;
        root.height = updateHeight(root);
        node.height = updateHeight(node);
        return node;
    }

    public Node insert(Node node, int data) {
        //当节点为空，直接插入
        if (node == null) {
            return (new Node(data));
        }
        //当插入元素<node.data,往node的左子树进行插入；>node.data，往node的右子树插入
        if (node.data > data) {
            node.left = insert(node.left, data);
        } else {
            node.right = insert(node.right, data);
        }
        //更新节点的高度
        node.height = updateHeight(node);
        //获取平衡因子(左子树高度-右子树高度)
        int balDiff = getBalance(node);

        // 右旋
        if (balDiff > 1 && data < node.left.data) {
            return rightRotate(node);
        }

        // 左旋
        if (balDiff < -1 && data > node.right.data) {
            return leftRotate(node);
        }

        // 先左旋在右旋
        if (balDiff > 1 && data > node.left.data) {
            node.left = leftRotate(node.left);
            return rightRotate(node);
        }

        // 先右旋在左旋
        if (balDiff < -1 && data < node.right.data) {
            node.right = rightRotate(node.right);
            return leftRotate(node);
        }

        return node;
    }

    
}

class Node {
    int data;
    Node left;
    Node right;
    int height;

    public Node(Integer data) {
        this.data = data;
        height = 1;
    }
}

3：AVL树的删除

3.1：删除叶子节点

3.2：删除只拥有左子树或右子树的节点

3.3：删除既拥有左子树又有右子树的节点

3.4：自测题

将上一道自测题的图依次删除16，15，11节点，画出最后的结果

参考链接

数据可视化网站： https://visualgo.net/zh

哔哩哔哩讲AVL：https://www.bilibili.com/video/BV1xE411h7dd

码农公寓