二叉搜索树之AVL树

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树节点在定义时维护一个平衡因子，具体节点定义如下：

java">java">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. 调整节点的平衡因子

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

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

调整节点的平衡因子

java">java">//平衡因子的修改
        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）

java">java">  //左单旋
    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）

java">java">//右单旋
    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）

java">java">  //左右双旋
    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）

java">java">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树插入操作的完整代码+验证代码

java">java">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

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

AVL树的性能分析

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

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

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

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

改，就不太适合。