Blu*_*eft 407
争论二进制树的性能是没有意义的 - 它们不是数据结构,而是一系列数据结构,都具有不同的性能特征.虽然不平衡二叉树确实比自平衡二叉树执行搜索更糟糕,但是有许多二元树(例如二进制尝试),"平衡"没有任何意义.
二叉树的应用
- 二进制搜索树 - 用于许多数据不断进入/离开的搜索应用程序,例如许多语言库中的对象
map和set对象. - 二进制空间分区 - 几乎在每个3D视频游戏中用于确定需要渲染的对象.
- 二进制尝试 - 几乎在每个高带宽路由器中用于存储路由器表.
- 哈希树 - 用于p2p程序和专门的图像签名,其中需要验证哈希,但整个文件不可用.
- 堆 - 用于实现高效优先级队列,后者又用于许多操作系统中的调度过程,路由器中的服务质量和A*(AI应用程序中使用的路径查找算法,包括机器人和视频游戏).也用于堆排序.
- 霍夫曼编码树(Chip Uni) - 用于压缩算法,例如.jpeg和.mp3文件格式使用的算法.
- GGM树 - 用于加密应用程序以生成伪随机数树.
- 语法树 - 由编译器和(隐式)计算器构造来解析表达式.
- Treap - 用于无线网络和内存分配的随机数据结构.
- T树 - 虽然大多数数据库使用某种形式的B树来存储驱动器上的数据,但是将所有(大多数)数据保存在内存中的数据库通常使用T树来执行此操作.
二元树比n-ary树更常用于搜索的原因是n-ary树更复杂,但通常没有提供真正的速度优势.
在具有m节点的(平衡)二叉树中,从一个级别移动到下一个级别需要一个比较,并且存在log_2(m)级别,用于总计log_2(m)比较.
相反,n-ary树将需要log_2(n)比较(使用二进制搜索)以移动到下一级别.由于存在log_n(m)总水平,因此搜索将需要log_2(n)*log_n(m)= log_2(m)比较总计.因此,虽然n-ary树更复杂,但它们在必要的总比较方面没有任何优势.
(然而,n-ary树在利基情况下仍然有用.立即想到的例子是四叉树和其他空间分区树,其中每个级别仅使用两个节点的分割空间将使逻辑不必要地复杂;并且在许多数据库中使用的B树,其中限制因素不是在每个级别进行多少次比较,而是一次可以从硬盘驱动器加载多少个节点)
- @MichaelErickson你,呃,读过这个答案吗？因为这正是我回答的问题. (4认同)
- > Treap - 用于无线网络和内存分配的随机数据结构.它们在内存分配和无线网络中的用途如何？ (3认同)
pax*_*blo 272
当大多数人谈论二叉树时,他们往往不会考虑二元搜索树,所以我将首先介绍它.
非平衡二叉搜索树实际上对于教育学生数据结构更有用.这是因为,除非数据即将在相对随机的顺序,树可以很容易退化为它的最坏情况下的形式,这是一个链表,因为简单的二进制树是不均衡的.
一个很好的例子:我曾经不得不修复一些将其数据加载到二叉树中进行操作和搜索的软件.它以排序的形式写出数据:
Alice
Bob
Chloe
David
Edwina
Frank
因此,当重新阅读时,最后得到以下树:
Alice
/ \
= Bob
/ \
= Chloe
/ \
= David
/ \
= Edwina
/ \
= Frank
/ \
= =
这是堕落的形式.如果你在那棵树上寻找弗兰克,你必须在找到他之前搜索所有六个节点.
二进制树在平衡它们时变得非常有用.这涉及通过其根节点旋转子树,以便任何两个子树之间的高度差小于或等于1.将这些名称一次一个地添加到平衡树中将为您提供以下序列:
1. Alice
/ \
= =
2. Alice
/ \
= Bob
/ \
= =
3. Bob
_/ \_
Alice Chloe
/ \ / \
= = = =
4. Bob
_/ \_
Alice Chloe
/ \ / \
= = = David
/ \
= =
5. Bob
____/ \____
Alice David
/ \ / \
= = Chloe Edwina
/ \ / \
= = = =
6. Chloe
___/ \___
Bob Edwina
/ \ / \
Alice = David Frank
/ \ / \ / \
= = = = = =
实际上,当添加条目时,您可以看到整个子树向左旋转(在步骤3和6中),这为您提供了一个平衡的二叉树,其中最坏情况查找O(log N)而不是O(N简并形式给出的.在任何时候,最高NULL(=)与最低值之间的差异不超过一个级别.并且,在上述最后的树,你可以只看着三个节点找到弗兰克(Chloe,Edwina,最后Frank).
当然,当你使它们成为平衡的多路树而不是二元树时,它们会变得更有用.这意味着每个节点包含多个项目(从技术上讲,它们包含N个项目和N + 1个指针,二叉树是具有1个项目和2个指针的单向多路树的特殊情况).
使用三向树,您最终得到:
Alice Bob Chloe
/ | | \
= = = David Edwina Frank
/ | | \
= = = =
这通常用于维护项目索引的键.我编写了针对硬件优化的数据库软件,其中节点的大小与磁盘块的大小完全相同(例如,512字节),并且您可以将尽可能多的密钥放入单个节点中.该指针在这种情况下,实际上是创纪录的数字成固定长度的记录直接访问文件的索引文件分开(这样的记录号X可以通过只求被发现X * record_length).
例如,如果指针是4个字节且密钥大小为10,则512字节节点中的密钥数为36.这是36个密钥(360个字节)和37个指针(148个字节),总共508个字节每个节点浪费4个字节.
多路密钥的使用引入了两阶段搜索的复杂性(多路搜索找到正确的节点结合小的顺序(或线性二进制)搜索,以找到节点中的正确密钥)但优势在于减少磁盘I/O比弥补这一点.
我认为没有理由为内存结构做这件事,你最好坚持使用平衡的二叉树并保持代码简单.
另外请记住,当数据集很小时,O(log N)过度的优势O(N)并不会真正出现.如果您使用多向树将十五个人存储在地址簿中,那可能会有些过分.当您在过去十年中存储来自您的十万客户的每个订单之类的东西时,优势就来了.
big-O表示法的重点是指出N无限接近时会发生什么.有些人可能不同意,但如果您确定数据集将保持在一定的大小以下,只要没有其他可用的东西,甚至可以使用冒泡排序:-)
至于二叉树的其他用途,有很多,例如:
- 二进制堆,其中较高的键高于或等于较低的键而不是左侧(或低于或等于和右);
- 哈希树,类似于哈希表;
- 用于编译计算机语言的抽象语法树;
- 用于压缩数据的霍夫曼树;
- 路由树以进行网络流量.
鉴于我为搜索树生成了多少解释,我很想在其他人上详细介绍,但如果你愿意,这应该足以研究它们.
- +1这样我们写的答案; 再向我介绍平衡的多路树,这是我之前没有遇到的事情. (24认同)
- 我不同意你的断言,即除了教育学生之外,它们几乎没用.即使是简单的静态数据结构,它们也非常有用.然而,这是一个非常好的书面和图解答案,所以其余的+1.:-) (3认同)
Dri*_*ise 59
二叉树是树数据结构,其中每个节点最多具有两个子节点,通常被区分为"左"和"右".具有子节点的节点是父节点,子节点可以包含对其父节点的引用.在树之外,通常会引用"根"节点(所有节点的祖先)(如果存在).可以通过从根节点开始并反复跟随对左子节点或右子节点的引用来到达数据结构中的任何节点.在二叉树中,每个节点的度数最大为2.
二叉树很有用,因为正如您在图片中看到的那样,如果要在树中找到任何节点,则只需要查看最多6次.例如,如果要搜索节点24,则应从根目录开始.
- 根的值为31,大于24,因此您转到左侧节点.
- 左侧节点的值为15,小于24,因此您转到右侧节点.
- 右侧节点的值为23,小于24,因此您转到右侧节点.
- 右侧节点的值为27,大于24,因此您转到左侧节点.
- 左侧节点的值为25,大于24,因此您转到左侧节点.
- 该节点的值为24,这是我们正在寻找的关键.
此搜索如下所示:
您可以看到在第一次传递时可以排除整个树的一半节点.第二个是左子树的一半.这使得搜索非常有效.如果这是在40 亿个元素上完成的,那么你最多只能搜索32次.因此,树中包含的元素越多,搜索效率就越高.
删除可能会变得复杂.如果节点有0或1个子节点,那么只需移动一些指针即可排除要删除的节点.但是,您无法轻松删除包含2个子节点的节点.所以我们采取捷径.假设我们想要删除节点19.
由于试图确定左右指针的移动位置并不容易,因此我们找到一个替代它的方法.我们去左侧的子树,尽可能向右走.这为我们提供了我们想要删除的节点的下一个最大价值.
现在我们复制除了左右指针之外的所有18个内容,并删除原始的18个节点.
为了创建这些图像,我实现了一个AVL树,一个自平衡树,这样在任何时间点,树在叶节点(没有子节点的节点)之间至多有一个级别的差异.这使树不会变得歪斜,并保持最长的O(log n)搜索时间,插入和删除所需的时间更长.
这是一个示例,展示了我的AVL树如何保持自己尽可能紧凑和平衡.
在排序数组中,查找仍然会O(log(n))像树一样,但随机插入和删除将采用O(n)而不是树O(log(n)).一些STL容器使用这些性能特征是有利的,因此插入和移除时间最多O(log n),这是非常快的.其中一些容器是map,multimap,set,和multiset.
有关AVL树的示例代码,请访问http://ideone.com/MheW8
- 如果你正在处理二进制*搜索*树(它本身很平衡),你只需要搜索O(log n).任意二进制树没有排序约束,随机BST有搜索复杂度O(log*) H*). (4认同)
Clu*_*ess 10
未提及的二叉树的一个有趣示例是递归计算的数学表达式.从实际的角度来看,它基本上是无用的,但它是一种有趣的方式来思考这些表达.
基本上,树的每个节点都有一个本身固有的值,或者通过对其子节点值进行操作来递归计算.
例如,表达式(1+3)*2可以表示为:
*
/ \
+ 2
/ \
1 3
为了评估表达式,我们要求父级的值.该节点依次从其子节点,加号运算符和仅包含"2"的节点获取其值.加号运算符依次从值为"1"和"3"的子项中获取其值,并将它们相加,并将4返回到返回8的乘法节点.
在某种意义上,这种二叉树的使用类似于反向抛光符号,因为执行操作的顺序是相同的.还有一点需要注意的是,它不一定必须是二叉树,它只是最常用的运算符是二进制的.在最基本的层面上,这里的二叉树实际上只是一种非常简单的纯函数式编程语言.
我不认为"纯"二叉树有任何用处.(除了教育目的)平衡二叉树,如红黑树或AVL树更有用,因为它们保证O(logn)操作.正常的二叉树可能最终成为一个列表(或几乎列表),并且在使用大量数据的应用程序中并不真正有用.
平衡树通常用于实现地图或集合.它们也可以用于O(nlogn)中的排序,即使存在更好的方法.
也可用于搜索/插入/删除哈希表,其通常具有比二叉搜索树更好的性能(平衡或不平衡).
如果需要搜索/插入/删除和排序,那么(平衡的)二进制搜索树将是有用的应用程序.给定一个现成的平衡树,Sort可以就地(几乎忽略递归所需的堆栈空间).它仍然是O(nlogn)但是具有较小的常数因子并且不需要额外的空间(除了新数组之外,假设必须将数据放入数组中).另一方面,哈希表无法排序(至少不能直接排序).
也许它们在一些复杂的算法中也很有用,但是我没有想到什么.如果我找到更多,我将编辑我的帖子.
其他树如fe B +树在数据库中被广泛使用
最常见的应用之一是以有序的形式有效地存储数据,以便快速访问和搜索存储的元素.例如,std::map或std::set在C++标准库中.
作为数据结构的二叉树对表达式解析器和表达式求解器的各种实现很有用.
它还可以用于解决一些数据库问题,例如索引.
通常,二叉树是特定的基于树的数据结构的一般概念,并且可以构造具有不同属性的各种特定类型的二叉树.
在C++ STL中,以及其他语言中的许多其他标准库,如Java和C#.二叉搜索树用于实现集合和映射.
- 实际上在C++中,集合/映射通常基于红黑树,这是一种具有更多限制的二叉搜索树. (2认同)
在现代硬件上，由于缓存和空间行为不佳，二叉树几乎总是次优的。这也适用于（半）平衡变体。如果您找到它们，则说明性能不重要（或由比较函数主导），或更可能是由于历史或无知的原因。
- 与什么相比次优？ (2认同)