二叉树有哪些应用？

Question

我想知道二叉树的特殊应用是什么。你能举一些真实的例子吗？

Answer 1

争论二叉树的性能是没有意义的-它们不是数据结构，而是一系列具有不同性能特征的数据结构。尽管不平衡的二叉树的确比自平衡的二叉树在搜索方面要差得多，但是有很多二叉树（例如二叉树尝试）对它们而言“平衡”毫无意义。二叉树的应用二进制搜索树 -用于许多不断输入/离开数据的搜索应用程序中，例如许多语言库中的map和set对象。二进制空间分区 -几乎在所有3D视频游戏中都使用，以确定需要渲染哪些对象。二进制尝试 -几乎在每个高带宽路由器中用于存储路由器表。散列树 -用于p2p程序和专用图像签名中，在散列树中需要验证散列，但整个文件不可用。堆 -用于实现高效的优先级队列，这些优先级队列又用于调度许多操作系统中的进程，路由器中的服务质量以及A * （用于AI应用程序（包括机器人和视频游戏）的路径查找算法）。也用于堆排序。霍夫曼编码树（Chip Uni）-用于压缩算法，例如.jpeg和.mp3文件格式所使用的算法。GGM树 -在加密应用程序中用于生成伪随机数树。语法树 -由编译器和（隐式）计算器构造以解析表达式。Treap-无线网络和内存分配中使用的随机数据结构。T树 -尽管大多数数据库使用某种形式的B树将数据存储在驱动器上，但是将所有（大部分）数据存储在内存中的数据库经常使用T树来这样做。二元树比n元树更常用于搜索的原因是n元树更复杂，但通常没有实际的速度优势。在带有m节点的（平衡）二叉树中，从一个级别移至下一个级别需要一个比较，并且存在多个log_2(m)级别，以进行总计log_2(m)比较。相比之下，n元树将需要log_2(n)比较（使用二进制搜索）才能进入下一个级别。由于存在log_n(m)总计级别，因此搜索将需要log_2(n)*log_n(m)= log_2(m)比较总计。因此，尽管n元树比较复杂，但是在进行必要的总比较方面它们没有任何优势。（但是，n元树在小生境中仍然有用。立即想到的例子是四叉树和其他空间划分树，其中每级仅使用两个节点划分空间将使逻辑不必要地复杂；以及许多数据库中使用的B树，其局限性不是每个级别进行多少比较，而是一次可以从硬盘驱动器加载多少个节点）

Answer 2

当大多数人谈论二叉树，他们不是没有想过二进制更多的时候是搜索树，所以我会先覆盖。实际上，不平衡的二进制搜索树仅对教育学生有关数据结构的作用有用。这是因为，除非该数据是在一个相对随机的顺序来了，树可以轻松地沦为其最坏情况下的形式，这是一个链表，因为简单的二进制树不均衡。一个很好的例子：我曾经不得不修复一些将其数据加载到二叉树中进行操作和搜索的软件。它以排序形式写出数据：AliceBobChloeDavidEdwinaFrank这样，当读回它时，最终得到以下树：  Alice /     \=       Bob       /   \      =     Chloe           /     \          =       David                 /     \                =       Edwina                       /      \                      =        Frank                              /     \                             =       =这是简并形式。如果要在那棵树中寻找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）。当然，当您使它们平衡多向树而不是二叉树时，它们会变得更加有用。这意味着每个节点拥有一个以上的项目（从技术上讲，它们包含N个项目和N + 1个指针，二叉树是具有1个项目和2个指针的1向多路树的特例）。使用三向树，您最终得到：  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)over 的优点O(N)并没有真正显现出来。如果您使用多向树将15个人存储在通讯录中，则可能是过大了。当您存储过去十年来来自十万个客户的每个订单之类的东西时，优势就来了。big-O表示法的全部要点是指出N接近无限时会发生什么。某些人可能会不同意，但是如果您确定数据集将保持在一定大小以下，并且只要没有其他可用的可用方法，则使用冒泡排序甚至可以，:-)至于二叉树的其他用途，有很多，例如：二进制堆，其中较高的键高于或等于较低的键，而不是位于（或低于或等于并等于）左边；哈希树，类似于哈希表；用于编译计算机语言的抽象语法树；霍夫曼树，用于压缩数据；网络流量的路由树。鉴于我为搜索树生成了多少解释，我不愿透露其他详细信息，但是您可以根据需要对它们进行足够的研究。

Answer 3

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