首页 > 常见问题 > 正文

平衡二叉树的特点有哪些?

烟雨青岚
发布: 2020-06-29 10:18:01
原创
9675 人浏览过

平衡二叉树的特点有:1、非叶子节点最多拥有两个子节点;2、非叶子节值大于左边子节点、小于右边子节点;3、树的左右两边的层级数相差不会大于1;4、没有值相等重复的节点。

平衡二叉树的特点有哪些?

平衡二叉树特点:

(1)非叶子节点最多拥有两个子节点;

(2)非叶子节值大于左边子节点、小于右边子节点;

(3)树的左右两边的层级数相差不会大于1;

(4)没有值相等重复的节点;

平衡二叉树概念

平衡二叉树是基于二分法的策略提高数据的查找速度的二叉树的数据结构;

特点:

平衡二叉树是采用二分法思维把数据按规则组装成一个树形结构的数据,用这个树形结构的数据减少无关数据的检索,大大的提升了数据检索的速度;平衡二叉树的数据结构组装过程有以下规则:

(1)非叶子节点只能允许最多两个子节点存在。

(2)每一个非叶子节点数据分布规则为左边的子节点小当前节点的值,右边的子节点大于当前节点的值(这里值是基于自己的算法规则而定的,比如hash值);

平衡树的层级结构:因为平衡二叉树查询性能和树的层级(h高度)成反比,h值越小查询越快、为了保证树的结构左右两端数据大致平衡降低二叉树的查询难度一般会采用一种算法机制实现节点数据结构的平衡,实现了这种算法的有比如Treap、红黑树,使用平衡二叉树能保证数据的左右两边的节点层级相差不会大于1.,通过这样避免树形结构由于删除增加变成线性链表影响查询效率,保证数据平衡的情况下查找数据的速度近于二分法查找;

更多相关知识,请访问 PHP中文网!!

以上是平衡二叉树的特点有哪些?的详细内容。更多信息请关注PHP中文网其他相关文章!

相关标签:
来源:php.cn
本站声明
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn
热门教程
更多>
最新下载
更多>
网站特效
网站源码
网站素材
前端模板