二叉树有哪些应用？
我想知道二叉树的特定应用是什么。 你能举一些真实的例子吗？
争吵二叉树的性能是没有意义的 – 它们不是一个数据结构，而是一系列数据结构，它们都具有不同的性能特征。 虽然不平衡的二叉树比自平衡二叉树的search性能差得多，但有许多二叉树（如二进制尝试） ，其中“平衡”没有意义。
二叉树的应用
- 二进制search树 – 用于数据不断进出的许多search应用程序，如许多语言库中的
map和set对象。 - 二进制空间分区 – 几乎用于每个3Dvideo游戏，以确定需要渲染什么对象。
- 二进制尝试 – 几乎用于存储路由器表的每个高带宽路由器。
- 散列树 – 用于p2p程序和专门的图像签名，其中散列需要validation，但整个文件不可用。
- 堆 – 用于实现高效的优先级队列，这些优先级队列又被用于许多操作系统中的调度进程，路由器的服务质量和A * （AI应用中使用的path寻找algorithm，包括机器人和video游戏） 。 也用于堆sorting。
- Huffman编码树 （ Chip Uni ） – 用于压缩algorithm，如.jpeg和.mp3文件格式所使用的algorithm。
- GGM树 – 用于encryption应用程序生成一个伪随机数树。
- 语法树 – 由编译器和（隐含）计算器构造来parsingexpression式。
- Treap – 无线networking和内存分配中使用的随机数据结构。
- T树 – 尽pipe大多数数据库使用某种forms的B树来将数据存储在驱动器上，但是将所有（大部分）数据保存在内存中的数据库通常使用T树来实现。
二叉树比n叉树更常用于search的原因是n叉树比较复杂，但通常不会提供真正的速度优势。
在具有m节点的（平衡）二叉树中，从一个级别移动到另一个级别需要比较，并且存在log_2(m)级别，总共log_2(m)比较。
相比之下，n元树将需要log_2(n)比较（使用二进制search）来移动到下一个级别。 由于总数为log_n(m) ，所以search将需要log_2(n)*log_n(m) = log_2(m)总和。 所以，尽pipen-ary树更复杂，但它们在必要的总比较方面没有任何优势。
（但是，n元树在小生境中仍然有用，例如四叉树和其他空间分割树，在每个级别只用两个节点来划分空间会使得逻辑不必要的复杂;在许多数据库中使用B树 ，其限制因素不是在每个级别完成多less比较，而是一次可以从硬盘驱动器加载多less个节点）
当大多数人谈论二叉树时，他们更多的时候并不考虑二叉search树，所以我会先介绍一下。
一个非平衡的二叉search树实际上是有用的教育学生关于数据结构。
这是因为，除非数据以相对随机的顺序进入，否则树会很容易退化为最坏的情况，这是一个链表，因为简单的二叉树是不平衡的。
一个很好的例子：我曾经不得不修复一些将数据加载到二叉树中进行操作和search的软件。 它以sorting的forms写出数据：
Alice Bob Chloe David Edwina Frank
所以，当读回来，结束了以下树：
Alice / \ = Bob / \ = Chloe / \ = David / \ = Edwina / \ = Frank / \ = =
这是退化的forms。 如果你在那棵树上寻找弗兰克，你必须在find他之前search全部六个节点。
二元树在平衡它们时变得真正有用。 这包括旋转子树通过它们的根节点，以便任何两个子树之间的高度差小于或等于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 / \ / \ / \ = = = = = =
实际上，当条目被添加时，您可以看到整个子树向左旋转，这就为您提供了一个平衡的二叉树，其中最坏的情况查找是O（logN），而不是退化forms给出的O（N）。 最高的NULL（ = ）与最低的不同的级别不一样。 而且，在上面的最后一棵树中，只能看到三个节点（ Chloe ， Edwina ，最后是Frank ）才能findFrank。
当然，当你使它们成为均衡的多路树而不是二叉树时，它们变得更有用。 这意味着每个节点拥有多个项目（技术上，它们包含N项和N + 1个指针，二叉树是具有1项和2个指针的单向多路树的特例）。
用三叉树，你会得到：
Alice Bob Chloe / | | \ = = = David Edwina Frank / | | \ = = = =
这通常用于维护项目索引的键。 我已经编写了针对硬件优化的数据库软件，其中一个节点正好是一个磁盘块的大小（比如说512个字节），并且将尽可能多的关键字放在一个节点中。 这种情况下的指针实际上是将数字logging到与索引文件分离的固定长度logging直接访问文件中（因此可以通过寻找X * record_length来findlogging号码X ）。
例如，如果指针是4个字节，密钥大小是10，则512字节节点中的密钥数量是36个。这是36个密钥（360个字节）和37个指针（148个字节），总共508个字节与每个节点浪费了4个字节。
多路键的使用引入了两阶段search的复杂性（多路search以find正确的节点并结合小序列search来find节点中的正确密钥），但是减less磁盘I / O比弥补这一点。
我认为没有理由为内存结构做这件事情，你最好坚持一个平衡的二叉树，并保持简单的代码。
另外请记住，当O（N）超过O（N）时，O（log N）的优势在数据集很小的时候并不真正出现。 如果您使用多路树将十五个人存储在您的地址簿中，则可能是矫枉过正。 当您在过去的十年里存储了几十万客户的每一笔订单时，这些优势就来了。
大O符号的全部要点是指出N接近无穷大时会发生什么。 有些人可能会不同意，但是如果你确信数据集将保持在一定的大小以下，那么使用冒泡sorting就可以了，只要没有别的东西可用:-)
至于二叉树的其他用途，还有很多，比如：
- 二进制堆，其中较高的键高于或等于较低的键，而不是在左边（或下面或等于和右边）;
- 散列树，类似于散列表;
- 用于编译计算机语言的抽象语法树;
- 霍夫曼树压缩数据;
- 为networkingstream量路由树。
考虑到我为search树产生了多less解释，我不愿意详细讨论其他的细节，但是如果你愿意的话，这应该足以研究它们。
二叉树是一种树型数据结构，每个节点至多有两个子节点，通常区分为“左”和“右”。 有孩子的节点是父节点，子节点可能包含父母的引用。 在树之外，如果存在的话，通常会有对“根”节点（所有节点的祖先）的引用。 数据结构中的任何节点都可以通过从根节点开始并重复引用左侧或右侧子节点来访问。 在二叉树中，每个节点的度数最多为2。
二叉树是有用的，因为正如你在图片中看到的，如果你想在树中find任何节点，你只需要看最多6次。 例如，如果你想search节点24，你可以从根开始。
- 根的值是31，大于24，所以你去了左边的节点。
- 左节点的值是15，小于24，所以你去右节点。
- 正确的节点值为23，小于24，所以你去右边的节点。
- 正确的节点值是27，这是大于24，所以你去左边的节点。
- 左节点的值是25，大于24，所以你去了左边的节点。
- 该节点的值为24，这是我们正在寻找的关键。
此search如下所示： 
您可以看到，您可以在第一遍中排除整个树的一半节点。 在第二个左边的子树的一半。 这使得非常有效的search。 如果这是在40 亿个元素上完成的，那么你只需要search最多32次。 因此，树中包含的元素越多，search效率就越高。
删除可能变得复杂。 如果节点有0个或1个孩子，那么只需要移动一些指针来排除要删除的指针。 但是，您不能轻松删除具有两个孩子的节点。 所以我们采取一个捷径。 假设我们想要删除节点19。
由于试图确定将左右指针移动到何处并不容易，因此我们find一个replace它。 我们去到左边的子树，尽可能地去我们可以去的地方。 这给了我们下一个我们想要删除的节点的最大值。
现在我们复制18个内容的所有内容，除了左边和右边的指针，并删除原来的18个节点。
为了创build这些图像，我实现了一个AVL树，一个自平衡树，以便在任何时间点，树在叶节点（没有子节点的节点）之间至多有一个不同的级别。 这样可以防止树偏斜，并保持最大的O(log n)search时间，同时插入和删除所需的时间也稍多一些。
下面是一个示例，展示了我的AVL树如何保持自己的紧凑和平衡。
在一个有序的数组中，查找仍然需要O(log(n)) ，就像树一样，但是随机的插入和移除需要O（n）而不是树的O(log(n)) 。 一些STL容器使用这些性能特征是有利的，所以插入和移除时间最多为O(log n) ，这是非常快的。 其中一些容器是map ， multimap ， set和multiset 。
摩尔斯电码的组织是一棵二叉树。
- 二叉树用于霍夫曼编码 ，用作压缩编码。
- 二叉树用于二叉search树 ，这对于维护数据logging没有太多额外的空间。
主要应用程序是二叉search树 。 这些数据结构中search，插入和删除都非常快（关于log(n)操作）
没有提到的二叉树的一个有趣的例子是recursion评估的mathexpression式。 从实际的angular度来看，这基本上是无用的，但想想这种expression方式是一种有趣的方式。
基本上树的每个节点都有一个或者是自身固有的值，或者是通过对其子元素的值进行recursion评估。
例如，expression式(1+3)*2可以表示为：
* / \ + 2 / \ 1 3
为了评估expression，我们要求父母的价值。 这个节点又从它的子节点，一个加号运算符和一个简单地包含'2'的节点获取它的值。 加运算符依次从值为“1”和“3”的子元素中获取其值，并将它们相加，返回4到返回8的乘法节点。
二叉树的使用与某种意义上的逆波兰符号类似，因为执行操作的顺序是相同的。 还有一点要注意的是，它不一定是二叉树，只是最常用的运算符是二进制的。 在最基本的层面上，这里的二叉树其实就是一个非常简单的纯函数式编程语言。
最常见的应用之一是以有序的forms有效地存储数据，以便快速访问和search存储的元素。 例如，C ++标准库中的std::map或std::set 。
作为数据结构的二叉树对于expression式parsing器和expression式求解器的各种实现是有用的。
它也可以用来解决一些数据库问题，例如索引。
通常，二叉树是特定的基于树的数据结构的一般概念，并且可以构build具有不同属性的各种特定types的二叉树。
二叉树的应用：
- 在路由器中实现路由表 。
- 数据压缩代码
- expression式分析器和expression式求解器的实现
- 解决索引等数据库问题 。
- expression评估
我不认为有什么用“纯”的二叉树。 （除了教育目的）平衡二叉树，如红黑树或AVL树更有用，因为它们保证O（logn）操作。 普通的二叉树可能最终会成为一个列表（或几乎是列表），并且在使用大量数据的应用程序中并不是很有用。
平衡树通常用于实现地图或集合。 它们也可以用于O（nlogn）中的sorting，甚至有更好的方法来做到这一点。
也可以使用search/插入/删除哈希表 ，通常比二叉search树（平衡或不平衡）具有更好的性能。
如果需要search/插入/删除和sorting，那么（平衡的）二叉search树将是有用的应用。 sorting可以是就地（几乎忽略了recursion所需的堆栈空间），给定一个准备好的构build平衡树。 它仍然是O（nlogn），但具有较小的常数因子，并且不需要额外的空间（除了新的数组，假设数据必须放入数组中）。 另一方面，哈希表不能被sorting（至less不是直接的）。
也许他们在一些复杂的algorithm中也是有用的，但是我没有想到什么。 如果我发现更多，我将编辑我的post。
其他树木，如Fe B +树，被广泛用于数据库
在C ++ STL和其他许多其他语言的标准库中，如Java和C＃。 二叉search树被用来实现集合和映射。
它们可以用作对数据进行sorting的快速方法。 将数据插入O（log（n））的二叉search树中。 然后遍历树，以便对它们进行sorting。
二叉树最重要的应用之一是平衡二叉search树，如：
- 红黑树
- AVL树
- 替罪羊树
这些types的树具有这样的性质，即每次插入或删除节点时，通过进行像旋转一样的操作来保持左子树和右子树的高度差别很小。
由此，树的整体高度保持logn的顺序，并且在O（logn）时间内执行诸如search，插入和删除节点的操作。 C ++的STL也以集合和映射的forms实现这些树。
你的程序语法，或者就此而言，诸如自然语言之类的许多其他事物可以使用二叉树进行分析（尽pipe不一定）。
java.util.Set实现
在现代硬件上，由于caching和空间行为不良，二叉树几乎总是次优的。 这也适用于（半）平衡变体。 如果你发现它们，就是性能不算的地方（或者被比较函数所支配），或者更可能出于历史或无知的原因。
一个使用二叉树表示AST的编译器，可以使用已知的algorithm来parsing后序树，inorder。程序员不需要拿出它自己的algorithm。 由于源文件的二叉树高于n-ary树，因此构build需要更多的时间。 采取这样的产品：selstmnt：=“if”“（”expr“）”stmnt“ELSE”stmnt在一棵二叉树中将有3层节点，但是n元树将有1层（chids）
这就是为什么基于Unix的操作系统很慢的原因。
