精华内容
下载资源
问答
  • 2022-01-03 19:47:25

      非平衡二叉树转化为平衡二叉树

    非平衡树的六种形态(第一次出现不平衡就转化平衡树,不会出现多处不平衡的现象)

    左撇(可以忽略)

    右撇(可以忽略)

    LL

    LR

    RR 

    RL

    注意:

    1、出现LL时,以第一个L为旋转点,转化成平衡树

    2、出现LR时,以R为旋转点,先旋转成LL,再以第一个L为旋转点,转化成平衡树

    3、出现LR时,如果失衡点有左子节点,则无法直接旋转,需要先进行失衡点与左子节点的小旋转,然后按照上述方式,做后续旋转

    4、LR与RL对称,LL与RR对称,理解其中两种,就理解相对称的其余两种

    更多相关内容
  • 【数据结构】平衡二叉树怎么自己画?        是什么?     要了解平衡二叉树,先得了解什么是二叉树? 二叉树定义: 在计算机中,二叉树是每一个节点最多有两...


    【数据结构】平衡二叉树怎么自己画?

          

    是什么?

        要了解平衡二叉树,先得了解什么是二叉树?


    二叉树定义:

    在计算机中,二叉树是每一个节点最多有两个子树的结构。通常子树被称作“左子树(left subtree)”“右子树(right subtree)”. 二叉树常被用于实现二叉树查找和二叉堆。


    什么是平衡二叉树:

         平衡二叉树(Balance Binary Tree)是二叉树的一个进化体,是一个引入平衡概念的二叉树。与1962年G.M Adelson-Velsky 和E.M.Landis 发明的,也叫AVL树。 平衡二叉树是对于每一个节点来说,他的左右子树高度差不能超过1, 如果插入或者删除一个节点,使得高度之差大于1,就要进行节点之间的旋转,将二叉树重新维持在一个平衡的状态。

       

     

    平衡二叉树是干什么的?

         平衡二叉树很好的解决了二叉树退化成链表的问题,把插入,查找,删除的时间复杂度最好情况和最坏情况都维持在O(LogN)。但是频繁的旋转是插入和删除牺牲掉O(LogN)左右的时间,不过相对于二叉查找树来说,时间上是稳定了许多。

     

    怎么画一棵平衡二叉树树(重点突出)

       今天小编想和大家分享的重点是给你几个数,到底怎么画这课平衡二叉树来?

         原则:

         1.将题目中已给的数,依次按二叉排序树的原理将树画下来(左子树值小于根值,右子数值大于根值,整棵树的左右子树值也满足二叉排序树规则。)

         2,每一次插入一个数值,都必须满足二叉排序树规则且左右子树高度只差不能查过1, 超过1 就要旋转。

    怎么旋转呢?

    (1)首先找平衡因子,平衡因子看哪个值先为-2(那个根左右子树或子树高度差超过1,这个根的平衡因子就为-2并且如果有两个平衡因子-2的,旋转那个靠近插入值那边的那个根);

    重要:(2)在刚刚插入的数值中,在同一分支中连续三个数旋转;注意,是沿着这三个数的中位数旋转,如果中位数不在中间,就将交换将中位数放在中间后进行交互后在旋转。

     

    下面我来看看实例:

    (1)2010年计算机专业统考的一题关于平衡二叉树

    原题:在下图所示的平衡二叉树中,插入关键字48后得到一棵新平衡二叉树,在新平衡二叉树中,关键字37所在节点的左边、右子结点中保存的关键字分别是

      

    (2)分别为2,1,0,3,4,5,6,9,8,7的10个结点来构造平衡二叉树,构造平衡二叉树过程。


    (3)27,16,73,35,42构造平衡二叉树


    (4)对序列(49,38,65,97,76,13,27,50)构造平很二叉树,并给出构造过程?

     

    解答:

    (1)  插入48,按二叉排序树的原理,48插在37的右边,在找平衡因子。

    怎么找平衡因子,看哪个根左右子树或子树先出现差大于1,那么这个根平衡因子就为-2,有题目分析,24首先出现平衡因子为-2,所以按照旋转原则来:24,53,37这三个数进行旋转

                          

    所以整棵树是这样的:

                     

    (2)如果要构造平衡二叉树,第一个必定是空集,注意不能少了空集。

    参考文献:

    http://blog.csdn.net/wxbmelisky/article/details/47787963

               

    (3)如图,现在有两个平衡因子都为-2,所以选择离插入值近的那个,所以是件73,35,42进行旋转;将数值为中位数的放中间进行旋转:

                    

    (4)平衡二叉树构造过程如下(按二叉排序树的原则一个一个的插入):

     

     

    原文链接:https://blog.csdn.net/u013067756/article/details/54236172

    看到最后的帮忙点个👍🙏 谢谢,这个对我真的很重要!
    在这里插入图片描述

    展开全文
  • 平衡二叉树(AVL)

    千次阅读 2021-09-04 18:02:37
    平衡二叉树,全称为平衡二叉搜索树 它是由苏联数学家Adelson-Velsky 和 Landis提出来的,因此平衡二叉树又叫AVL树 平衡二叉树的定义是一种递归定义,要求每个节点都具有以下特性: 可以是一棵空树 左子树和右子树...

    1. 概述

    1.1 定义

    • 平衡二叉树,全称为平衡二叉搜索树
    • 它是由苏联数学家Adelson-Velsky 和 Landis提出来的,因此平衡二叉树又叫AVL树

    平衡二叉树的定义是一种递归定义,要求每个节点都具有以下特性:

    1. 可以是一棵空树
    2. 左子树和右子树高度之差的绝对值不超过1(左右子树的高度差可以为0、1和 -1)
    3. 左子树和右子树均为平衡二叉树

    为什么平衡二叉树是二叉搜索树?

    • 之前,在学习二叉搜索树时,增删该查的效率最坏为 O ( n ) O(n) O(n)。此时,二叉树退化成一条链
    • 若二叉搜索树尽可能的平衡,增删改查的时间复杂度将稳定在 O ( l o g 2 N ) O(log_2N) O(log2N)
    • 因此,我们希望二叉搜索树是平衡的二叉树,我想这也是平衡二叉树是基于二叉搜索树提出来的原因

    1.2 平衡因子与最小不平衡子树

    平衡因子

    • 定义中,左子树和右子树高度之差被称作平衡因子:左子树高度 - 右子树高度
    • AVL树中,要求 a b s ( 平 衡 因 子 ) < = 1 abs(平衡因子) <= 1 abs()<=1,即左右子树的高度差为0、1和 -1
    • 以上数值分别表示:左子树与右子树等高、左子树比右子树高、左子树比右子树矮

    在这里插入图片描述
    最小不平衡子树

    • 平衡二叉树,要求平衡因子 a b s ( 平 衡 因 子 ) < = 1 abs(平衡因子) <= 1 abs()<=1
    • 下图,新插入节点37,该树不再是平衡二叉树。因为,节点58的左右子树高度差为2
      在这里插入图片描述
    • 从新插入节点向上查找,第一个 a b s ( 平 衡 因 子 ) > 1 abs(平衡因子) > 1 abs()>1的节点为根的子树,被称为最小不平衡子树
    • 上图中,新插入节点向上查找,节点58左右子树高度差为2,以节点58为根节点的子树,就是最小不平衡子树

    关于最小不平衡子树的说明

    1. 新插入节点,可能导致平衡二叉树出现多棵不平衡的子树
    2. 此时,我们只需要调整最小不平衡子树,就能让整棵树平衡

    2. 平衡二叉树的左旋/右旋

    • 本章中,红色表示最小不平衡子树的根节点,蓝色表示新插入的节点

    2.1 右旋

    • 上图中,节点58为根节点的子树抽取出来。
    • 想要让其变成二叉平衡树,最简单的想法,将根节点58向左儿子47的右下方下压(降低左子树高度)
    • 下压后,根节点58成为左儿子47的右子树,将与左儿子原本的右子树51冲突
    • 巧妙之处: 将原本的右子树51改成根节点58的左子树,整棵树恢复平衡
      在这里插入图片描述
    • 上述操作就是平衡二叉树的右旋:将根节点绕左儿子顺时针下压

    右旋的规则

    1. 根节点成为左子节点的右子树
    2. 左子节点原本的右子树成为根节点的左子树(一个右子树被占据,一个左子树空闲,刚好可以互补)
    • 新插入节点37的插入位置:根节点58的左儿子的左子树上,这种情况称为LL
    • 后续,我们还将接触RR、LR、RL三种情况

    2.2 左旋

    • 下图中,新插入节点18,使得以12为根节点的树成为不平衡二叉树,最小不平衡子树的根节点也是12
    • 此时,左子树比右子树矮2
    • 要想平衡该二叉树,最直观的想法:将根节点12向右儿子15的左下方下压(降低右子树高度)
    • 问题来了,此时根节点12成为右儿子的左子树,原本的左子节点13如何处理?
    • 巧妙之处: 将原本的左子节13点变成节点12的右子树,整棵树恢复平衡
      在这里插入图片描述
    • 上述操作就是平衡二叉树的左旋:将根节点绕右儿子逆时针下压

    左旋的规则

    1. 根节点成为右儿子点的左子树
    2. 右儿子原本的左子树成为根节点的右子树(一个左子树被占据,一个右子树空闲,刚好互补)
    • 新插入节点18的位置:根节点12的右儿子的右子树,这种情况称为RR

    2.3 调整的四种情况

    • 上面小节中,我们通过右旋和左旋,见识了平衡二叉树调整的两种情况,分别是LL和RR

    四种情况的描述

    1. LL:新插入节点为最小不平衡子树根节点的左儿子的左子树上 → \rightarrow 右旋使其恢复平衡

    2. RR:新插入节点为最小不平衡子树根节点的右儿子的右子树上 → \rightarrow 左旋使其恢复平衡

    3. LR:新插入节点为最小不平衡子树根节点的左儿子的右子树上 → \rightarrow 以左儿子为根节点进行左旋,再按原始的根节点右旋
      在这里插入图片描述

    4. RL:新插入节点为最小不平衡子树根节点的右儿子的左子树上 → \rightarrow 以右儿子为根节点进行右旋,再按原始的根节点左旋
      在这里插入图片描述

    2.4 构建平衡二叉树

    • 基于数组{3, 2, 1, 4, 5, 6, 7, 10, 9, 8}构建一棵平衡二叉树
    • 具体的构建过程,参考博客:平衡二叉树实现原理 —— Best example 👍 👍👍👍
    • 这是我见过的、唯一的从零开始构建一棵平衡二叉树,且LL、RR、LR、RL四种情况都包含的示例

    参考链接:

    3. 代码实现

    3.1 树节点的定义

    增加高度属性

    • 二叉搜索树是否平衡,取决于左右子树的高度差
    • 插入节点或删除节点时,想要知道二叉树是否保持平衡,需要计算左右子树的高度
    • 计算左右子树的高度,一般通过自顶向下或自底向上的方式,递归计算(不对深度和高度加以区分)
    • 这样将会存在一定的时间开销和空间开销
    • 因此,需要在原有的TreeNode基础上,增加一个高度字段,用于记录当前节点的高度
    • 规定: 空节点的高度为0,叶子节点的高度为1,

    平衡二叉树,树节点的定义如下

    public class AVLNode {
        public int height;
        public AVLNode left;
        public AVLNode right;
        public int val;
    
        public AVLNode() {
        }
    
        public AVLNode(int val) {
            this.height = 1;
            this.left = null;
            this.right = null;
            this.val = val;
        }
    
        // 获取某个节点的高度
        public int getHeight(AVLNode node) {
            return node == null ? 0 : node.height;
        }
    }
    

    3.2 LL、RR、LR、RL的实现

    3.2.1 LL

    • 当待插入节点位于最小不平衡子树根节点的左儿子的左子树时,需要将根节点右旋
    • (1)根节点成为左儿子的右子树;(2)左儿子原本的右子树成为根节点的左子树

    代码实现:

    1. 先执行步骤(2),空出左儿子的右子树位置给根节点;再将根节点放置到左儿子的右子树位置
    2. 右旋后,根节点和左儿子的高度需要更新
    3. 左儿子就是调整后树的新根节点
      // LL,右旋
      public AVLNode rightRotate(AVLNode root) {
          // 右旋,左儿子成为新的根节点
          AVLNode newRoot = root.left;
          // 左儿子的右子树称为根节点的左子树
          root.left = newRoot.right;
          // 根节点成为右儿子的右子树
          newRoot.right = root;
      
          // 更新高度
          root.height = Math.max(getHeight(root.left), getHeight(root.right)) + 1;
          newRoot.height = Math.max(getHeight(newRoot.left), root.height) + 1;
      
          return newRoot;
      }
      

    3.2.2 RR

    • 当待插入节点位于最小不平衡子树根节点的右儿子的右子树时,需要进行左旋
    • (1)根节点成为右儿子的左子树;(2)右儿子原本的左子树成为根节点的右子树

    代码实现

    1. 先执行步骤(2),空出右儿子的左子树给根节点;再将根节点放到右儿子的左子树位置

    2. 左旋后,需要更新根节点和右儿子的高度

    3. 右儿子成为新的根节点

      // RR,左旋
      public AVLNode leftRotate(AVLNode root) {
          // 左旋,右儿子成为新的根节点
          AVLNode newRoot = root.right;
          // 右儿子的左子树成为根节点的右子树
          root.right = newRoot.left;
          // 根基点成为右儿子的左子树
          newRoot.left = root;
      
          // 更新根节点和新根节点的高度
          root.height = Math.max(getHeight(root.left), getHeight(root.left)) + 1;
          newRoot.height = Math.max(getHeight(newRoot.right), root.height) + 1;
      
          return newRoot;
      }
      

    3.2.3 LR

    • 当插入节点位于最小不平衡子树根节点的左儿子的右子树时,先左旋左儿子,再右旋根节点

    • LL和RR操作已经实现,再实现LR就很简单了

      // LR,左旋左儿子,再右旋根节点
      public AVLNode leftRightRotate(AVLNode root) {
          // 左旋左儿子
          root.left = leftRotate(root.left);
          // 右旋根节点
          return rightRotate(root);
      }
      

    3.2.4 RL

    • 当插入节点位于最小不平衡子树根节点的右儿子的左子树时,先右旋右儿子,再左旋根节点

    • LL和RR操作已经实现,再实现RL就很简单了

      // RL, 右旋右儿子,再左旋根节点
      public AVLNode rightLeftRotate(AVLNode root) {
          // 右旋右儿子
          root.right = rightRotate(root.right);
          // 左旋根节点
          return leftRotate(root);
      }
      

    3.3 插入节点

    3.3.1 插入节点

    • 插入节点时,与二叉搜索的插入一样,需要先根据大小关系确定插入位置

    • 完成插入后,如果导致当前树不平衡,需要旋转使其平衡
      (1)左儿子插入的,有LL、LR两种情况
      (2)右儿子插入的,有RR、RL两种情况

    • 不管是否调整平衡因子,都需要更新根节点的高度

      public AVLNode insert(int val, AVLNode root) {
          // 根节点为空,直接新建节点
          if (root == null) {
              return new AVLNode(val);
          }
      
          // 根据大小关系确定插入位置
          if (root.val > val) {
              // 在左儿子中插入,可能会使得左儿子变高
              root.left = insert(val, root.left);
      
              // 插入后,不平衡需要调整
              if (getHeight(root.left) - getHeight(root.right) == 2) {
                  // 插入的位置是左儿子的左子树,需要右旋
                  if (root.left.val > val) {
                      root = rightRotate(root);
                  } else { // 左儿子的右子树,需要先左旋再右旋
                      root = leftRightRotate(root);
                  }
              }
          } else if (root.val < val) {
              root.right = insert(val, root.right);
      
              // 插入后,不平衡需要调整
              if (getHeight(root.right) - getHeight(root.left) == 2) {
                  // 右儿子的右子树,左旋
                  if (root.right.val < val) {
                      root = leftRotate(root);
                  } else {
                      root = rightLeftRotate(root);
                  }
              }
          }
      
          // 完成插入更新高度
          root.height = Math.max(getHeight(root.left), getHeight(root.right)) + 1;
      
          return root;
      }
      

    3.3.2 构建平衡二叉树

    • 基于插入节点功能,可以输入一组节点值,构建一棵平衡二叉树

    • 代码如下

      public AVLNode buildTree(int[] nums) {
         // 创建一个空的根节点
         AVLNode root = null;
      
         // 依次完成节点插入
         for (int i = 0; i < nums.length; i++) {
             root = insert(nums[i], root);
         }
      
         return root;
      }
      

    3.3.3 功能验证

    • 为了验证构建好的二叉树,是否是我们预期的结构,需要打印二叉树

    • 由于使用上一章节中的数组{3, 2, 1, 4, 5, 6, 7, 10, 9, 8}

    • 二叉树的节点值和最终的树结构已知,作者选择通过层次遍历打印二叉树

    • 稳妥的做法: 通过二叉树是否平衡、中序遍历是否为升序来确定构建效果

      // 层次遍历二叉树
      public List<Integer> levelTraverse(AVLNode root) {
          List<Integer> list = new ArrayList<>();
          // 特殊情况,直接返回结果
          if (root == null) {
              return list;
          }
      
          // 借助队列实现层次遍历
          Queue<AVLNode> queue = new LinkedList<>();
          queue.offer(root);
          list.add(root.val);
      
          while (!queue.isEmpty()) {
              // 出队,访问左右子节点
              AVLNode node = queue.poll();
              if (node.left != null) {
                  queue.offer(node.left);
                  list.add(node.left.val);
              }
      
              if (node.right != null) {
                  queue.offer(node.right);
                  list.add(node.right.val);
              }
          }
      
          return list;
      }
      
    • 完成构建函数的实现后,通过以下代码验证是否成功构建平衡二叉树

      int[] nums = {3, 2, 1, 4, 5, 6, 7, 10, 9, 8};
      AVLNode root = new AVLNode();
      // 构建平衡二叉树
      root = root.buildTree(nums);
      // 打印二叉树,判断构建是否ok
      System.out.println(root.levelTraverse(root));
      
    • 执行结果:[4, 2, 7, 1, 3, 6, 9, 5, 8, 10],与真实树结构的层次遍历结果一致
      在这里插入图片描述


    十分感谢大佬的博客,给我构建平衡二叉树的灵感。看了很多博客,还是这篇博客写得比较符合我的需求

    3.4 删除节点

    3.4.1 删除节点分析及代码实现

    • 对于删除节点,之前学习过如何删除二叉搜索树中的节点
      (1)被删除节点是叶子节点,直接删除
      (2)被删除节点有右子树,将后继节点上提,再递归删除后继节点
      (3)被删除节点只有左子树,将前驱节点上提,在递归删除前驱节点

    • 现在问题来了,删除节点以后,可能会使得平衡二叉树失去平衡,如何调整使其依然保持平衡?

    • 感谢博客:[Java]平衡二叉树的插入与删除,给我灵感

    完成节点删除后:

    1. 如果 h e i g h t ( 左 子 树 ) − h e i g h t ( 右 子 树 ) > = 2 height(左子树) - height(右子树) >= 2 height()height()>=2,说明被删除节点位于右子树。因为右子树变矮,才变得不平衡
    2. 如果 h e i g h t ( 右 子 树 ) − h e i g h t ( 左 子 树 ) > = 2 height(右子树) - height(左子树) >= 2 height()height()>=2,说明被删除节点位于左子树。因为左子树变矮,才变得不平衡
    3. 删除节点可以看做插入节点:在右子树删除节点 → \rightarrow 在左子树插入节点;在左子树删除节点 → \rightarrow 在右子树插入节点
    4. 左子树插入节点: h e i g h t ( 左 儿 子 的 左 子 树 ) > h e i g h t ( 左 儿 子 的 右 子 树 ) height(左儿子的左子树) > height(左儿子的右子树) height()>height(),说明是在左儿子的左子树插入,属于LL;否则, 属于LR
    5. 右子树插入节点: h e i g h t ( 右 儿 子 的 右 子 树 ) > h e i g h t ( 右 儿 子 的 左 子 树 ) height(右儿子的右子树) > height(右儿子的左子树) height()>height(),说明是在右儿子的右子树插入,属于RR;否则,属于RL
    • 代码实现如下

      public AVLNode remove(AVLNode root, int val) {
          // 停止条件:节点为null,无法继续删除
          if (root == null) {
              return null;
          }
      
          // 通过大小关系,确定删除节点的位置
          if (root.val > val) {
              // 在左子树进行节点删除
              root.left = remove(root.left, val);
          } else if (root.val < val) {
              root.right = remove(root.right, val);
          } else {
              // 找到了对应的节点,按情况删除
              if (root.left == null && root.right == null) {
                  root = null;
              } else if (root.right != null) {
                  // 后继节点上提,再删除后继节点
                  AVLNode successor = successor(root);
                  root.val = successor.val;
      
                  // 在右子树中删除后继节点
                  root.right = remove(root.right, successor.val);
              } else {
                  // 前驱节点上提,再删除前驱节点
                  AVLNode preSuccessor = preSuccessor(root);
                  root.val = preSuccessor.val;
      
                  // 在左子树中删除前驱节点
                  root.left = remove(root.left, preSuccessor.val);
              }
          }
      
          // 删除完成后,可能需要调整平衡度
          if (root == null) {
              return null;
          }
      
          // 左子树比右子树高,说明删除的是右子树的节点
          if (getHeight(root.left) - getHeight(root.right) >= 2) {
              // 模拟在左子树插入的情况:在左儿子的左子树插入,在左儿子的右子树插入
              if (getHeight(root.left.left) > getHeight(root.left.right)) {
                  return rightRotate(root);
              } else {
                  return leftRightRotate(root);
              }
          } else if (getHeight(root.right) - getHeight(root.left) >= 2) { // 在左子树删除节点
              // 模拟在右子树插入节点
              if (getHeight(root.right.right) > getHeight(root.right.left)) {
                  return leftRotate(root);
              } else {
                  return rightLeftRotate(root);
              }
          }
      
          // 无需调整,直接更新root的高度并返回
          root.height = Math.max(getHeight(root.left), getHeight(root.right)) + 1;
          return root;
      }
      
      // 寻找前驱节点
      private AVLNode preSuccessor(AVLNode root) {
          // 特殊情况
          if (root == null) {
              return null;
          }
          // 左子树寻找最右节点
          root = root.left;
          while (root.right != null) {
              root = root.right;
          }
          return root;
      }
      
      // 寻找后继节点
      private AVLNode successor(AVLNode root) {
          // 特殊情况
          if (root == null) {
              return null;
          }
          // 在右子树寻找最左节点
          root = root.right;
          while (root.left != null) {
              root = root.left;
          }
      
          return root;
      }
      

    3.4.2 功能验证

    • 仍然基于上面的二叉树,进行节点删除

    情况一:依次删除8, 5, 6
    在这里插入图片描述

    • 代码如下

      int[] nums = {3, 2, 1, 4, 5, 6, 7, 10, 9, 8};
      AVLNode root = new AVLNode();
      // 构建平衡二叉树
      root = root.buildTree(nums);
      System.out.println(root.levelTraverse(root));
      // 节点的删除
      root = root.remove(root, 8);
      System.out.println(root.levelTraverse(root));
      
      root = root.remove(root, 5);
      System.out.println(root.levelTraverse(root));
      
      root = root.remove(root, 6);
      System.out.println(root.levelTraverse(root));
      
    • 删除节点后的结果
      在这里插入图片描述

    • 情况二:删除5, 6
      在这里插入图片描述

    • 相关代码

      int[] nums = {3, 2, 1, 4, 5, 6, 7, 10, 9, 8};
      AVLNode root = new AVLNode();
      // 构建平衡二叉树
      root = root.buildTree(nums);
      System.out.println(root.levelTraverse(root));
      // 删除节点5和6
      root = root.remove(root, 5);
      System.out.println(root.levelTraverse(root));
      
      root = root.remove(root, 6);
      System.out.println(root.levelTraverse(root));
      
    • 打印结果
      在这里插入图片描述

    4. 后记

    展开全文
  • 考研之数据结构016_平衡二叉树AVL一、定义二、插入操作三、插入后调整“不平衡”问题1.LL左孩子左子树平衡旋转(右单旋转)1.LL代码:2.RR右孩子右子树平衡旋转(左单旋转)1.RR代码:3.LR左孩子右子树平衡旋转( ...

    考试重点(选择题):
    1.我们在二叉排序树中,插入一个新结点之后,怎么保证这棵树依然是“平衡二叉树”。
    2.高为h的平衡二叉树,最少有几个结点——递推求解
    在这里插入图片描述

    一、定义

    平衡二叉树,简称平衡树(AVL树): 树上任一结点的左子树和右子树的高度之差不超过1。
    ps:AVL是平衡树 ——ASL是:平均查找长度 =》不要混淆。

    结点的平衡因子某结点的左子树高-右子树高
    二叉树是平衡的话,各个结点的平衡银子只能是:“-1,0,1”。
    例如:如下图,50根节点,左子树高度是2,而右子树高度为3.所以:结点的平衡银子=左子树2-右子树3=-1
    在这里插入图片描述
    让一颗二叉排序树保持平衡,就可以保证查找效率:log2n

    在这里插入图片描述

    二、插入操作

    在我们插入一个新结点后,如何保持二叉树的平衡?
    方法:我们可以从新插入的结点开始往上找,找到第一个不平衡的结点,进行调整以该结点为根的子树——最小不平衡子树。
    最小不平衡子树:最小的结点的左右子树高度相差大于1

    在这里插入图片描述

    三、插入后调整“不平衡”问题

    在插入操作中,只要将最小不平衡树调整平衡,则其他祖先结点都会恢复平衡。
    二叉排序树的特性:
    左子树结点值< 根节点的值 < 右子树结点的值
    目标:
    1.插入新结点后,恢复平衡
    2.保持二叉排序树的特性。

    在这里插入图片描述

    1.LL左孩子左子树平衡旋转(右单旋转)

    由于结点A的左孩子(L)的左子树(L)上插入了新结点,A的平衡因子从1增2,导致A为根的子树失去平衡,需要一次向右的旋转操作:
    将A的左孩子B向右上旋转代替A称为根节点,将A结点向右下旋转称为B的右子树的根节点,而B的原右子树则作为A结点的左子树

    自己简述:
    在调整LL最小不平衡子树中,让目前根的左子树B结点成为根节点,并让左子树的右子树BR,成为原根A结点的左子树。(原根节点A,之前左子树是B,现在A成了根节点B的右子树了)

    在这里插入图片描述

    1.LL代码:

    f是指向原根节点
    P指向根节点的左子树
    
    
    
    f->lchild=p->rchild;
    B的右子树,成为A结点的左子树。 
    下一步是为了,让A结点成为B结点的右子树
    
    p->rchild=f
    A结点变成B的右孩子。
    是因为F存放的是原根节点A的地址,现在将F的值赋值给B的右孩子了。
    也就是说B的右孩子是A
    
    gf->lchild/rchild=p
    A的父结点原本指向A的孩子指针,指向P(也就是B)
    也就是将根节点的上一结点指向根节点。
    。从而B成了根节点
    

    在这里插入图片描述

    2.RR右孩子右子树平衡旋转(左单旋转)

    RR 平衡旋转(左单旋转)。由于结点A的右孩子(R)的右子树(R)上插入了新结点,高度有-1变-2了,导致了A为根的子树失去了平衡,需要一次向左的旋转操作。将A根节点的右孩子B向左上旋转,代替A称为根节点。将A向左下旋转成为B的左孩子,将之前B的左子树,变成A的右子树
    自己叙述:
    在调整RR最小不平衡子树中,让目前根节点A的右子树成为根节点,现在B成为了根节点。再让B的右子树的左子树,成为现在根节点的左子树A结点的右子树。

    在这里插入图片描述

    1.RR代码:

    不平衡之前
    A是:根节点
    B是:根节点A的右孩子
    
    变平衡:
    将B的左孩子变为A的右孩子,让A结点变成B的左孩子,在修改A的父结点指针,指向B结点。
    (是因为根节点之前是A ,现在根节点是B。让父结点从A变成B)
    
    平衡之后
    B是:根节点
    A是:根节点B的左孩子
    

    在这里插入图片描述

    3.LR左孩子右子树平衡旋转( 旋转)

    在这里插入图片描述

    在这里插入图片描述

    C结点就是  根节点的左子树的右孩子
    
    先让C结点左旋转,顶替B的位置,
    再让C结点在进行一个右上旋转。
    替换A的位置。
    ---------------
    
    首先是C左旋替换B的位置,然后B变成C的左孩子。
    然后是C右旋替换A的位置,然后C的右孩子变成A的左孩子。
    从而:A变成C的右孩子
    

    4.RL右孩子的左子树平衡旋转(旋转)

    在这里插入图片描述

    先让C结点,右旋转顶替B,在左旋顶替A
    --
    右旋顶替B:
    C的右孩子,成为B的左孩子。
    C的右子树,成为B
    
    左旋顶替A:
    先让C的左子树,成为A的右子树。
    再让C的左子树,成为A
    
    

    5.练习:调整完以后,一定验算是否符合左中右依次递增。

    1.

    在这里插入图片描述

    2.

    在这里插入图片描述
    在这里插入图片描述

    3.

    将60结点的左子树,交给他的父结点的右子树。
    将60结点的右子树,交给他的爷结点的左子树。

    在这里插入图片描述
    在这里插入图片描述

    四、查找效率分析

    假设nh表示深度为h的平衡树中含有的最少结点数。

    在这里插入图片描述
    n1= 1
    n2= 1+n1= =2
    n3= n2+n1+1 =4
    n4= n3+n2+1 =7
    n5= n4+n3+1 = 7+4+1=12
    在这里插入图片描述
    平均查找长度(查找的时间复杂度)和树高是同一个数量级。
    在这里插入图片描述

    展开全文
  • 二叉排序树与平衡二叉树的实现

    热门讨论 2010-12-26 15:25:31
    题目名称 二叉排序树与平衡二叉树的实现 评分项目 分值 得分 评价内涵 工作 表现 20% 01 学习态度 6 遵守各项纪律,工作刻苦努力,具有良好的科学工作态度。 02 科学实践、调研 7 通过实验、试验、查阅文献、深入...
  • 平衡二叉树
  • 文章目录一、写在前言二、平衡二叉树(一)平衡二叉树介绍1、Why2、What3、how(二)平常二叉树构造1、左旋转2、右旋转3、双旋转(三)代码实现三、结束语 一、写在前言 还有一天,后天就要回学校了,心里无比的激动...
  • 平衡二叉树总结

    千次阅读 2018-04-20 20:27:11
    平衡二叉树相关概念以及性质 平衡二叉树的类结构 LL型失衡以及解决办法 RR型失衡以及解决办法 LR型失衡以及解决办法 RL型失衡以及解决办法 balance和checkBalance函数 完整源码测试 说明 在学二叉平衡树...
  • 代码实现平衡二叉树

    2020-12-16 07:13:28
    实现二叉树对于我们已经算是轻车熟路了。先来定义树的结点:class AVLNode {public int data;public int depth;public int balance;public AVLNode parent;public AVLNode left;public AVLNode right;public AVLNode...
  • 【数据结构】平衡二叉树的插入、删除

    万次阅读 多人点赞 2018-08-14 23:47:21
    定义:什么叫平衡二叉树 定义及原理 不平衡的四种情况 旋转操作 插入节点 删除节点 定义:什么叫平衡二叉树 是二叉查找树的一个进化体,也是第一个引入平衡概念的二叉树。1962年,G.M. Adelson-Velsky 和...
  • 平衡二叉树的查找、折半查找的实现、Hash表的实现(除留余数法)
  • 【数据结构】----平衡二叉树怎么自己画?

    万次阅读 多人点赞 2017-01-08 19:23:27
    【数据结构】平衡二叉树怎么自己画?   是什么?  要了解平衡二叉树,先得了解什么是二叉树? 二叉树定义: 在计算机中,二叉树是每一个节点最多有两个子树的结构。通常子树被称作“左子树(left subtree)”...
  • 平衡二叉树,又称为 AVL 树。实际上就是遵循以下两个特点的二叉树: ①每棵子树中的左子树和右子树的深度差不能超过 1; ②二叉树中每棵子树都要求是平衡二叉树; 其实就是在二叉树的基础上,若树中每棵子树都满足其...
  • 平衡二叉树

    2018-05-16 17:16:08
    根据给定的输入序列建立一棵平衡二叉树,求出建立的平衡二叉树的树根。 Input 输入一组测试数据。数据的第1行给出一个正整数N(n &lt;= 20),N表示输入序列的元素个数;第2行给出N个正整数,按数据给定顺序建立...
  • 我们从二叉排序树讲起,然后我们聊聊平衡二叉树 二叉排序树 首先,对于一颗二叉排序树来讲,它满足以下的性质。 1.左子树的所有结点 都 小于 根节点 2.右子树的所有结点 都 大于 根节点 3.左右子树本身也是一颗 二叉...
  • 每碰到一个节点,就判断以该结点为根的左右子树是否是平衡二叉树(通过求左右子树的树高),然后在判断该结点的左右子树为根的子树是否是平衡二叉树。这样就遍历树中每一个结点,对每个结点都判断是否平衡二叉树。 ...
  • 二叉排序树或是一棵空树,或着是具有以下性质的二叉树: (1)若左子树不空,则左子树上的所有节点值均小于他的根节点值。 (2)若右子树不空,则右子树上的所有节点值均大于他的根节点值。 (3)它的左右子树也分别...
  • 平衡二叉树的根题目答案声明 题目 答案 #include<iostream> #include<malloc.h> using namespace std; typedef struct node* avl; struct node{ int data; avl left,right; }; int GetHeight(avl a)/...
  • 文章目录单选题选择题题解编程题7-3 插入排序还是堆排序 (25分) 不会输入格式:输出格式:输入样例 1:输出样例 1:输入样例 2...在下列所示的平衡二叉树中,插入关键字48后得到一棵新平衡二叉树。在新平衡二叉树中,关
  • 一、平衡二叉树的概念 平衡二叉树(Balancedbinarytree)是由阿德尔森-维尔斯和兰迪斯(Adelson-VelskiiandLandis)于1962年首先提出的,所以又称为AVL树。 定义:平衡二叉树或为空树,或为如下性质的二叉排序树: ...
  • 平衡二叉树,又被称为AVL树(有别于AVL算法),且具有以下性质:它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。这个方案很好的解决了二叉查找树退化成链表的问题,...
  • 问题 A: 算法9-9~9-12:平衡二叉树的基本操作 题目描述 平衡二叉树又称AVL树,它是一种具有平衡因子的特殊二叉排序树。平衡二叉树或者是一棵空树,或者是具有以下几条性质的二叉树: 1.若它的左子树不空,则...
  • 二叉树 每个节点最多有两颗子数; 左右子树有序,不能颠倒 即使某个节点中只有一颗子树,也要区分是左右;如上图所示:节点C是节点A的右子树,节点F是节点C的右子树。 特殊的二叉树: 1、斜树:所有节点都只有左子...
  • 思路分析: 这个题的重点就是平衡二叉树的插入,基本的情况和二分搜索树类似,多了平衡调整。对于一棵平衡二叉树来说,他的任意一个节点的左右子树的高度差不能超过1。 因此,在Node节点的设计中,我们需要为每一个...
  • Day39:平衡二叉树

    2020-05-25 12:13:48
    剑指Offer_编程题——平衡二叉树 题目描述: 输入一颗二叉树,判断该二叉树是否是平衡二叉树。在这里,我们只需要考虑其平衡性,不需要考虑其是不是排序二叉树。 具体要求: 时间限制: C/C++ 1秒,其他语言2秒 ...
  • AVL平衡二叉树的插入和删除 题目描述 AVL树是一种平衡二叉树(BBST),能够很好的兼顾数据查询、删除、插入性能。 本次实验通过读取插入和删除命令,执行AVL树的动态调整。通过输出先序序列,对比动态调整的结果是否...
  • #平衡二叉树
  •  将关键字(DEC, FEB, NOV, OCT, JUL, SEP, AUG, APR, MAR, MAY, JUN, JAN)按字母顺序依次插入到一棵初始为空的AVL树中,画出每插入一个关键字后的AVL树,并标明平衡旋转的类型。在所建立的AVL树中删除关键字MAY,为...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 3,602
精华内容 1,440
关键字:

平衡二叉树旋转题目