数据结构 AVL树概念以及实现插入的功能(含Java代码实现)

为啥要有avl树

avl树是在二叉搜索树下的一种进阶形式,是为了防止二叉搜索树在极端情况下产生的链表化的场景,从而在二叉搜索树的基础上,加上了某些条件来阻止这种极端情况的产生,但不是保证完全平衡,而是放开了一定的条件,使得这种情况不那么难以满足.(条件:左右子树的高度差的绝对值不大于1)?,我们在发现大于1的时候可以使用左右旋转的方式来调整数的形态,从而保证了查找的时候有近似于O(logN)的性能.

缺点:

当然,有得必有失,这样也带来了一定的损耗:浪费了空间来保存新的变量,每次插入都判断是否满足条件,这样导致了插入的效率变低,这也使得这种二叉树不适合连续多次的插入和修改数据.

如果我们需要持续多次的插入数据,那么也有更进一步的数据结构 --- 红黑树?

AVL树的定义

平衡因子

定义为每个节点的左子树和右子树的高度差(左减去右,右减去左都可以表示)

本文使用右减左表示高度差的定义

例如空树的高度差就是0,这就代表着平衡,

当高度差达到-1,就表示左子树高了,但是还在允许的范围之间,无需调整

当高度差达到1,就代表右子树高了,也在允许的范围之内

当左右子树的高度差超过这个范围(绝对值大于2的时候),那么我们就得需要实现左右旋转来满足这种结构的查找效率.

节点代码结构

static class TreeNode{
        public int val;
        public int bf;//balance factor 平衡因子
        public TreeNode left;//左孩子
        public TreeNode right;//右孩子
        public TreeNode parent;//父节点

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

实现插入功能

总体思路:

1.按照平衡二叉树的比较方式去寻找到应该插入在的节点

2.插入完了修改一下bf(平衡因子)的值

3.判断是否平衡

3.1 bf = 0直接跳出循环即可

3.2 bf = 1 或 bf = -1就继续向上寻找

3.3 bf = 2考虑左旋右旋修改avl树的结构

以下会包含四种失衡以及解决方案

1.LL类型

我们能很容易发现这种不平衡式因为左子树太深而导致的,此时我们要使用右旋来保证结构的正确.

具体步骤就是

1.将subL作为根节点

2.subLR作为parent的左孩子

3.parent作为subL的右孩子

此时我们发现subL和parent的平衡因子都会变成0

2.RR类型

此时我们明显发现右子树的深度要高于左子树两个节点

此时我们就需要进行左旋来调整整体结构的状态

整体步骤与之前类似

1.将subR提出来当根节点

2.subRL作为parent的右子树

3.parent作为subR的左子树

3.RL类型

这个你可以理解是在右子树深的情况下子树是左子树比较深,而前面的方式是左右子树的子树也是呈现同一趋势的.

执行方式

1.先对右子树进行一次右旋,这时候我们发现总体又一次呈现了RR型状态

左旋即可达成平衡的目标

这里如果我们插入的是节点值是55又会有不一样的平衡值

4.LR类型

执行方式也是一样的,我们对左子树进行左旋,再对整体进行右旋即可

这里我直接给出操作形式,其实这里插入的是25也会有另一种结果,在代码中有所体现,读者可自行画图推导

完整avl树插入代码?

public class AVLTree {
    static class TreeNode{
        public int val;
        public int bf;//balance factor 平衡因子
        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 cur = root;
        TreeNode parent = null;
        while(cur != null){
            if(val < cur.val){
                parent = cur;
                cur = cur.left;
            }else if(val == cur.val){
                return false;
            }else{
                parent = cur;
                cur = cur.right;
            }
        }
        if(parent.val>val){
            parent.left = node;
        }else{
            parent.right = node;
        }
        node.parent = parent;
        //调节负载因子
        cur = node;
        //负载因子的修改
        while(parent != null){
            //先看cur是parent的左还是右
            //平衡因子为右 - 左
            if(cur == parent.right){
                //右树高,因子++
                parent.bf++;
            }else{
                //左树高
                parent.bf--;
            }
            //检查平衡因子变化完了是多少
            if(parent.bf == 0){
                break;
            }else if(parent.bf == 1 || parent.bf == -1){
                //继续向上判断修改平衡因子
                //因为等于1和-1只代表当前子树平衡
                cur = parent;
                parent = parent.parent;
            }else{
                //2或者-2的情况,考虑左旋右旋
                if(parent.bf == 2){
                    if(cur.bf == 1){
                        rotateLeft(parent);
                    }else{
                        //-1的情况
                        rotateRL(parent);
                    }
                }else{
                    //-2的情况
                    if(cur.bf == 1){
                        rotateLR(parent);

                    }else{
                        //-1的情况
                        rotateRight(parent);
                    }
                }
                break;
            }
        }
        return true;
    }

   //左单旋
    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(root == parent){
            root = subR;
            root.parent = null;
        }else{
            if(pParent.left == parent){
                pParent.left = subR;
            }else{
                pParent.right = subR;
            }
            subR.parent = pParent;
        }
        subR.bf = 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{
            //此刻的parent也不一定是根节点,还是有左右树的
            if(pParent.left == parent){
                pParent.left = subL;
            }else{
                pParent.right = subL;
            }
            subL.parent = pParent;
        }
        subL.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 rotateRL(TreeNode parent) {
        TreeNode subR = parent.right;
        TreeNode subRL = subR.left;
        int bf = subRL.bf;
        rotateRight(parent.right);
        rotateLeft(parent);
        if(bf == 1){
            parent.bf = -1;
            subR.bf = 0;
            subRL.bf = 0;
        }else if(bf == -1){
            parent.bf = 0;
            subR.bf = 0;
            subRL.bf = 1;
        }
    }


    //验证当前树
    public void inorder(TreeNode root){
        if(root == null){
            return;
        }
        inorder(root.left);
        System.out.println(root.val+" ");
        inorder(root.right);
    }

    private int height(TreeNode root){
        if(root == null){
            return 0;
        }
        int left = height(root.left);
        int right = height(root.right);
        return Math.max(left+1,right+1);
    }
    public boolean isBalanced(TreeNode root){
        if(root == null){
            return true;
        }
        int left = height(root.left);
        int right = height(root.right);
        //判断平衡因子是否有问题
        if (right-left != root.bf){
            System.out.println("这个节点" + root.val +"平衡因子异常");
            return false;
        }
        return Math.abs(left-right)<=1&&
                isBalanced(root.left) && isBalanced(root.right);
    }

    public static void main(String[] args) {
        int[] arr= new int[]{4, 2, 6, 1, 3, 5, 15, 7, 16,14};
        AVLTree avl = new AVLTree();
        for (int i = 0; i < arr.length; i++) {
            avl.insert(arr[i]);
        }
        System.out.println(avl.isBalanced(avl.root));
    }
}