数据结构之「AVL树」

前言

二叉搜索树在一般情况下它的查找时间复杂度是 O(log n)。但在一些特殊的情况下，它会退化为斜树变成线性结构，导致查询效率大大降低，根本发挥不出折半查找的优势。因此，就需要一种平衡的二叉搜索树来达到我们期望查询时间复杂度为 O(log n) 的数据结构，那就是平衡二叉搜索树。

平衡二叉搜索树

平衡二叉搜索树又叫 AVL树，它具有以下性质：
1.任一节点对应的两棵子树的最大高度差为 1。
2.两棵子树都是平衡二叉树。

通过保证上面 2 条规则，因此它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下的时间复杂度都是O(log n)。因此，它是一颗相对稳定的树。

为了保证左右 2 棵子树的最大高度差为 1，我们需要在插入和删除时，对树进行旋转操作，以保证树的平衡性。有 2 种基本的操作，那就是左旋和右旋。

树的左旋和右旋
在进行左右旋转时，会出现四种可能性：
1.左左形态
当 x 是 y 的左节点，y 又是 z 的左节点时，这个时候只需要把 y 节点向右旋转即可。如下图：
左左
2.左右形态
当 x 是 y 的右节点，而 y 又是 z 的左节点时，需要先把 y 左旋，变成 左左形态，然后再把 z 右旋。如下图：
左右
3.右右形态
当 x 是 y 的右节点， y 又是 z 的右节点时，这时候只需要把 y 节点向左旋转即可。如下图：
右右
4.右左形态
当 x 是 y 的左节点，而 y 又是 z 的右节点时，需要先把 y 右旋，变成 右右形态，然后再把 z 左旋。如下图：
右左

平衡二叉树的实现

public class AVLTree {

    //获取左右节点的高度差
    public int getBalance(Node n) {
        if (n != null) {
            return (getHeight(n.left) - getHeight(n.right));
        }
        return 0;
    }
    //获取节点的高度
    public int getHeight(Node n) {
        if (n != null) {
            return n.height;
        }
        return 0;
    }

    //右旋
    public Node rightRotate(Node y) {
        Node x = y.left;
        Node T2 = x.right;

        // 旋转
        x.right = y;
        y.left = T2;

        // 更新节点的高度
        x.height = Math.max(getHeight(x.left), getHeight(x.right)) + 1;
        y.height = Math.max(getHeight(y.left), getHeight(y.right)) + 1;

        return x;
    }

    //左旋
    public Node leftRotate(Node x) {
        Node y = x.right;
        Node T2 = y.left;

        // 旋转
        y.left = x;
        x.right = T2;

        // 更新节点的高度
        x.height = Math.max(getHeight(x.left), getHeight(x.right)) + 1;
        y.height = Math.max(getHeight(y.left), getHeight(y.right)) + 1;

        return y;
    }

    public Node insert(Node node, int data) {
        if (node == null) {
            return (new Node(data));
        }
        if (node.data > data) {
            node.left = insert(node.left, data);
        } else {
            node.right = insert(node.right, data);
        }
        // 更新节点的高度
        node.height = Math.max(getHeight(node.left), getHeight(node.right)) + 1;

        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(int data) {
        this.data = data;
        height = 1;
    }
}

总结

二叉搜索树的不稳定性，就有可能退化为近似链或链，查询时间复杂度就退化为 O(n)。当 n 很大的时候，性能就大大降低，达不到折半的效果。因此，我们需要一个平衡的二叉搜索树。

平衡二叉树是通过对树节点的左旋和右旋来保证树的平衡性，也就是保证左右子树的高度差不超过 1。

在对树进行左旋和右旋时，有四种形态分别是：左左，左右，右右，右左。

因此，平衡二叉树的查找、插入和删除在平均和最坏情况下的时间复杂度都是O(log n)。

PS:
清山绿水始于尘，博学多识贵于勤。
我有酒，你有故事吗？
公众号：「清尘闲聊」。
欢迎一起谈天说地，聊代码。