数据结构之「AVL树」

你的名字 2022-01-20 08:43 235阅读 0赞

### 前言 ###

二叉搜索树在一般情况下它的查找时间复杂度是 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:  
清山绿水始于尘，博学多识贵于勤。  
我有酒，你有故事吗？  
公众号：「**清尘闲聊**」。  
欢迎一起谈天说地，聊代码。