网站建设 招标资质要求,wordpress全局pjax,双牌网站建设,石家庄公司网站建设目录
基本介绍
平衡因子
平衡二叉树
平衡二叉树的高度 基本介绍
什么是平衡二叉树#xff1f;
以一个例子来解释一下#xff1a;
搜索树结点按不同的插入次序#xff0c;将会导致不同的深度和平均查找长度ASL 在二叉搜索树中查找一个元素#xff1a; #xff08…目录
基本介绍
平衡因子
平衡二叉树
平衡二叉树的高度 基本介绍
什么是平衡二叉树
以一个例子来解释一下
搜索树结点按不同的插入次序将会导致不同的深度和平均查找长度ASL 在二叉搜索树中查找一个元素 a要找到Jan需要查找一次要找到Feb需要查找两次 要找到Mar也需要查找两次......要找到Nov需要查找六次。 把所有查找次数加起来再除以12 得到平均查找长度ASLa 1 2 * 2 3 * 3 4 * 3 5 * 2 6 * 1 / 12 3.5 b要找到July需要查找一次要找到Feb需要查找两次 要找到May也需要查找两次......要找到Sept需要查找四次。 算出平均查找长度ASLb 1 2 * 2 3 * 4 4 * 5 / 12 3.0 c要找到Apr需要查找一次要找到Aug需要查找两次...... 要找到Sept需要查找十二次。 算出平均查找长度ASLc 1 2 3 4 5 6 7 8 9 10 11 12 / 12 6.5 通过上面的例子我们可以看到方式b的平均查找长度最短在观感上结点的分布也比较均匀。
所以二叉树我们要求比较平衡才能够让查找的长度更短一些。 而如何衡量一颗二叉树平衡不平衡呢
是左右两边的结点数差不多是左右两边的高度差不多
这样我们就认为基本上平衡即为平衡二叉树。 平衡因子 平衡因子Balance Factor简称BF BFT - 其中和分别为T的左、右子树的高度。 平衡二叉树 平衡二叉树Balanced Binary Tree AVL树 空树或者任一结点左、右子树高度差的绝对值不超过1即 下面来判断一下以下几颗二叉树是否为平衡二叉树
(1) (2) (3) 先来看第一棵二叉搜索树 再来看第二棵二叉搜索树 最后看第三棵二叉搜索树 平衡二叉树的高度
我们要二叉树平衡其目的是为了让二叉树的高度更低一些
越平衡的二叉树高度就越低。
一棵结点总数为n的完全二叉树高度为 h log2n 那么平衡二叉树的高度是否能达到呢
设为 高度为h的平衡二叉树的最少结点数。 结点数最少时 总结出 可以得到一个公式
我们会发现这个公式有点眼熟是与斐波那契序列的公式有点像。 从这里我们就来分析一下nh跟斐波那契序列的有什么关系。 在数学上有一个公式 当i逐步增大时大致等于公式算出来的值。
且是一个指数函数。
根据我们上面分析出来的和的关系就可以代入得到的相关公式。 所以反过来我们就得到h的表达式 用自己的想法把他推一遍 综上所述我们可以得到结论
给定结点数为n的AVL树的最大高度为 end 学习自MOOC数据结构——陈越、何钦铭
