二叉搜索树之AVL树

左手的ㄟ右手 2024-03-27 15:34 3阅读 0赞

### AVL树的概念 ###

二叉搜索树虽可以缩短查找的效率，但**如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺**

**序表中搜索元素，效率低下**。因此，两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年 发明了一种

解决上述问题的方法：**当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过**

**1(需要对树中的结点进行调整)**，即可降低树的高度，从而减少平均搜索长度。

一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树：

**它的左右子树都是AVL树**

**左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)**

**平衡因子bf = 右子树高度 - 左子树高度**

**如果一棵二叉搜索树是高度平衡的，它就是AVL树。如果它有n个结点，其高度可保持在O(log\_2 n)，搜索时间**

**复杂度O(log\_2 n)**。

### AVL树的插入 ###

AVL树节点在定义时维护一个平衡因子，具体节点定义如下：

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;
            }
        }

AVL树的插入过程可以分为两步：

1. **按照二叉搜索树的方式插入新节点**

2. **调整节点的平衡因子**

**按照二叉搜索树的方式插入新节点：**

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){
                    return false;
                }else {
                    parent = cur;
                    cur = cur.left;
                }
            }
    
            if (parent.val < val){
                parent.right = node;
            }else {
                parent.left = node;
            }
    
            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 {
                            //cur.bf == -1
                            rotateRL(parent);
                        }
                    }else {
                        //parent.bf == -2 左树高-》需要降低左树的高度
                        if (cur.bf == -1){
                            //右单旋
                            rotateRight(parent);
                        }else {
                            //cur.bf == 1
                            //左右双旋
                            rotateLR(parent);
                        }
                    }
                    //上述代码走完就已经平衡了
                    break;
                }
            }

##### **左单旋-插入位置在较高右子树的右侧：（parent.bf = 2, cur.bf = 1）** #####

![90793d8938474447b8f6bcec7ac42a56.png][]

//左单旋
        private void rotateLeft(TreeNode parent) {
            TreeNode subR = parent.right;
            TreeNode subRL= subR.left;
            parent.right = subRL;
            subR.left = parent;
            if (subRL != null){
                subRL.parent = parent;
            }
            TreeNode pParent = parent.parent;
            parent.parent = 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）** #####

![903362d0d8fe46d2b08d4faad1ecbb3d.png][]

//右单旋
        private void rotateRight(TreeNode parent) {
            TreeNode subL = parent.left;
            TreeNode subLR = subL.right;
    
            parent.left = subLR;
            subL.right = parent;
            if (subLR != null){
                subLR.parent = parent;
            }
            //必须先记录当前的父亲的父亲节点
            TreeNode pParent = parent.parent;
            parent.parent = subL;
            //检查当前节点是不是根节点
            if (parent == root){
                root = subL;
                root.parent = null;
            }else {
                //不是根节点，判断这颗子树是左子树还是右子树
                if (pParent.left == parent){
                    pParent.left = subL;
                }else {
                    pParent.right = subL;
                }
                subL.parent = pParent;
            }
            subL.bf = 0;
            parent.bf = 0;
        }

##### **左右双旋-插入位置在较高左子树的右侧：（parent.bf = -2, cur.bf = 1）** #####

![210adcd01759480fa2e713c6422296d8.png][]

//左右双旋
        private void rotateLR(TreeNode parent) {
            TreeNode subL = parent.left;
            TreeNode subLR= subL.right;
            int bf = subLR.bf;
    
            rotateLeft(parent.left);
            rotateRight(parent);
    
            if (bf == -1){
                subL.bf = 0;
                subLR.bf = 0;
                parent.bf = 1;
            }else if (bf == 1){
                subL.bf = -1;
                subLR.bf = 0;
                parent.bf = 0;
            }
        }

##### **右左双旋-插入位置在较高右子树的左侧：（parent.bf = 2, cur.bf = -1）** #####

![36355c89b039493b9953d956c7099899.png][]

private void rotateRL(TreeNode parent) {
            TreeNode subR = parent.right;
            TreeNode subRL = subR.left;
            int bf = subRL.bf;
            rotateRight(parent.right);
            rotateLeft(parent);
    
            if (bf == 1){
                subR.bf = 0;
                subRL.bf = 0;
                parent.bf = -1;
            }else if (bf == -1){
                subR.bf = 1;
                subRL.bf = 0;
                parent.bf = 0;
            }
        }

##### AVL树插入操作的完整代码+验证代码 #####

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){
                    return false;
                }else {
                    parent = cur;
                    cur = cur.left;
                }
            }
    
            if (parent.val < val){
                parent.right = node;
            }else {
                parent.left = node;
            }
    
            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 {
                            //cur.bf == -1
                            rotateRL(parent);
                        }
                    }else {
                        //parent.bf == -2 左树高-》需要降低左树的高度
                        if (cur.bf == -1){
                            //右单旋
                            rotateRight(parent);
                        }else {
                            //cur.bf == 1
                            //左右双旋
                            rotateLR(parent);
                        }
                    }
                    //上述代码走完就已经平衡了
                    break;
                }
            }
            return true;
        }
    
        private void rotateRL(TreeNode parent) {
            TreeNode subR = parent.right;
            TreeNode subRL = subR.left;
            int bf = subRL.bf;
            rotateRight(parent.right);
            rotateLeft(parent);
    
            if (bf == 1){
                subR.bf = 0;
                subRL.bf = 0;
                parent.bf = -1;
            }else if (bf == -1){
                subR.bf = 1;
                subRL.bf = 0;
                parent.bf = 0;
            }
        }
    
        //左右双旋
        private void rotateLR(TreeNode parent) {
            TreeNode subL = parent.left;
            TreeNode subLR= subL.right;
            int bf = subLR.bf;
    
            rotateLeft(parent.left);
            rotateRight(parent);
    
            if (bf == -1){
                subL.bf = 0;
                subLR.bf = 0;
                parent.bf = 1;
            }else if (bf == 1){
                subL.bf = -1;
                subLR.bf = 0;
                parent.bf = 0;
            }
        }
    
        //左单旋
        private void rotateLeft(TreeNode parent) {
            TreeNode subR = parent.right;
            TreeNode subRL= subR.left;
            parent.right = subRL;
            subR.left = parent;
            if (subRL != null){
                subRL.parent = parent;
            }
            TreeNode pParent = parent.parent;
            parent.parent = 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;
            subL.right = parent;
            if (subLR != null){
                subLR.parent = parent;
            }
            //必须先记录当前的父亲的父亲节点
            TreeNode pParent = parent.parent;
            parent.parent = subL;
            //检查当前节点是不是根节点
            if (parent == root){
                root = subL;
                root.parent = null;
            }else {
                //不是根节点，判断这颗子树是左子树还是右子树
                if (pParent.left == parent){
                    pParent.left = subL;
                }else {
                    pParent.right = subL;
                }
                subL.parent = pParent;
            }
            subL.bf = 0;
            parent.bf = 0;
        }
        //中序遍历
        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 leftHeight = height(root.left);
            int rightHeight = height(root.right);
            return leftHeight > rightHeight ? leftHeight+1 : rightHeight+1;
        }
    
        public boolean isBalanced(TreeNode root){
            if (root == null)return true;
            int leftHeight = height(root.left);
            int rightHeight = height(root.right);
    
            if (rightHeight-leftHeight != root.bf){
                System.out.println("这个节点："+root.val + "有异常!");
                return false;
            }
    
            return Math.abs(leftHeight-rightHeight) <= 1
                    && isBalanced(root.left)
                    && isBalanced(root.right);
        }
    }

### AVL树的删除 ###

因为AVL树也是二叉搜索树，可按照二叉搜索树的方式将节点删除，然后再更新平衡因子，只不过与删除不

同的是，删除节点后的平衡因子更新，最差情况下一直要调整到根节点的位置。

1、找到需要删除的节点

2、按照搜索树的删除规则删除节点--参考[https://blog.csdn.net/crazy\_xieyi/article/details/127627063][https_blog.csdn.net_crazy_xieyi_article_details_127627063]

3、更新平衡因子，如果出现了不平衡，进行旋转。--单旋，双旋

### AVL树的性能分析 ###

AVL树是一棵绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过1，这样可以保证查询

时高效的时间复杂度，即 。但是如果要对AVL树做一些结构修改的操作，性能非常低下，比如：插入时要

维护其绝对平衡，旋转的次数比较多，更差的是在删除时，有可能一直要让旋转持续到根的位置。因此：如果需**要**

**一种查询高效且有序的数据结构，而且数据的个数为静态的(即不会改变)，可以考虑AVL树，但一个结构经常修**

**改，就不太适合。**

[90793d8938474447b8f6bcec7ac42a56.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/98aef0556b2b4fc0b1f7f71ac92db7a8.png
[903362d0d8fe46d2b08d4faad1ecbb3d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/42f859a1410a43ddb5efe645590729fa.png
[210adcd01759480fa2e713c6422296d8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/bf4a9d96f3694715933b98c41eeb8133.png
[36355c89b039493b9953d956c7099899.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/1b6a1308330b4d25b09c1672bef76519.png
[https_blog.csdn.net_crazy_xieyi_article_details_127627063]: https://blog.csdn.net/crazy_xieyi/article/details/127627063