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

appeal2022-11-21 08:02:07996

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

本文导航

二叉树深度是怎么算的

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

满二叉树是将一个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

标签: 学习
分享给朋友:

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

重庆市重点中学 目前重庆重点中学排名

重庆市重点中学 目前重庆重点中学排名

重庆市排名前十的中学是哪十个啊重庆市重点中学排名,重庆前50名重点中学,2021重庆前50名重点中学。本文导航重庆前十名中学排名榜目前重庆重点中学排名重庆市高中排名前100中学重庆前十名中学排名榜1 重庆一中 2 南开中学 3 重庆八中4 育才中学 5 巴蜀中学 6 外语学校7 西师附中 8 求精中...

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

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

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

黑龙江省社会科学院怎么样 黑龙江省社会科学院研究生院毕业后好就业吗

黑龙江省社会科学院怎么样 黑龙江省社会科学院研究生院毕业后好就业吗

黑龙江社会科学院怎么样?黑龙江省社会科学院的研究生怎么样啊,学校看着不怎么好啊,求详解?黑龙江省社会科学院研究生院毕业后好就业吗?黑龙江省社会科学院的基本情况,黑龙江省社会科学院怎么样?黑龙江省社会科学院怎么样?本文导航黑龙江社会科学院怎么样黑龙江省社会科学院的研究生怎么样啊,学校看着不怎么好啊,求...

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

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

不想学微机原理怎么办 通信系统原理 ,数字信号处理 ,微机原理及应用对于没学过的学生而言,哪门最容易自学

微机原理及汇编语言 看不懂,该怎么学呀?微机原理听说很难哈……自学微机原理可能吗?学数学的 再难的数学都可以学懂 可是微机原理一点儿都看不懂 急 请教一下这门该怎么学 谢谢!?微机原理怎么学?通信系统原理 ,数字信号处理 ,微机原理及应用对于没学过的学生而言,哪门最容易自学,微机原理学了有什么用,需...

文史基础考什么 目前专升本报什么专业比较好

历史学专业基础是考什么?事业单位 文史哲学基础知识考试范围是什么?事业单位的文史哲学基础知识包括哪些?可以具体一点点吗?O(∩_∩)O谢谢?兰石化2015单招文史类考生考察什么基础知识?文史类专接本有哪些专业?考哪些科目,文史综合从哪里刷题?本文导航历史学专业基础是考什么?事业单位考试中综合知识考什...

发表评论

访客

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