• 高级数据结构——AVL树

    目录

    AVL树

    AVL树定义

    AVL树又被称为是高度平衡的二叉搜索树,一棵AVL树的任意左右子树的高度差不超过1,且任意一个节点大于该节点的左子节点的值,小于该节点的右子节点的值在这里插入图片描述

    AVL树插入实现

    首先AVL树是在二叉搜索树的基础上保证高度平衡的一棵树,因此AVL树的插入是基于二叉搜索树的插入,而AVL树插入的难点就在于如何保证高度平衡,保证高度平衡的原理就是每插入一个节点就通过左旋,右旋,左右双旋的方式调整树的结构.因此我们首先介绍左旋,右旋,左右双旋的实现

    AVL树节点实现

     static class TreeNode{
  	 public int val;   // 节点的值
     public TreeNode left; // 节点的左子树
     public TreeNode right; // 节点的右子树 
     public TreeNode parent; // 节点的父母节点
     public int bf; // 右树高度和左树高度的差(右-左),当然也可以设置为左-右
     public TreeNode(int val){
         this.val = val;
     }
 }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10

    左旋实现

    首先需要考虑什么情况下需要左旋,一定是左树的高度要大于右树的高度+1
    在这里插入图片描述

    如图,对于根节点为3的这个子树,其右子树高度为2,而左子树高度为0,对于这样一棵树,很明显需要进行左旋.
    现在我们考虑一个问题,对于上述这棵树而言,节点为4的左右子节点是否能够同时存在?答案是否定的,原因是在插入每一个节点之后,我们都需要去判断是否有树要发生旋转,因此当插入4节点的左右任意一个节点后3这棵树就需要发生旋转. 下面我们来考虑左旋的代码如何实现
    首先最好的方式是不影响4这棵树的左右子树的结构(因为已经达到了平衡),然后将节点3移到树4的左子树上
    在这里插入图片描述
    如图,通过这种方式我们就使原来不平衡的子树平衡

     private void rotateLeft(TreeNode p){
     TreeNode pp = p.parent; //获取待调整节点的父亲
      TreeNode subR = p.right; //获取待调整节点的右子树根节点
      TreeNode subRL = subR.left; //获取待调整节点的右子树的左树根节点
      p.right = subRL; 
      //这段代码实际上是不会发生的,因为subRL正常情况下是null,但还是将这段逻辑写完整比较好
      if(subRL != null){
          subRL.parent = p;
      }
      //对调p和subR的父子关系
      subR.left = p;
      p.parent = subR;
      //设置pp和新的'p'(原来的subR)之间的父子关系
      if(pp != null){
          if(pp.left == p){
              pp.left = subR;
              subR.parent = pp;
          }else if(pp.right == p){
              pp.right = subR;
              subR.parent = pp;
          }
      }else{
          subR.parent = null;
          root = subR;
      }
      // 最后更新subR的p的右左子树高度差bf
      subR.bf = 0;
      p.bf = 0;
  }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29

    右旋实现

    上面介绍了左旋之后,右旋就上反过来即可,即left改为right,right改为left
    在这里插入图片描述

     private void rotateRight(TreeNode p){
 		// 和左旋逻辑一致,就是left变为right,right变为left
        TreeNode pp = p.parent;
        TreeNode newRoot = p.left;
        p.left = newRoot.right;
        if(p.left != null){
            p.left.parent = p;
        }
        newRoot.right = p;
        p.parent = newRoot;
        if(pp != null){
            if(pp.left == p){
                pp.left = newRoot;
                newRoot.parent = pp;
            }else if(pp.right == p){
                pp.right = newRoot;
                newRoot.parent = pp;
            }
        }else{
            newRoot.parent = null;
            root = newRoot;
        }
        newRoot.bf = 0;
        p.bf = 0;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25

    左右双旋实现

    左右双旋的含义就是先左旋,然后再右旋,那么什么情况下进行左右双旋呢?其实很好想,先进行的旋转肯定是调整的子树的结构,将待调整树通过左旋调整为整个树右旋的情况,然后再对整个树右旋
    在这里插入图片描述
    针对上图,就是对根节点为1的树进行左旋,然后在针对节点为3的树进行右旋
    这里需要讨论一个问题:就是对更新后的树的bf的更新
    在这里插入图片描述
    在这里插入图片描述
    针对不同的subRL的bf需要单独判断平衡后的bf更新

    private void rotateLR(TreeNode p){
        TreeNode subL = p.left;
        TreeNode subLR = subL.right;
        int bf = subLR.bf;

        rotateLeft(p.left);
        rotateRight(p);
        //bf为0时旋转后的平衡因子均为0
        if(bf == -1){
            subL.bf = 0;
            subLR.bf = 0;
            p.bf = 1;
        }else if(bf == 1){
            subL.bf = -1;
            subLR.bf = 0;
            p.bf = 0;
        }
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18

    右左双旋实现

    右左双旋和左右双旋的思路一致,也是left变right,right变left,然后也重新针对subRL的bf进行讨论

     private void rotateRL(TreeNode p){
        TreeNode subR = p.right;
        TreeNode subRL = subR.left;
        int bf = subRL.bf;

        rotateRight(p.right);
        rotateLeft(p);
        if(bf == 1){
            subRL.bf = 0;
            subR.bf = 0;
            p.bf = -1;
        }else if(bf == -1){
            subRL.bf = 0;
            subR.bf = 1;
            p.bf = 0;
        }
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17

    AVL树插入实现

    在讨论了如何平衡AVL树后,AVL树的插入就可以先像二叉搜索树一样先将节点插入到AVL树中,然后对AVL树中的叶子节点到根节点进行树结构的调整

      public boolean insert(int val){
        if(root == null){
            root = new TreeNode(val);
            return true;
        }
        TreeNode p = null;
        TreeNode cur = root;
        // 将节点按照顺序插入到叶子节点中
        while(cur != null){
            if(cur.val < val){
                p = cur;
                cur = cur.right;
            }else if(cur.val == val){
                // AVL树中不应该存在两个值相同的节点
                return false;
            }else{
                p = cur;
                cur = cur.left;
            }
        }
        TreeNode node = new TreeNode(val);
        if(p.val < val){
            p.right = node;
        }else if(p.val > val){
            p.left = node;
        }
        node.parent = p;
        cur = node;
        // 从叶子结点到根节点对AVL树进行旋转调整
        while(p != null){
            if(p.right == cur){
                p.bf++;
            }else if(p.left == cur){
                p.bf--;
            }
            if(p.bf == 0){
                break;
            }else if(p.bf == 1 || p.bf == -1){
                //继续向上寻找需要旋转的子树
                cur = p;
                p = p.parent;
            }else{
                //发生旋转
                if(p.bf == 2){
                    if(cur.bf == 1){
                        //左单旋
                        rotateLeft(p);
                    }else if(cur.bf == -1){
                        //右左双旋
                        rotateRL(p);
                    }
                }else if(p.bf == -2){
                    if(cur.bf == 1){
                        //左右双旋
                        rotateLR(p);
                    }else if(cur.bf == -1){
                        //右单旋
                        rotateRight(p);
                    }
                }
                break;
            }
        }
        return true;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65

    AVL树删除实现

    AVL树的删除是基于二叉搜索树的删除,然后调整AVL树的结构以达到高度平衡.而高度平衡的方法已经在AVL树的插入中介绍过.因此这里重点介绍二叉搜索树的删除.
    二叉树的删除的关键是找替罪羊,在找到替罪羊后,将替罪羊删除掉,然后将替罪羊节点的值赋给本来要删除的节点.而这个替罪羊首先必须是叶子结点(叶子结点的删除直接置为null即可),然后必须是相邻的节点,因此替罪羊必须是带删除节点的左子树的最右下节点(前驱节点)或右子树的最左下节点(后置节点).在这里插入图片描述

    // 获得待删除节点的前驱节点
private TreeNode getPrevNode(TreeNode p){
        if(p == null){
            return p;
        }
        TreeNode cur = p;
        if(cur.left != null){
        	// 得到但删除节点左树的最右下节点
            cur = cur.left;
            while(cur.right != null){
                cur = cur.right;
            }
            return cur;
        }else{
        	// 实际上在删除的过程中不会让带吗走到这个代码块中,所以这一部分可以不管
            TreeNode parent = cur.parent;
            while(parent != null && parent.left == cur){
                cur = parent;
                parent = cur.parent;
            }
            return parent;
        }
    }
   	// 获得待删除节点的后继节点
    private TreeNode getNextNode(TreeNode p){
        if(p == null){
            return null;
        }
        TreeNode cur = p;
        if(cur.right != null){
        	// 获取带删除节点的右子树的最左下节点
            cur = cur.right;
            while(cur.left != null){
                cur = cur.left;
            }
            return cur;
        }else{
            TreeNode parent = cur.parent;
            while(parent != null && parent.right == cur){
                cur = parent;
                parent = cur.parent;
            }
            return parent;
        }
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45

    在找到替罪羊节点后,我们就可以进行AVL树的删除

     public boolean remove(TreeNode p){
 		// getNode(p)获得待删除节点
        TreeNode replaced = getNode(p);
        if(replaced == null){
            return false;
        }
        TreeNode removed = replaced;
        if(removed.left != null && removed.right != null){
        	// 之所以说在找替罪羊结点时不会走到else语句块的原因就在于删除方法调用替罪羊方法的前提是待删除节点的左右子树均不为空.
        	// 获取左树高度和右树高度
            int leftHeight = getHeight(removed.left);
            int rightHeight = getHeight(removed.right);
            // 这里需要判断一下左右树的高度来决定替罪羊是找前驱节点还是后继节点,因为删除意味着可能导致某一侧树的高度降低,所有替罪羊尽可能找在树高的一侧
            if(leftHeight > rightHeight){
                removed = getPrevNode(removed);
            }else{
                removed = getNextNode(removed);
            }
        }
        TreeNode moved = null;
        // 获取替罪羊节点的子树结构:至少有一侧为空
        if(removed.left != null){
            moved = removed.left;
        }else{
            moved = removed.right;
        }
        // 获取替罪羊节点的父亲节点
        TreeNode parent = removed.parent;
		
		// 将替罪羊父亲节点和替罪羊的子树节点连接起来
        if(moved != null){
            moved.parent = parent;
        }
        if(parent == null){
            root = moved;
            return true;
        }else if(parent.left == removed){
            parent.left = moved;
        }else{
            parent.right = moved;
        }
		// 将替罪羊节点的值赋给待删除节点,至此删除部分完成
        if(removed.val != replaced.val){
            replaced.val = removed.val;
        }
        // 调整删除后树的结构,以保证高度平衡
        adjustStructure(parent);
        return true;
    }
     private void adjustStructure(TreeNode p){
        do {
        	// 获取左右树高度来判断具体怎么旋转
            int leftHeight = getHeight(p.left);
            int rightHeight = getHeight(p.right);
            // if语句中的逻辑和AVL树插入代码中的旋转逻辑一致
            if(Math.abs(leftHeight - rightHeight) >= 2){
                if(leftHeight > rightHeight){
                    TreeNode left = p.left;
                    if(getHeight(left.left) > getHeight(left.right)){
                        rotateRight(p);
                    }else{
                        rotateLR(p);
                    }
                }else{
                    TreeNode right = p.right;
                    if(getHeight(right.right) > getHeight(right.left)){
                        rotateLeft(p);
                    }else{
                        rotateRL(p);
                    }
                }
                // 注意树的结构如果发生改变,原来的父亲和儿子节点的关系发生对调,所以原来的父亲节点现在的关系其实是儿子,所以p.parent.parent才是爷爷节点
                p = p.parent.parent;
                continue;
            }
     		// 如果树的结构没有发生改变那么p的关系还是父亲,p.parent就是父亲
            p = p.parent;
        }while(p != null);
    }
    private  int getHeight(TreeNode p){
        if(p == null){
            return 0;
        }
        return Math.max(getHeight(p.left),getHeight(p.right)) + 1;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85

    AVL树优缺点

    AVL树优点:AVL树查找数据的时间复杂度为O(logN),且不会因为数据流本身有序而退化成O(N)(因为AVL树高度平衡)
    AVL树缺点:由于AVL树要保证高度平衡,因此在向AVL树中插入节点或删除节点时有时候会导致整个树结构发生改变.所以AVL树的插入和删除非常麻烦.

    总结

    AVL树可以是专门为了查找数据而生,它适用于海量静态数据的查询的场景,而不适合频繁插入删除数据的场景.

  • 相关阅读:
    04 # 手写 apply
    MCE | 神经退行性疾病——比癌症更残忍
    2022年11月华南师范大学自考本科计算机信息管理系统加考实践题目
    ImmunoChemistry艾美捷自噬试验，红色解决方案
    离线语音识别PocketSphinx(一)
    装机必备的浏览器推荐，干净好用，选这4款不会出错
    C#/.NET/.NET Core优秀项目和框架2023年12月简报
    Kubernetes 100个常用命令！点赞收藏一键三连
    第5章：程序控制结构
    基于SSH开发教师管理系统
  • 原文地址：https://blog.csdn.net/weixin_52477733/article/details/126711964