首页 > 代码库 > 二叉树的优点和缺点
二叉树的优点和缺点
二叉排序树是一种比较有用的折衷方案。
数组的搜索比较方便,可以直接用下标,但删除或者插入某些元素就比较麻烦。
链表与之相反,删除和插入元素很快,但查找很慢。
二叉排序树就既有链表的好处,也有数组的好处。
在处理大批量的动态的数据是比较有用。
文件系统和数据库系统一般都采用树(特别是B树)的数据结构数据,主要为排序和检索的效率。二叉树是一种最基本最典型的排序树,用于教学和研究树的特性,本身很少在实际中进行应用,因为缺点太明显了(看看教科书怎么说的)。就像冒泡排序一样,虽然因为效率问题并不实用,单不失一种教学例子的好手段。
平衡二叉树都有哪些应用场景
二叉树支持动态的插入和查找,保证操作在O(height)时间,这就是完成了哈希表不便完成的工作,动态性。但是二叉树有可能出现worst-case,如果输入序列已经排序,则时间复杂度为O(N)
平衡二叉树/红黑树就是为了将查找的时间复杂度保证在O(logN)范围内。
所以如果输入结合确定,所需要的就是查询,则可以考虑使用哈希表,如果输入集合不确定,则考虑使用平衡二叉树/红黑树,保证达到最大效率
平衡二叉树主要优点集中在快速查找。
如果你知道SGI/STL的set/map底层都是用红黑树(平衡二叉树的一种)实现的,相信你会对这些树大有兴趣。
缺点:
顺序存储可能会浪费空间(在非完全二叉树的时候),但是读取某个指定的节点的时候效率比较高O(0)
链式存储相对二叉树比较大的时候浪费空间较少,但是读取某个指定节点的时候效率偏低O(nlogn)
二叉树的优点和缺点
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。