【高阶数据结构】AVL树

文章目录

前言
1. 什么是二叉搜索树
2. 什么是AVL树
3. AVL树节点的定义
4. AVL树的插入
- 4.1 新节点插入较高右子树的右侧
- 4.2 新节点插入较高左子树的左侧
- 4.3 新节点插入较高左子树的右侧
- 4.4 新节点插入较高右子树的左侧
- 插入操作完整代码
- 插入操作总结
AVL树的验证
AVL树的删除
AVL树性能分析

前言

前面我们学习了什么是二叉搜索树，但是由于二叉搜索树的局限性，所以对二叉搜索树进行了改进，出现了 AVL 树，这篇文章，我将为大家分享关于 AVL 树——高度平衡的二叉搜索树。

1. 什么是二叉搜索树

我前面为大家详细介绍了二叉搜索树，大家可以去看看这篇文章二叉搜索树，在这里简单为大家介绍一下什么是二叉搜索树。

二叉搜索树（Binary Search Tree）是一种数据结构，它可以用于存储有序的元素集合。在二叉搜索树中，每个节点都有两个子节点，通常称为左子节点和右子节点。节点的值必须大于其左子树中的任何节点的值，并且必须小于其右子树中的任何节点的值。因此，二叉搜索树也被称为二叉排序树或二叉查找树。

在这里插入图片描述

二叉搜索树的特点是，对于每个节点，其左子树中的所有元素都小于该节点，而右子树中的所有元素都大于该节点。这种结构使得在二叉搜索树中查找特定的元素变得非常快速。

对于高度平衡的二叉搜索树，查询数据的时间复杂度可以达到 O(logN)，但是如果该二叉搜索树接近于一个单分支树，那么时间复杂度就会退化到 O(N)。

在这里插入图片描述
所以为了避免出现这种极端的二叉搜索树的情况，就对二叉搜索树进行了优化，出现了 AVL 树，也叫做高度平衡的二叉搜索树。

2. 什么是AVL树

AVL树，也称为自平衡二叉查找树，是一种特殊的二叉查找树，其中任何节点的两个子树的高度差最多为1，也就是平衡因子的绝对值小于等于1。这种平衡性质使得AVL树在插入、删除和查找操作中保持相对稳定，时间复杂度为O(log n)。

平衡因子 = 右子树的高度 - 左子树的高度

AVL树得名于其发明者G. M. Adelson-Velsky和E. M. Landis，他们在1962年的论文《An algorithm for the organization of information》中发表了AVL树。

AVL树的特点包括：

任何节点的两个子树的高度差最多为1，因此也被称为高度平衡树。
插入和删除操作可能需要通过一次或多次旋转来重新平衡树。
查找、插入和删除在平均和最坏情况下都是O(log n)。

在AVL树中，旋转操作用于平衡树的左右子树的高度差，使得树保持平衡。根据需要插入或删除节点的位置，可以进行右旋、左旋或左右旋、右左旋等旋转操作。

AVL树的平衡性质使得它在动态数据集中表现良好，广泛应用于数据库、文件系统和缓存等场景。

3. AVL树节点的定义

为了 AVL 树实现简单，AVL 树节点在定义时会维护一个平衡因子：

class TreeNode {
    public int bf; //平衡因子=右子树的高度-左子树的高度
    public int val;
    public TreeNode left; //节点的左孩子
    public TreeNode right; //节点的右孩子
    public TreeNode parent; //节点的双亲节点

    public TreeNode(int val) {
        this.val = val;
    }
}

4. AVL树的插入

AVL 树就是在二叉搜索树的基础上引入了平衡因子，因此 AVL 树也可以看成是二叉搜索树，AVL 树的插入就是在二叉搜索树插入的基础上添加了一个调整平衡因子的操作。

在这里插入图片描述

通过代码体现就是这样的：

public boolean insert(TreeNode root, int data) {
    TreeNode node = new TreeNode(data);
    if (root == null) {
        root = node;
        return true;
    }
    TreeNode cur = root, parent = null; //parent节点用来记录cur节点的双亲节点，为后面的节点插入做准备
    while (cur != null) {
        if (cur.val < data) {
            parent = cur;
            cur = cur.right;
        }else if (cur.val > data) {
            parent = cur;
            cur = cur.left;
        }else {
            return false;
        }
    }
    //遍历到叶子节点之后，根据data和parent节点值的大小关系决定是插入到parent的左子树还是右子树
    if (parent.val < data) {
        parent.right = node;
    }else {
        parent.left = node;
    }
    node.parent = parent;
}

插入新数据之后，对节点的平衡因子进行调整：

在这里插入图片描述

cur = node;
while (parent != null) {
    if (parent.right == cur) {
        parent.bf++;
    }else {
        parent.bf--;
    }
    //如果插入节点之后的，parent的平衡因子变为0，那么就说明parent在
    //插入这个节点之前就拥有孩子节点，插入节点之后，parent节点拥有
    //左、右孩子，所以该树中的所有节点的平衡因子都不会发生变化。
    if (parent.bf == 0) return true;
    else if (parent.bf == -1 || parent.bf == 1) {
        cur = parent;
        parent = parent.parent;
    }else {
        //节点的平衡因子等于2或者-2的时候，调整节点，使之高度平衡
    }
}

在调整平衡因子的过程中，如果出现了左右孩子高度差的绝对值大于1的情况，就需要对该节点的左右子树进行调整，插入新节点之后，不能保证该二叉搜索树是高度平衡的二叉树，所以就需要我们对不平衡的地方做出调整，那么当前情况该如何对节点进行调整，才能保证该二叉树是一个高度平衡的二叉搜索树呢？

这种情况我们可以对高度不平衡的节点的左右子树进行左旋的操作：

在这里插入图片描述

这只是一种插入情况，下面我们讲所有的需要对节点进行调整的插入情况列举出来。

4.1 新节点插入较高右子树的右侧

在这里插入图片描述

当新节点插入的是较高的右子树的右侧的时候，也就是 parent.bf = 2，cur .bf= 1 的时候通过左单旋来降低右子树的高度。

public void rotateLeft(TreeNode parent) {
    TreeNode subR = parent.right;
    TreeNode subRL = subR.left;
    TreeNode pParent = parent.parent;
    parent.right = subRL;
    if (subRL != null) {
        subRL.parent = parent;
    }
    subR.left = parent;
    parent.parent = subR;
    //这里判断需要旋转的节点是否为根节点，如果是根节点，那么旋转之后的根节点没有双亲节点
    //如果不是根节点，那么旋转之后的根节点的双亲节点就是原根节点的双亲节点
    if (root == parent) {
        root = subR;
        root.parent = pParent;
    }else {
        if (pParent.left == parent) {
            pParent.left = subR;
        }else {
            pParent.right = subR;
        }
        subR.parent = pParent;
    }
    //调整平衡因子
    subR.bf = parent.bf = 0;
}

调整左右子树的高度之后，再调整平衡因子。

在这里插入图片描述

4.2 新节点插入较高左子树的左侧

在这里插入图片描述

此时需要降低左子树的高度，增加右子树的高度，也就是对该树进行右旋操作：

在这里插入图片描述

通过代码演示就是这样的：

public void rotateRight(TreeNode parent) {
    TreeNode subL = parent.left;
    TreeNode subLR = subL.right;
    parent.left = subLR;
    if (subLR != null) {
        subLR.parent = parent;
    }
    TreeNode pParent = parent.parent;
    if (root == parent) {
        root = subL;
        subL.parent = null;
    }else {
        if (pParent.left == parent) {
            pParent.left = subLR;
        }else {
            pParent.right = subLR;
        }
        subLR.parent = pParent;
    }
    subL.right = parent;
    parent.parent = subL;
    subL.bf = parent.bf = 0;
}

4.3 新节点插入较高左子树的右侧

在这里插入图片描述

这种情况下要想降低左子树的高度，增加右子树的高度，只通过右单旋是无法做到的，当新节点插入较高左子树的右侧的时候，就需要线将 cur 的左右子树进行左单旋，然后再对 parent 的左右子树进行右单旋：

在这里插入图片描述

通过代码实现就是这样的：

public void rotateLR(TreeNode parent) {
    TreeNode subL = parent.left;
    TreeNode subLR = subL.right;
    int bf = subL.bf;
    
    rotateLeft(parent.left);
    rotateRight(parent);

	//根据插入的位置是左子树还是右子树来修改平衡因子
    if (bf == 1) {
        parent.bf = 1;
        subL.bf = 0;
        subLR.bf = 0;
    }else {
        parent.bf = 0;
        subL.bf = -1;
        subLR.bf = 0;
    }
}

4.4 新节点插入较高右子树的左侧

在这里插入图片描述

这种情况下，只对 parent 的左右子树进行左单旋的话，是无法保证平衡的，当新插入的节点在较高右子树的左侧的时候，需要先对 subR 的左右子树进行右旋，然后对 parent 的左右子树进行左旋:

在这里插入图片描述

通过代码体现就是这样的：

public void rotateRL(TreeNode parent) {
    TreeNode subR = parent.right;
    TreeNode subRL = subR.left;
    int bf = subRL.bf;

    rotateRight(subR);
    rotateLeft(parent);

    if (bf == -1) {
        parent.bf = 0;
        subR.bf = 1;
        subRL.bf = 0;
    }else {
        parent.bf = -1;
        subR.bf = 0;
        subRL.bf = 0;
    }
}

插入操作完整代码

class TreeNode {
    public int bf; //平衡因子=右子树的高度-左子树的高度
    public int val;
    public TreeNode left; //节点的左孩子
    public TreeNode right; //节点的右孩子
    public TreeNode parent; //节点的双亲节点

    public TreeNode(int val) {
        this.val = val;
    }
}

public class AVLTree {
    TreeNode root;
    public boolean insert(int data) {
        TreeNode node = new TreeNode(data);
        if (root == null) {
            root = node;
            return true;
        }
        TreeNode cur = root, parent = null; //parent节点用来记录cur节点的双亲节点，为后面的节点插入做准备
        while (cur != null) {
            if (cur.val < data) {
                parent = cur;
                cur = cur.right;
            }else if (cur.val > data) {
                parent = cur;
                cur = cur.left;
            }else {
                return false;
            }
        }
        //遍历到叶子节点之后，根据data和parent节点值的大小关系决定是插入到parent的左子树还是右子树
        if (parent.val < data) {
            parent.right = node;
        }else {
            parent.left = node;
        }
        node.parent = parent;
        cur = node;
        while (parent != null) {
            //如果新节点插入的是parent的右子树，那么平衡因子就会加一
            if (parent.right == cur) {
                parent.bf++;
            }else {  //如果新节点插入的是parent的左子树，那么平衡因子就会减一
                parent.bf--;
            }
            //如果parent的平衡因子为0，那么其他节点的平衡因子的绝对值都不会大于1
            if (parent.bf == 0) break;
            //如果parent的平衡因子为1或者-1，那么就说明其他节点的平衡因子可能就会变化，
            //所以需要向上遍历调整其他节点的平衡因子
            else if (parent.bf == -1 || parent.bf == 1) {
                cur = parent;
                parent = parent.parent;
            }else {
                //节点的平衡因子等于2或者-2的时候，调整节点，使之高度平衡
                if (parent.bf == 2) {
                    if (cur.bf == 1) {
                        rotateLeft(parent);
                    }else {
                        rotateRL(parent);
                    }
                }else if (parent.bf == -2) {
                    if (cur.bf == -1) {
                        rotateLeft(parent);
                    }else {
                        rotateLR(parent);
                    }
                }
                //调整完成之后，其他节点的平衡因子的绝对值就是小于2的了，可以直接跳出循环
                break;
            }
        }
        return true;
    }

    public void rotateLeft(TreeNode parent) {
        TreeNode subR = parent.right;
        TreeNode subRL = subR.left;
        TreeNode pParent = parent.parent;
        parent.right = subRL;
        if (subRL != null) {
            subRL.parent = parent;
        }
        if (root == parent) {
            root = subR;
            root.parent = pParent;
        }else {
            if (pParent.left == parent) {
                pParent.left = subR;
            }else {
                pParent.right = subR;
            }
            subR.parent = pParent;
        }
        subR.left = parent;
        parent.parent = subR;
        subR.bf = parent.bf = 0;
    }

    public void rotateRight(TreeNode parent) {
        TreeNode subL = parent.left;
        TreeNode subLR = subL.right;
        parent.left = subLR;
        if (subLR != null) {
            subLR.parent = parent;
        }
        TreeNode pParent = parent.parent;
        if (root == parent) {
            root = subL;
            subL.parent = null;
        }else {
            if (pParent.left == parent) {
                pParent.left = subLR;
            }else {
                pParent.right = subLR;
            }
            subLR.parent = pParent;
        }
        subL.right = parent;
        parent.parent = subL;
        subL.bf = parent.bf = 0;
    }

    public void rotateLR(TreeNode parent) {
        TreeNode subL = parent.left;
        TreeNode subLR = subL.right;
        int bf = subL.bf;
        rotateLeft(parent.left);
        rotateRight(parent);

        //根据插入的位置是左子树还是右子树来修改平衡因子
        if (bf == 1) {
            parent.bf = 1;
            subL.bf = 0;
            subLR.bf = 0;
        }else {
            parent.bf = 0;
            subL.bf = -1;
            subLR.bf = 0;
        }
    }

    public void rotateRL(TreeNode parent) {
        TreeNode subR = parent.right;
        TreeNode subRL = subR.left;
        int bf = subRL.bf;

        rotateRight(subR);
        rotateLeft(parent);

        if (bf == -1) {
            parent.bf = 0;
            subR.bf = 1;
            subRL.bf = 0;
        }else {
            parent.bf = -1;
            subR.bf = 0;
            subRL.bf = 0;
        }
    }
}

插入操作总结

新节点插入之后，假设以 parent 为根的子树不平衡，即 parent 的平衡因子为 2 或者 -2，解决情况如下：

parent 的平衡因子为 2，说明 parent 的右子树高，设 parent 的右子树的根为 subR

当 subR 的平衡因子为 1 时，执行左单旋
当 subR 的平衡因子为 -1 时，执行右左双旋

当 parent 的平衡因子为 -2，说明 parent 的左子树高，设 parent 的左子树的根为 subL

当 subL 的平衡因子为 -1 时，执行右单旋
当 subL 的平衡因子为 1 时，执行左右双旋

AVL树的验证

因为 AVL 树是高度平衡的二叉搜索树，所以我们在验证是否为 AVL 树的时候，不仅需要判断它是否为二叉搜索树，还需要验证它是否高度平衡。

判断是否为二叉搜索树：

private int prev = Integer.MIN_VALUE;
public boolean isBinarySearchTree(TreeNode root) {
    if (root == null) return true;
    boolean l = isBinarySearchTree(root.left);
    if (!l) return false;
    if (root.val > prev) {
        prev = root.val;
    }else {
        return false;
    }
    return isBinarySearchTree(root.right);
}

判断是否高度平衡：

public boolean isBalance(TreeNode root) {
    if (root == null) return true;
    boolean lb = isBalance(root.left);
    if (!lb) return false;
    boolean rb = isBalance(root.right);
    if (!rb) return false;
    int l = height(root.left);
    int r = height(root.right);
	//平衡因子可能有错误
    if (r - l != root.bf) {
        System.out.println(root.val + "平衡因子异常");
    }
    return Math.abs(l - r) <= 1;
}

提供接口：

public boolean isAVLTree(TreeNode root) {
    return isBalance(root) && isBinarySearchTree(root);
}

AVL树的删除

因为 AVL 树也是二叉搜索树，所以也可以先根据二叉搜索树的方式进行删除，然后再调整平衡因子，这里我就不为大家介绍了，大家有兴趣可以去看看《算法导论》或者《数据结构-用面向对象方法与C++描述》殷人昆版这两本书。

AVL树性能分析

AVL树是一种自平衡二叉搜索树，每个节点都保存一个平衡因子，用于判断是否需要进行旋转操作来保持树的平衡。平衡因子是右子树的高度减去左子树的高度（有时相反），其值只可能是-1、0或1。如果插入或删除一个节点后，某个节点的平衡因子的绝对值大于1，就需要进行旋转操作来重新平衡这棵树。

AVL树的性能如下：

查询性能：AVL树的每个节点的左右子树高度差的绝对值都不超过1，这样可以保证查询时高效的时间复杂度，即O(log n)，其中n是树中节点的数量。因此，AVL树的查询性能比普通的二叉搜索树更稳定。
插入性能：在AVL树中插入节点时，需要维护其绝对平衡，因此旋转的次数可能比较多。插入操作的时间复杂度也是O(log n)。
删除性能：在AVL树中删除节点时，有可能需要一直进行旋转操作，直到达到根节点。因此，删除操作的性能可能相对较差，时间复杂度也可能较高。

总体来说，AVL树的性能比普通的二叉搜索树更稳定，查询性能更高。但是，如果需要对AVL树进行频繁的结构修改操作，其性能可能会受到影响。因此，如果需要一种查询高效且有序的数据结构，而且数据的个数为静态的（即不会改变），可以考虑使用AVL树。但如果数据经常需要修改，其他数据结构可能更适合。