首页 > 资讯 > 后端开发 > JAVA >AVL树（Java）

891

分享到

AVL树（Java）

数据结构 java AVL树 2024-01-21 15:01:19 891人浏览八月长安

摘要

目录一、什么是AVL树二、AVL树的实现 AVL树的节点 AVL树的插入 AVL树的旋转右单旋左单旋左右双旋右左双旋 AVL树的验证三、AVL树的性能分析一、什么是AVL树在了解什么

一、什么是AVL树

二、AVL树的实现

AVL树的节点

AVL树的插入

AVL树的旋转

右单旋

左单旋

左右双旋

右左双旋

AVL树的验证

三、AVL树的性能分析

一、什么是AVL树

在了解什么是AVL树之前，我们先回顾二叉搜索树的概念

二叉搜索树（二叉排序树），它或是一棵空树，或具有以下性质：

1. 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值

2. 若它的右子树不为空，则右子树上所有节点的值都大于根节点

3. 它的左右子树也分别是二叉搜索树

根据二叉搜索树的性质，我们可以发现：

1. 二叉搜索树中最左侧的节点是树中最小的节点，最右侧的节点是树中最大的节点

2. 若采用中序遍历二叉搜索树，则可得到一个有序的序列

二叉搜索树最主要的作用就是用于进行查询：

当二叉搜索树是一颗完全二叉树时：

其查询的平均查找次数为: $log_{2}^{}n$

而当二叉搜索树是一颗单支树时：

其平均查找次数为： $\frac{n}{2}$

由此可见二叉搜索树的平均查找次数与二叉搜索树的深度成正相关，即深度越深，比较查找的次数越多。而当其是单支树时，二叉搜索树的性能就降低了，此时，能否对其进行改进，使其无论怎样插入，都能够使二叉搜索树的性能最佳？

AVL树的出现解决了这个问题。

ALV树（也就是平衡二叉查找树，简称平衡二叉树）或是一颗空树，或具有以下性质：

1. 它的左右子树高度之差（简称平衡因子）的绝对值不超过1

2. 它的左右子树都是AVL树

由AVL树的性质，我们可以发现：

1. 每当向AVL树中插入新的节点时，都要保证每个节点的左右子树高度差（平衡因子）的绝对值不超过1（当超过时需要对树中的节点进行调整，即降低树的高度，从而减少平均搜索长度）

2. 若一颗AVL树有n个节点，它的高度能够保持在 $log_{2}^{}N$ ，因此，其搜索的时间复杂度为O( $log_{2}^{}N$ )

二、AVL树的实现

AVL树的节点

在这里，我们通过一个内部类来实现AVL树节点的定义，通过维护节点的左孩子、右孩子和父亲节点来实现AVL树，同时定义一个平衡因子bf，通过平衡因子来判断是否需要调整树中节点。同时，我们需要定义根节点：

public class AVLTree {
    static class Treenode{
        public int val;//节点的值
        public int bf;//平衡因子
        public TreeNode left;//左孩子
        public TreeNode right;//右孩子
        public TreeNode parent;//父亲节点
        public TreeNode(int val){
            this.val = val;
        }
    }

    public TreeNode root;//根节点
}

当前节点的平衡因子 = 右子树的高度 - 左子树的高度

AVL树的插入

AVL树就是在二叉搜索树的基础上引入了平衡因子，因此，我们可以将AVL树的插入过程分为两步：

1. 插入新的节点

2. 调整节点的平衡因子

现在我们对新的节点进行插入：

1. 当AVL树为空时，插入的节点即为根节点

2. AVL树不为空，则寻找新节点的插入位置

如何寻找新节点的插入位置？

若新节点node的值val > 当前节点cur的值val，则在cur的右子树寻找插入位置；

若node.val < cur.val，则在cur的左子树寻找插入位置；

若node.val = cur.val，则AVL树中已有该节点，插入失败，直接返回false

在找到插入位置后，我们需要知道其父亲节点，从而进行插入，因此在查找过程中，我们可以定义当前节点cur的父亲节点parent，用于最后进行插入新节点：

    //节点的插入
    public boolean insert(int val){
        TreeNode node = new TreeNode(val);
        //若根节点为空，则直接将插入为根节点
        if(root == null){
            root = node;
            return true;
        }
        //根节点不为空，查找其插入位置
        TreeNode parent = null;
        TreeNode cur = root;
        while (cur != null){
            if(cur.val < val){
                parent = cur;
                cur = cur.right;
            }else if(cur.val > val){
                parent = cur;
                cur = cur.left;
            }else{
                return false;//若已有该节点，则插入失败，直接返回false
            }
        }
        //将节点插入
        node.parent = parent;
        cur = node;
    }

AVL树的旋转

在插入新的节点之后，此时AVL树中某些节点的平衡因子会发生改变，因此我们需要对平衡因子进行修改，而在插入新节点后，节点的平衡因子的绝对值可能超过1，此时我们需要对节点进行调整

我们首先对平衡因子进行修改：

在插入新节点时，我们定义了其父亲节点parent，由于在这里平衡因子 = 右子树的高度 - 左子树的高度

因此，若新插入的节点在parent的左子树，则其平衡因子 -1；而若新插入的节点在parent的右子树，则平衡因子 +1

在修改完当前平衡因子后，我们需要对当前平衡因子进行检查，判断其是否符合条件：

1. 若修改后的平衡因子 = 0，则表明未修改时parent的平衡因子bf = 1 或 -1，在插入后被调整成为0，此时子树parent已经平衡了，且其高度并未发生改变，不会影响上面节点的平衡因子，因此不用再继续向上判断

2. 若修改后的平衡因子 = 1 或 -1，则表明未修改时parent的平衡因子bf = 0，在插入之后被调整成 1 或 -1，此时子树parent的高度增加，上面节点的平衡因子也会被影响，因此需要继续向上更新平衡因子

3. 若修改后的平衡因子的绝对值 > 1，此时则需要对AVL树的节点进行调整，重新使其平衡

在这里，我们通过旋转来调整节点的平衡因子，AVL树的旋转分为四种情况：

右单旋

（1）新节点插入较高左子树的左侧->右单旋

当新节点插入较高左子树的左侧时：

此时 patent.bf = -2, cur.bf = -1，要想办法降低左子树的高度，因此对其进行调整：

将对于以parent 为根的子树：

将cur作为其根；parent作为cur的右子树；cur原右子树（若有的话）作为parent的左子树，

这样重新调整后，cur和parent的平衡因子都被调整为0，此时以cur为根的子树已经平衡

因此，我们调整的步骤为：

我们设parent的左孩子cur为subL，cur的右孩子为subLR（因为要考虑cur的右孩子不存在的情况）

1. 将parent的左孩子更新为subLR，将subLR的父亲节点更新为parent

注：此时要考虑subLR为空的情况，若subLR为空，则不需要更新

2. 将subL的右孩子更新为parent，将parent的父亲节点更新为subL

注：在更新parent的父亲节点时，我们首先要将parent的父亲节点pParent保存起来，因为我们需要将subL的父亲节点更新为parent的父亲节点

3. 更新subL的父亲节点，

若parent原为根节点，此时需要将根节点更新为subL，同时将subL的父亲节点更新为null；

若parent原不为根节点，则更新subL的父亲节点为pParent，同时需要更新pParent的孩子节点，此时需要判断parent为pParent的左孩子还是右孩子，并更新

右单旋代码：

//右单旋
private void rotateRight(TreeNode parent){
    TreeNode subL = parent.left;
    TreeNode subLR = subL.right;

    parent.left = subLR;
    if(subLR != null){//只有当subLR不为空时，才能修改其父亲节点
        subLR.parent = parent;
    }
    
    subL.right = parent;
    //在修改parent的父亲节点时，必须先记录其父亲节点，以便修改subL的父亲节点
    TreeNode pParent = parent.parent;
    parent.parent = subL;
    //判断subL是否被修改为根节点
    if(parent == root){
        root = subL;
        root.parent = null;
    }else {
        subL.parent = pParent;
        //判断是左子树还是右子树
        if(pParent.left == parent){
            pParent.left = subL;
        }else {
            parent.right = subL;
        }
    }
    //修改平衡因子
    subL.bf = 0;
    parent.bf = 0;
}

左单旋

新节点插入较高右子树的右侧->左单旋

左单旋与右单旋类似：

当新的节点插入到较高右子树的右侧时：

此时 parent.bf = 2, cur.bf = 1，要想办法降低右子树的高度，对以parent为根的子树进行调整：

设parent的右孩子cur为subR，subR的左孩子为subRL（要考虑subR的左孩子为空的情况）

1. 将parent的右孩子更新为subRL，将subRL的父亲节点更新为parent（若subRL不为空）

2. 将subR的左孩子更新为parent，保存parent的父亲节点pParent，再更新parent的父亲节点为subR

3. 更新subR的父亲节点，若parent原为根节点，则更新根节点为subR，并将其父亲节点更新为null；若parent原不为根节点，则更新subR的父亲节点为pParent，判断parent原为pParent的左孩子还是右孩子，并将subR更新为pParent的孩子节点

左单旋代码：

//左单旋
private void rotateLeft(TreeNode parent){
    TreeNode subR = parent.right;
    TreeNode subRL = subR.left;
    
    parent.right = subRL;
    if(subRL != null){//只有当subRL不为空时，才能修改其父亲节点
        subRL.parent = parent;
    }
    
    subR.left = parent;
    //在修改parent父亲节点前将其进行记录，以便后续修改subR的父亲节点
    TreeNode pParent = parent.parent;
    parent.parent = subR;
    //判断subR是否被修改为根节点
    if(parent == root){
        root = subR;
        root.parent = null;
    }else {
        //判断是其左子树还是右子树
        if(pParent.left == parent){
            pParent.left = subR;
        }else{
            pParent.right = subR;
        }
        subR.parent = pParent;
    }
    //修改平衡因子
    subR.bf = 0;
    parent.bf = 0;
}

左右双旋

新节点插入较高左子树的右侧->左右双旋（先左单旋再右单旋）

当新的节点插入较高左子树的右侧时：

此时 parent.bf = -2, cur.bf = 1，此时对于以parent为根的子树，无论是进行右单旋，还是进行左单旋，都不能使其平衡。因此，此时不能只进行一次旋转，而需要进行两次旋转：
首先，我们需要对以cur为根的子树进行一次左单旋：

然后再对以parent为根的子树进行一次右单旋：

此时调整后的子树达到平衡状态，由于进行的左单旋和右单旋会更改其中节点的平衡因子，因此我们需要对被修改的平衡因子进行重新调整：

平衡因子被修改的节点有：parent、parent的左孩子subL、subL的右孩子subLR

它们的平衡因子都被修改为0，

然而经过两次旋转后，它们的平衡因子并不都为0

通过观察我们发现，当subLR的平衡因子原为-1时，经过调整后，parent的平衡更新为1

当subLR的平衡因子原为1时，经过调整后，subL的平衡因子被更新为-1：

当subLR的平衡因子原为0时，经过调整后，parent、subL和subLR的平衡因子都为0：

因此，我们根据subLR原平衡因子来调整旋转两次之后的平衡因子

为什么subLR的平衡因子不同，两次旋转后的平衡因子也不同呢？

当subLR的平衡因子为-1时，经过一次左单旋，subRL的左子树变为subR的右子树，由于subR的平衡因子为1，经过这次左旋后，其右子树的高度减一（少了subRL），此时subR的平衡因子变为0，且subRL变为subR的父亲节点。

当subLR变为subR的父亲节点时，其平衡因子变为 -2 ，这是因为subRL的原平衡因子为-1，经过一次左旋后，其左子树高度增加1（增加了subR），右子树高度不变，因此平衡因子变为 -2。

而parent的平衡因子不变，仍是 -2，这是因为在经过一次左单旋后，其右子树高度不变，虽其左孩子变为了subRL，但其高度未改变，因此parent的平衡因子不变

其过程更新过程如下图：

此时，我们假设subLR的左子树高度为m，由于其平衡因子为-2，则subLR的右子树高度为m-2，而parent的左子树高度为m+1，parent的右子树高度为m-1

当进行一次右旋后，由于subR的左右子树不变，因此其平衡因子仍为0

而parent变为subLR的右子树，且其左子树变为subLR的右子树，parent的右子树高度未改变，任为m - 1，而parent的左子树变为subLR的右子树，因此其高度变为m-2，则parent子树的高度为m-1，平衡因子变为 1

subLR的左子树为改变，高度任为m，而右子树变为以parent为根的子树，parent子树的高度为m-1，再加上parent，则为m，因此subLR的平衡因子变为0

当subLR的平衡因子为1和为0时也是同样的分析过程，大家可自行进行分析，这里就不再进行分析了

左右双旋代码：

//左右双旋
private void rotateLR(TreeNode parent){
    TreeNode subL = parent.left;
    TreeNode subLR = subL.right;
    //记录subLR平衡因子
    int bf = subLR.bf;
    rotateLeft(parent.left);//先左旋
    rotateRight(parent);//再右旋
    //修改平衡因子
    if(bf == -1){
        parent.bf = 1;
    }else if(bf == 1){
        subL.bf = -1;
    }
}

右左双旋

新节点插入较高右子树的左侧->右左双旋（先右单旋再左单旋）

右左双旋与左右双旋的情况类似

当新节点插入较高右子树的左侧时：

此时 parent.bf = 2, cur.bf = -1，仍要进行两次旋转，才能将以parent为根的子树调整为平衡的子树

此时要先对其进行右旋：

再对其进行左旋：

最后，我们再根据原subRL的平衡因子对平衡因子对其修改：

当subRL原平衡因子为1时，更新后的parent的平衡因子为-1

当subRL原平衡因子为-1时，更新后的subR的平衡因子为1

当subRL原平衡因子为0时，更新后parent、subR和subRL的平衡因子都为0

右左双旋的代码为：

//右左双旋
private void rotateRL(TreeNode parent){
    TreeNode subR = parent.right;
    TreeNode subRL = subR.left;
    //记录subRL的平衡因子
    int bf = subRL.bf;
    rotateRight(subR);//先右旋
    rotateLeft(parent);//再左旋
    //修改平衡因子
    if(bf == 1){
        parent.bf = -1;
    }else if(bf == -1){
        subR.bf = 1;
    }
}

由上述四种旋转过程可知：经过旋转后，都能使节点的平衡因子到达平衡，此时无需再向上调整，因此修改平衡因子的代码为：

        //修改平衡因子
        //平衡因子 = 右子树高度 - 左子树高度
        while (parent != null){
            //判断cur是parent的左还是右，从而决定其平衡因子是++还是--
            if(cur == parent.right){
                parent.bf++;
            }else {
                parent.bf--;
            }

            //检查当前平衡因子 判断是否符合条件（-1 0 1）
            if(parent.bf == 0){
                //已经平衡
                break;
            }else if(parent.bf == 1 || parent.bf == -1){
                //需要继续向上判断是否需要修改平衡因子
                cur = parent;
                parent = cur.parent;
            }else {
                //不平衡，需要进行旋转，使其平衡
                if(parent.bf == 2){//右树高，需要左旋，从而降低右树高度
                    if(cur.bf == 1){
                       //直接左旋
                        rotateLeft(parent);
                    }else {
                        //右左双旋
                        rotateRL(parent);
                    }

                }else {//左树高，需要右旋，从而降低左树高度
                    if(cur.bf == -1){
                        //直接右旋
                        rotateRight(parent);
                    }else {
                        //左右双旋
                        rotateLR(parent);
                    }
                }
                //旋转之后，平衡
                break;
            }
        }

AVL树的验证

在我们插入节点后，如何验证我们创建出的树是否是AVL树？

AVL树是高度平衡的二叉搜索树，其平衡因子的绝对值不超过1，能否通过节点的平衡因子来验证？

不能通过平衡因子来验证，因为平衡因子是我们通过计算得出的，若我们在计算时出现错误，那我们通过平衡因子验证的结果也是错误的（例如在左右双旋时，未在最后修改平衡因子，则此时计算的平衡因子不完全正确）

那么我们应该如何进行验证呢？

首先，AVL树也是二叉搜索树，二叉搜索树中序遍历的结果是有序的，因此我们可以通过中序遍历来验证

    public void inorder(TreeNode root) {
        if(root == null) return;
        inorder(root.left);
        System.out.print(root.val+" ");
        inorder(root.right);
    }

其次，AVL树节点的平衡因子绝对值不超过1，即左右子树的高度差不超过1，我们可以通过计算左右子树的高度差来判断树是否是高度平衡的，同时，通过比较计算出的高度差和平衡因子，我们也可以验证当前节点的平衡因子是否正确

    private int height(TreeNode root) {//计算子树高度
        if(root == null) return 0;
        int leftH = height(root.left);
        int rightH = height(root.right);

        return leftH > rightH ? leftH+1 : rightH+1;
    }

    public boolean isBalanced(TreeNode root) {
        if(root == null) return true;
        int leftH = height(root.left);
        int rightH = height(root.right);
        //判断平衡因子是否正确
        if(rightH-leftH != root.bf) {
            System.out.println("节点："+root.val+" 平衡因子异常");
            return false;
        }
        //判断左右子树高度差绝对值是否不超过1
        return Math.abs(leftH-rightH) <= 1
                && isBalanced(root.left)
                && isBalanced(root.right);
    }

完整代码：

public class AVLTree {
    static class TreeNode{
        public int val;//节点的值
        public int bf;//平衡因子
        public TreeNode left;//左孩子
        public TreeNode right;//右孩子
        public TreeNode parent;//父亲节点
        public TreeNode(int val){
            this.val = val;
        }
    }

    public TreeNode root;//根节点

    //节点的插入
    public boolean insert(int val) {
        TreeNode node = new TreeNode(val);
        //若根节点为空，则直接将插入为根节点
        if (root == null) {
            root = node;
            return true;
        }
        //根节点不为空，查找其插入位置
        TreeNode parent = null;
        TreeNode cur = root;
        while (cur != null) {
            if (cur.val < val) {
                parent = cur;
                cur = cur.right;
            } else if (cur.val > val) {
                parent = cur;
                cur = cur.left;
            } else {
                return false;//若已有该节点，则插入失败，直接返回false
            }
        }
        //将节点插入
        node.parent = parent;
        cur = node;

        //修改平衡因子
        //平衡因子 = 右子树高度 - 左子树高度
        while (parent != null){
            //判断cur是parent的左还是右，从而决定其平衡因子是++还是--
            if(cur == parent.right){
                parent.bf++;
            }else {
                parent.bf--;
            }

            //检查当前平衡因子 判断是否符合条件（-1 0 1）
            if(parent.bf == 0){
                //已经平衡
                break;
            }else if(parent.bf == 1 || parent.bf == -1){
                //需要继续向上判断是否需要修改平衡因子
                cur = parent;
                parent = cur.parent;
            }else {
                //不平衡，需要进行旋转，使其平衡
                if(parent.bf == 2){//右树高，需要左旋，从而降低右树高度
                    if(cur.bf == 1){
                       //直接左旋
                        rotateLeft(parent);
                    }else {
                        //先右旋，再左旋
                        rotateRL(parent);
                    }

                }else {//左树高，需要右旋，从而降低左树高度
                    if(cur.bf == -1){
                        //直接右旋
                        rotateRight(parent);
                    }else {
                        //先左选，再右旋
                        rotateLR(parent);
                    }
                }
                //经过旋转之后，就平衡
                break;
            }
        }
        return true;
    }
    //左单旋
    private void rotateLeft(TreeNode parent){
        TreeNode subR = parent.right;
        TreeNode subRL = subR.left;

        parent.right = subRL;
        if(subRL != null){//只有当subRL不为空时，才能修改其父亲节点
            subRL.parent = parent;
        }

        subR.left = parent;
        //在修改parent父亲节点前将其进行记录，以便后续修改subR的父亲节点
        TreeNode pParent = parent.parent;
        parent.parent = subR;
        //判断subR是否被修改为根节点
        if(parent == root){
            root = subR;
            root.parent = null;
        }else {
            //判断是其左子树还是右子树
            if(pParent.left == parent){
                pParent.left = subR;
            }else{
                pParent.right = subR;
            }
            subR.parent = pParent;
        }
        //修改平衡因子
        subR.bf = 0;
        parent.bf = 0;
    }

    //右单旋
    private void rotateRight(TreeNode parent){
        TreeNode subL = parent.left;
        TreeNode subLR = subL.right;

        parent.left = subLR;
        if(subLR != null){//只有当subLR不为空时，才能修改其父亲节点
            subLR.parent = parent;
        }

        subL.right = parent;
        //在修改parent的父亲节点时，必须先记录其父亲节点，以便修改subL的父亲节点
        TreeNode pParent = parent.parent;
        parent.parent = subL;
        //判断subL是否被修改为根节点
        if(parent == root){
            root = subL;
            root.parent = null;
        }else {
            subL.parent = pParent;
            //判断是左子树还是右子树
            if(pParent.left == parent){
                pParent.left = subL;
            }else {
                parent.right = subL;
            }
        }
        //修改平衡因子
        subL.bf = 0;
        parent.bf = 0;
    }

    //左右双旋
    private void rotateLR(TreeNode parent){
        TreeNode subL = parent.left;
        TreeNode subLR = subL.right;
        //记录subLR平衡因子
        int bf = subLR.bf;
        rotateLeft(parent.left);//先左旋
        rotateRight(parent);//再右旋
        //修改平衡因子
        if(bf == -1){
            parent.bf = 1;
        }else if(bf == 1){
            subL.bf = -1;
        }
    }

    //右左双旋
    private void rotateRL(TreeNode parent){
        TreeNode subR = parent.right;
        TreeNode subRL = subR.left;
        //记录subRL的平衡因子
        int bf = subRL.bf;
        rotateRight(subR);//先右旋
        rotateLeft(parent);//再左旋
        //修改平衡因子
        if(bf == 1){
            parent.bf = -1;
        }else if(bf == -1){
            subR.bf = 1;
        }
    }

    //验证
    public void inorder(TreeNode root) {//中序遍历
        if (root == null) return;
        inorder(root.left);
        System.out.print(root.val + " ");
        inorder(root.right);
    }

    private int height(TreeNode root) {//计算子树高度
        if(root == null) return 0;
        int leftH = height(root.left);
        int rightH = height(root.right);

        return leftH > rightH ? leftH+1 : rightH+1;
    }

    public boolean isBalanced(TreeNode root) {
        if(root == null) return true;
        int leftH = height(root.left);
        int rightH = height(root.right);
        //判断平衡因子是否正确
        if(rightH-leftH != root.bf) {
            System.out.println("节点："+root.val+" 平衡因子异常");
            return false;
        }
        //判断左右子树高度差绝对值是否不超过1
        return Math.abs(leftH-rightH) <= 1
                && isBalanced(root.left)
                && isBalanced(root.right);
    }
}

三、AVL树的性能分析

AVL树是一颗绝对平衡的二叉搜索树，要求每个节点的左右子树高度差的绝对值都不超过1，这样能够保证查询时的高效，即查询的时间复杂度为O（ $log_{2}N$ ）。但当对AVL树进行一些结构的修改操作时，性能就会比较低下（在插入时为了保持其绝对平衡，就需要进行旋转）。因此，若需要一种查询高效且有序的数据结构，且数据的个数为静态的（不改变），可以考虑使用AVL树，但若是其经常进行修改，就不太适合使用AVL树。