什么叫理想平衡二叉树 平衡二叉树是不是必须左小右大

appeal2022-11-21 08:02:071760

平衡二叉树怎么理解啊?平衡二叉树定义,什么是“理想平衡二叉树?平衡二叉树是什么?能通俗地说一下并举例子吗?什么叫做平衡二叉树?平衡二叉树是什么?

本文导航

二叉树深度是怎么算的

这要涉及到满二叉树与完全二叉树的问题

满二叉树是将一个n层二叉树完全排满的二叉树,第n层有2^n个元素;

n层完全二叉树是将n层满二叉树最后一层从后向前依次去处少于2^n个元素;

完全二叉树是平衡二叉树的一个特例,平衡二叉树是将完全二叉树的最后一层元素任意排在空位上的一种二叉树。

如下图所示,左为满二叉树,右为完全二叉树:

平衡二叉树的调整方法

所谓平衡二叉树是指树中任一结点的左、右子树高度大致相同。平衡二叉树有很多种最著名的是由前苏联数学家Adelse—Velskil和Landis在1962年提出的,称为AVL树。平衡二叉树(AVL树)定义如下:平衡二叉树或者是一棵空树,或者是具有以下性质的二叉排序树:(1)它的左子树和右子树的高度之差绝对值不超过1;(2)它的左子树和右子树都是平衡二叉树。

平衡二叉树构建图解

理想二叉树是一种特殊的满二叉树,其所有叶结点均在同一高度或者同一深度,也即一棵深度(高度)为h且有 2^h-1个结点的二叉树。

如何构造平衡二叉树

简单说就是平衡二叉排序树,也就是首先是二叉排序树,然后还是平衡的。可以这样理解

它要么是一 棵空树,要么是它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树

平衡二叉树构造方法

这要涉及到满二叉树与完全二叉树的问题

满二叉树是将一个n层二叉树完全排满的二叉树,第n层有2^n个元素;

n层完全二叉树是将n层满二叉树最后一层从后向前依次去处少于2^n个元素;

完全二叉树是平衡二叉树的一个特例,平衡二叉树是将完全二叉树的最后一层元素任意排在空位上的一种二叉树。

如下图所示,左为满二叉树,右为完全二叉树:

平衡二叉树是不是必须左小右大

平衡二叉树(AVL)

那对图 1 进行下改造,把数据重新节点重新连接下,图 2 如下:

图 2 可以看到以下特性:

1. 所有左子树的节点都小于其对应的父节点(4,5,6)<(7);(4)<(5);(8)< (9);

2. 所有右子树上的节点都大于其对应的父节点(8,9,10)>(7);(6)>(5);(10)>(9);

3. 每个节点的平衡因子差值绝对值 <=1;

4. 每个节点都符合以上三个特征。

满足这样条件的树叫平衡二叉树(AVL)树。

问:那再次查找节点 5,需要遍历多少次呢?

由于数据是按照顺序组织的,那查找起来非常快,从上往下找:7-5,只需要在左子树上查找,也就是遍历 2 次就找到了 5。假设要找到叶子节点 10,只需要在右子树上查找,那也最多需要 3 次,7-9-10。也就说 AVL 树在查找方面性能很好,最坏的情况是找到一个节点需要消耗的次数也就是树的层数, 复杂度为 O(logN)

如果节点非常多呢?假设现在有 31 个节点,用 AVL 树表示如图 3:

图 3 是一棵高度为 4 的 AVL 树,有 5 层共 31 个节点,橙色是 ROOT 节点,蓝色是叶子节点。对 AVL 树的查找来看起来已经很完美了,能不能再优化下?比如,能否把这个节点里存放的 KEY 增加?能否减少树的总层数?那减少纵深只能从横向来想办法,这时候可以考虑用多叉树。

扫描二维码推送至手机访问。

版权声明:本文由尚恩教育网发布,如需转载请注明出处。

本文链接:https://www.shane-english.com.cn/view/68102.html

标签: 学习
分享给朋友:

“什么叫理想平衡二叉树 平衡二叉树是不是必须左小右大” 的相关文章

减字木兰花竞渡 减字木兰花意象特点

减字木兰花·竞渡的全文翻译,黄裳《减字木兰花 竞渡》翻译,减字木兰花竞渡的诗,减字木兰花竞渡的作者,减字木兰花和减字木兰花竞渡分析两首诗营造的意境有什么不同?《减字木兰花·竞渡》北宋词人黄裳。本文导航绝句的翻译三年级下减字木兰花莺初解语翻译七绝芳菲满园古诗风落吴江雪纷纷入酒杯的作者减字木兰花意象特点...

纸船和风筝 太阳和松鼠有哪些相同点和不同点

纸船和风筝 太阳和松鼠有哪些相同点和不同点

纸船和风筝主要讲了什么?《纸船和风筝》一文中,小熊和松鼠能够重归于好是因为什么?二年级语文纸船和风筝,松鼠为什么高兴的哭了?《纸船和风筝》是一篇什么故事?纸船和风筝的故事告诉我们什么道理?纸船和风筝文中的你指的是什么?本文导航追风筝的人主要讲了什么太阳和松鼠有哪些相同点和不同点二年级纸船和风筝阅读风...

法律经济学要考什么 西南财经大学经济数学研究生就业

经济法考研考哪些科目,我今年大一,专业是经济学,想考法律经济学.考研都考什么科目呢?西南财经大学的法律经济学要考数学吗???法经济考研的科目有哪些,经济学专科考试科目有哪些。本文导航考研经济法是学硕还是专硕本科经济学考研能考会计学吗西南财经大学经济数学研究生就业考研经济法难度排名大二经济学考什么考研...

川美理论类怎么考 四川美院本科提前批录取结束了吗

川美理论类怎么考 四川美院本科提前批录取结束了吗

四川美术学院考研同等学力加试的专业基础和艺术理论考什么?四川美院点招考哪些内容,四川美院文化分一般要考多少才稳?请问川美考研 文艺理论 是怎么考的呢···急?本文导航四川美术学院硕士研究生招生目录四川美院本科提前批录取结束了吗四川美院文化分一般要考多少才稳?请问川美考研 文艺理论 是怎么考的呢···...

委培生是什么意思 定向委培生和普通本科的区别

委培生是什么意思 定向委培生和普通本科的区别

委培是什么意思啊?委培生是什么意思?委培生是什么意思?什么是委培生?与正规招生的有什么区别?请问什么是委培生啊?委培生是什么?好不好?本文导航委培上班的是什么编制委培生有限制吗委培生怎么报名定向委培生和普通本科的区别委培生的前途专科委培生的好处和坏处委培上班的是什么编制委培即委托培养,也就是说某个单...

零基础学高数买什么书 学高数要看什么书

自学高等数学要看什么书呢?我想自学高等数学,应该读什么书?零基础,想学高等数学该怎么学?看什么书?高数入门的必读书籍有哪些值得推荐。本文导航自学高等数学入门教程自学用什么书高中数学零基础能学会高等数学吗学高数要看什么书自学高等数学入门教程难道你连高中都没有上,高数与你高中的知识联系也不大,认真学高数...

发表评论

访客

◎欢迎参与讨论,请在这里发表您的看法和观点。