精华内容
下载资源
问答
  • 平衡二叉树的定义

    千次阅读 2019-05-09 21:07:29
    平衡二叉树又称AVL树,它插入语、删除、查找操作均可在O(log n)时间内完成。 1. AVL树或者是一棵空树,或者是具有下列性质非空二叉搜索树: (1) 任一结点左、右子树均为AVL树 (2) 根结点左、右子树高度差...

    定义

    平衡二叉树又称AVL树,它的插入语、删除、查找操作均可在O(log n)的时间内完成,平衡二叉树是建立在搜索二叉树基础上的平衡。
    1. AVL树或者是一棵空树,或者是具有下列性质的非空二叉搜索树:
    (1) 任一结点的左、右子树均为AVL树
    (2) 根结点左、右子树高度差绝对值不超过1
    2. 对于二叉树中任一结点T,其平衡因子(BF)定义为BF(T)=hl-hr,其中hl和hr分别为T的左、右子树的高度
    有了平衡因子的定义,AVL树“任一结点左右子树高度差的绝对值不超过1”这一性质可以表述为“一棵AVL树种任一结点的平衡因子只能在集合{-1,0,1}中取值”,这就是平衡的量化标准

    展开全文
  • 34平衡二叉树的定义

    2021-01-17 14:18:10
    平衡二叉树的定义:在插入和删除二叉树结点时,要保证任意结点的左右子树高度差的绝对值不超过1,将这样的二叉树称为平衡二叉树,简称AVL树 因此,平衡二叉树可定义为一颗空树或者具有下列性质的二叉树:它的左子树...

    平衡二叉树的定义:在插入和删除二叉树结点时,要保证任意结点的左右子树高度差的绝对值不超过1,将这样的二叉树称为平衡二叉树,简称AVL树
    因此,平衡二叉树可定义为一颗空树或者具有下列性质的二叉树:它的左子树和右子树都是平衡二叉树,且左子树和右子树高度差的绝对值不超过1.如下所示,结点中的值为该结点的平衡因子

    在这里插入图片描述

    展开全文
  • 本题中,一棵高度平衡二叉树定义为: 一个二叉树每个节点左右两个子树高度差绝对值不超过1。 示例 1: 给定二叉树 [3,9,20,null,null,15,7] 3 / \ 9 20 / \ 15 7 返回 true 。示例 2: 给定二叉树...

    问题描述:

    给定一个二叉树,判断它是否是高度平衡的二叉树。

    本题中,一棵高度平衡二叉树定义为:

    一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。

    示例 1:

    给定二叉树 [3,9,20,null,null,15,7]

        3
       / \
      9  20
        /  \
       15   7

    返回 true

    示例 2:

    给定二叉树 [1,2,2,3,3,null,null,4,4]

           1
          / \
         2   2
        / \
       3   3
      / \
     4   4
    

    返回 false

    基本思路:

    按照平衡二叉树的定义来好了:

    • 空节点是平衡二叉树
    • 如果一个节点左右子树高度差不超过1,且左右子树均为平衡二叉树,那么该节点也是平衡二叉树。

    对高度求递归,再对定义求递归,判断一下,就出来了。

    要注意区别BST和平衡二叉树,这两个是完全不同的概念

    BST和平衡二叉树结合,形成的高度平衡的二叉搜索树,那就是一个崭新的世界。

    高度平衡的二叉搜索树可以由AVl, RBT, Treap(区分于普通的树堆)和

    AC代码:

    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
        int GetHeight(TreeNode *root) {
        // 其实这里在求节点的个数了
          // 处理特殊情况
          if (!root) return 0;
          // 获得左右子树高度
          int left_height = 0;
          int right_height = 0;
          if (root->left) left_height = GetHeight(root->left);
          if (root->right) right_height = GetHeight(root->right);
          // 取最大的为深度
          return max(left_height, right_height) + 1;
        }
        bool isBalanced(TreeNode* root) {
          if (!root) return true;
          int left_height = GetHeight(root->left);
          int right_height = GetHeight(root->right);
          // 不仅左右子树高度差为1, 而且左右子树必须都是平衡树
          if (fabs(left_height - right_height) <= 1 && isBalanced(root->left) && isBalanced(root->right))
            return true;
          return false;
        }
    };

    改进思路:

    之前的代码在求深度和遍历平衡二叉树的过程中重复了。

    不妨在求平衡二叉树的深度的时候引入一个flag,如果子树不是平衡二叉树就变为false;

    这里是用了-1代替false;在返回合理的值时候做一个判断,然后继续把-1往上穿

    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
        int maxDepth(TreeNode* root) {
            if(root == NULL)
                return 0;
            int left = maxDepth(root->left);
            int right = maxDepth(root->right);
            if(abs(left- right)>1 || left == -1 || right == -1)
                return -1;
            return max(left, right) + 1;
        }
        bool isBalanced(TreeNode* root) {
            if(root == NULL)
                return true;
            return maxDepth(root) != -1;
        }
    };

    其他经验:

    在一个函数中其实完全可以把传值和判断一体化

    做法就是传一个不合法的值作为判断。

    每次穿合法的值的时候判断一下是否合法,不合法的话继续传递不合法的值。

    展开全文
  • “平衡因子”:BF(T)=h(L)-h(R) 其中h(L)和h(R)分别为T...平衡二叉树的调整: 记住一点:无论怎么调整,都要保证还是二叉搜索树,左子树要比根结点小,右子树要比根结点大   深度:对于任意结点n,n的深...

     

    “平衡因子”:BF(T)=h(L)-h(R)

    其中h(L)和h(R)分别为T的左右子树的高度。

    平衡二叉树 (AVL树(提出平衡树的人名首字母)) 空树或者任一节点左右子树高度差的绝对值不超过1,即-1=<BF(T)<=1

     

    平衡二叉树的调整:

    记住一点:无论怎么调整,都要保证还是二叉搜索树,左子树要比根结点小,右子树要比根结点大

     

    深度:对于任意结点n,n的深度为从根到n的唯一路径长,根的深度为0

    高度:对于任意结点n,n的高度为从n到一片树叶的最长路径长,所有树叶的高度为0

    两个结点间的路径长度:为两个结点间路径边的条数。

     

     

    当破坏者是在被破坏者的右子树的右子树上时,应该RR旋转保持平衡(过程如下)

    将被破坏者也就是发现者的右子树提上来,由于平衡二叉树也是二叉搜索树,所以BL一定比B小 比A大,则放到A的右边。

     

     

     

     

     

     

    展开全文
  • 一、什么是平衡二叉树? 说到平衡二叉树,我们就得先说说什么是平衡因子。 平衡因子(Balance Factor,简称BF): BF(T) = hL - hR, 其中hL和hR分别为树T的左、右子...下面是判别是否是平衡二叉树的例子:这里我就不分
  • 数据结构 - 平衡二叉树(C++)

    万次阅读 多人点赞 2019-02-22 15:36:53
    平衡二叉树的定义 平衡二叉树(Balanced Binary Tree)是具有以下性质的二叉树:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。 判断一棵二叉树是否平衡(C++) ...
  • 一、平衡二叉树的定义为避免树的高度增长过快,降低二叉树的排序性能,规定在插入和删除二叉树结点时,保证任意结点的左右子树高度差的绝对值不大于1。这样的二叉树被称为平衡二叉树(Balanced Binary Tree)。二、...
  • 平衡二叉树

    2017-09-25 16:55:24
    1. 平衡二叉树的定义 若一颗二叉树中每个节点的左右子树的高度至多相差1,则称为平衡二叉树。在算法中,通过平衡因子(balanced factor bf)来具体实现上述平衡二叉树的定义。 1.1 平衡因子的定义 平衡二叉树中每个...
  • 平衡二叉树的定义是:它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。我们要判断是否为平衡二叉树就要一直递归判断它的子树是否为平衡二叉树,一层层去判断。代码...
  • 最美二叉树—平衡二叉树

    千次阅读 2020-06-11 19:06:07
    一、平衡二叉树的定义 二、平衡二叉树的插入 三、调整最小不平衡子树A 四、调整最小不平衡子树(LL) 五、调整最小不平衡子树(RR) 七、调整最小平衡子树(LR) 八、调整最小不平衡子树(RL) 九、调整最小...
  • 平衡二叉树的定义是:如果某二叉树中任意节点的左右子树的深度相差不超过1,那么它就是一棵平衡二叉树。拿到二叉树的题目,一般的解题思路都可以先从左右子树递归求解。如果左子树不满足平衡或右子树不满足平衡,...
  • 4.5.2 平衡二叉树

    2016-09-20 11:35:27
    1、平衡二叉树的定义 为了避免树的高度增长过快,降低二叉排序树的性能,我们规定在插入和删除二叉树结点时,要保证任意结点的左、右子树高度差的绝对值不超过1,将这样的二叉树称为平衡二叉树,简称平衡树(AVL树)...
  • 我们在上一篇文章中分享了平衡二叉树的定义和实现原理,这一节我们来演示如何通过代码实现平衡二叉树,最后分析下平衡二叉树的算法复杂度。实例演示在开始之前,我们先通过一个对比来加强理解,在没有介绍平衡二叉树...

空空如也

空空如也

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

平衡二叉树的定义