二叉树有哪些应用?

在c++ STL中，以及许多其他语言的标准库中，如Java和c#。二叉搜索树用于实现set和map。

主要的应用程序是二叉搜索树。在这些数据结构中，搜索、插入和删除都非常快(关于log(n)操作)。

它们可以作为一种快速排序数据的方法。在O(log(n))处将数据插入二叉搜索树。然后遍历树，对它们进行排序。

当大多数人谈论二叉树时，他们通常会想到二叉搜索树，所以我将首先介绍它。

非平衡二叉搜索树实际上只对教育学生了解数据结构有用。这是因为，除非数据以相对随机的顺序进入，否则树很容易退化为最坏情况的形式，即链表，因为简单的二叉树是不平衡的。

一个很好的例子:我曾经不得不修复一些软件，它将数据加载到二叉树中进行操作和搜索。它把数据以排序的形式写出来:

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趋近于无穷大时会发生什么。有些人可能不同意，但如果你确定数据集将保持在某个大小以下，只要没有其他现成的数据，使用冒泡排序甚至是可以的:-)

至于二叉树的其他用途，还有很多，例如:

• 二进制堆，其中较高的键是大于或等于较低的键，而不是在左边(或在下面或等于和右边);
• 哈希树，类似于哈希表;
• 用于计算机语言编译的抽象语法树
• 霍夫曼树用于数据压缩;
• 用于网络流量的路由树。

考虑到我为搜索树生成了很多解释，我不愿详细介绍其他搜索树，但如果您愿意，这应该足以研究它们了。

你的程序语法，或者其他很多东西，比如自然语言，都可以用二叉树来解析(虽然不一定)。

java.util.Set的实现

• 在霍夫曼编码中使用了二叉树，它被用作压缩代码。
• 在二叉搜索树中使用了二叉树，它用于保存没有太多额外空间的数据记录。

也可以用于搜索/插入/删除哈希表，它通常比二叉搜索树(平衡与否)有更好的性能。

在需要搜索/插入/删除和排序的应用程序中，(平衡的)二叉搜索树将是有用的。排序可以在适当的位置(几乎，忽略递归所需的堆栈空间)，给定一个就绪的构建平衡树。它仍然是O(nlogn)，但有一个更小的常数因子，不需要额外的空间(除了新的数组，假设数据必须放入数组中)。另一方面，哈希表不能排序(至少不能直接排序)。

也许它们在一些复杂的算法中也很有用，但说实话，我什么也想不起来。如果我发现更多，我会编辑我的帖子。

其他树如f.e. B +树在数据库中广泛使用

最常见的应用之一是高效地以排序形式存储数据，以便快速访问和搜索存储的元素。例如，c++标准库中的std::map或std::set。

二叉树作为一种数据结构，对于表达式解析器和表达式求解器的各种实现非常有用。

它也可以用来解决一些数据库问题，例如，索引。

一般来说，二叉树是一种特定的基于树的数据结构的一般概念，各种特定类型的二叉树可以构造成具有不同性质的二叉树。

关于二叉树，还有一个有趣的例子没有提到，那就是递归求值的数学表达式。从实际的角度来看，它基本上是无用的，但它是一种有趣的方式来考虑这样的表达式。

基本上，树的每个节点都有一个值，这个值要么是自身固有的，要么是通过对其子节点的值进行操作来递归计算的。

例如，表达式(1+3)*2可以表示为:

    *
/ \
+   2
/ \
1   3

为了求表达式的值，我们要求父元素的值。这个节点又从它的子节点，一个加号运算符和一个只包含“2”的节点中获取它的值。加号运算符依次从值为“1”和“3”的子运算符中获取其值，并将它们相加，将4返回给返回8的乘法节点。

这种二叉树的使用在某种意义上类似于反向抛光表示法，因为执行操作的顺序是相同的。还有一点需要注意的是，它不一定是二叉树，只是最常用的操作符是二叉的。在最基本的层次上，这里的二叉树实际上只是一种非常简单的纯函数式编程语言。

争论二叉树的性能是没有意义的——它们不是一种数据结构，而是一组数据结构，都具有不同的性能特征。虽然在搜索方面不平衡二叉树确实比自平衡二叉树差得多，但有许多二叉树(如二进制尝试)对它们没有意义。

二叉树的应用

• 二叉搜索树 -用于数据不断进入/离开的许多搜索应用程序，例如许多语言库中的map和set对象。
• 二进制空间分区 -几乎在每个3D视频游戏中使用，以确定需要渲染的对象。
• 二进制试 -用于几乎所有的高带宽路由器，用于存储路由器表。
• 哈希树 -用于种子和专门的图像签名，其中哈希需要验证，但整个文件不可用。也用于区块链，例如。比特币。
• 堆 -用于实现高效的优先级队列，它反过来用于调度许多操作系统中的进程，路由器中的服务质量，和A* (用于人工智能应用的寻径算法，包括机器人和视频游戏)。也用于堆排序。
• 霍夫曼编码树 (芯片大学) -用于压缩算法，例如.jpeg和.mp3文件格式所使用的算法。
• 与树 -在密码应用程序中用于生成伪随机数树。
• 语法树 -由编译器和(隐式)计算器构造来解析表达式。
• Treap -用于无线网络和内存分配的随机数据结构。
• -树 -虽然大多数数据库使用某种形式的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元树更复杂，但就必要的总体比较而言，它们没有提供任何优势。

(然而，n-ary树在生态位环境中仍然有用。首先想到的例子是四叉树和其他空间分区树，其中每层只使用两个节点划分空间会使逻辑不必要地复杂;and B-trees在许多数据库中使用，其中限制因素不是在每个级别上进行多少比较，而是一次可以从硬盘加载多少节点)

在现代硬件上，由于糟糕的缓存和空间行为，二叉树几乎总是次优的。这也适用于(半)平衡的变种。如果您发现了它们，则说明性能不重要(或由比较函数主导)，或者更可能是由于历史或无知的原因。

二叉树是一种树状数据结构，其中每个节点最多有两个子节点，通常用“left”来区分。和“;right"。带有子节点的节点是父节点，子节点可以包含对父节点的引用。在树之外，经常会提到“根”。节点(所有节点的祖先)，如果它存在的话。数据结构中的任何节点都可以通过从根节点开始并重复跟随对左子节点或右子节点的引用来访问。在二叉树中，每个节点的次数最多为2。

二叉树很有用，因为正如你在图中看到的，如果你想找到树中的任何节点，你最多只需要找6次。例如，如果您想搜索节点24，您将从根节点开始。

• 根节点的值为31，大于24，所以要到左边的节点。
• 左边节点的值为15，小于24，所以要转到右边节点。
• 右边节点的值为23，小于24，所以您要转到右边节点。
• 右边节点的值是27，大于24，所以要转到左边节点。
• 左边节点的值是25，比24大，所以你到左边节点。
• 节点的值为24，这是我们要查找的键。

您可以看到，在第一次传递时就可以排除整个树的一半节点。左边子树的一半在第二个。这使得搜索非常有效。如果这是在4个欧元元素上完成的，你只需要搜索最多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找到

二叉树的应用:

1. 实现路由器中的路由表。
2. 数据压缩码
3. 表达式解析器和表达式求解器的实现
4. 解决数据库问题，如索引。
5. 表达式求值

二叉树最重要的应用之一是平衡二叉搜索树，比如:

• 红黑树
• AVL trees
• 替罪羊树

这些类型的树具有这样的特性，即通过每次插入或删除节点时进行旋转等操作，将左子树和右子树的高度差保持在较小的范围内。

因此，树的整体高度保持为log n的阶数，并且搜索、插入和删除节点等操作在O(log n)时间内执行。c++的STL也以集合和映射的形式实现了这些树。

这就是为什么基于Unix的操作系统很慢的原因。

摩尔斯电码的组织是一个二叉树。

几乎所有的数据库(和类数据库)程序都使用二叉树来实现它们的索引系统。

BST是一种二叉树，在Unix内核中用于管理一组虚拟内存区域(vma)。