我想知道二叉树的具体应用是什么。你能举几个例子吗?
当前回答
在现代硬件上,由于糟糕的缓存和空间行为,二叉树几乎总是次优的。这也适用于(半)平衡的变种。如果您发现了它们,则说明性能不重要(或由比较函数主导),或者更可能是由于历史或无知的原因。
其他回答
当大多数人谈论二叉树时,他们通常会想到二叉搜索树,所以我将首先介绍它。
非平衡二叉搜索树实际上只对教育学生了解数据结构有用。这是因为,除非数据以相对随机的顺序进入,否则树很容易退化为最坏情况的形式,即链表,因为简单的二叉树是不平衡的。
一个很好的例子:我曾经不得不修复一些软件,它将数据加载到二叉树中进行操作和搜索。它把数据以排序的形式写出来:
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(=)与最低的NULL(=)的差异都不超过一个级别。在上面的最后一棵树中,您可以通过查看三个节点(Chloe、Edwina和最后的Frank)找到Frank。
当然,当你把它们做成平衡的多路树而不是二叉树时,它们会变得更有用。这意味着每个节点拥有一个以上的项(从技术上讲,它们拥有N个项和N+1个指针,二叉树是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)的优势并不会真正显现出来。如果您使用多路树来存储15个人在您的地址簿,这可能是多余的。当您存储过去十年来自数十万客户的每一笔订单时,优势就显现出来了。
大o符号的全部意义在于指出当N趋于无穷时会发生什么。有些人可能不同意,但如果你确定数据集将保持在某个大小以下,只要没有其他现成的数据,使用冒泡排序甚至是可以的:-)
至于二叉树的其他用途,还有很多,例如:
二进制堆,其中较高的键高于或等于较低的键,而不是在左侧(或低于或等于或右); 哈希树,类似于哈希表; 用于计算机语言编译的抽象语法树 霍夫曼树用于数据压缩; 用于网络流量的路由树。
考虑到我为搜索树生成了很多解释,我不愿详细介绍其他搜索树,但如果您愿意,这应该足以研究它们了。
主要应用是二叉搜索树。这是一种数据结构,其中搜索、插入和删除都非常快(大约log(n)次操作)
关于二叉树,还有一个有趣的例子没有提到,那就是递归求值的数学表达式。从实际的角度来看,它基本上是无用的,但它是一种有趣的方式来考虑这样的表达式。
基本上,树的每个节点都有一个值,这个值要么是自身固有的,要么是通过对其子节点的值进行操作来递归计算的。
例如,表达式(1+3)*2可以表示为:
*
/ \
+ 2
/ \
1 3
为了求表达式的值,我们要求父元素的值。这个节点又从它的子节点,一个加号运算符和一个只包含“2”的节点中获取它的值。加号运算符依次从值为“1”和“3”的子运算符中获取其值,并将它们相加,将4返回给返回8的乘法节点。
这种二叉树的使用在某种意义上类似于反向抛光表示法,因为执行操作的顺序是相同的。还有一点需要注意的是,它不一定是二叉树,只是最常用的操作符是二叉的。在最基本的层次上,这里的二叉树实际上只是一种非常简单的纯函数式编程语言。
它们可以作为一种快速排序数据的方法。在O(log(n))处将数据插入二叉搜索树。然后遍历树,对它们进行排序。
在c++ STL中,以及许多其他语言的标准库中,如Java和c#。二叉搜索树用于实现set和map。