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

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

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

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

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

---

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

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

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

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

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

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

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

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

使用二叉树表示AST的编译器可以使用已知的算法 解析树像海报，有序。程序员不需要提出自己的算法。 因为源文件的二叉树比n元树高，所以构建它需要更多的时间。 以这个生产为例: selstmnt:= "if" "(" expr ")" stmnt "ELSE" stmnt 在二叉树中，它将有3层节点，但n-ary树将有1层(子节点)

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

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

二叉树的应用

Binary Search Tree - Used in many search applications where data is constantly entering/leaving, such as the map and set objects in many languages' libraries. Binary Space Partition - Used in almost every 3D video game to determine what objects need to be rendered. Binary Tries - Used in almost every high-bandwidth router for storing router-tables. Hash Trees - Used in torrents and specialized image-signatures in which a hash needs to be verified, but the whole file is not available. Also used in blockchains for eg. Bitcoin. Heaps - Used in implementing efficient priority-queues, which in turn are used for scheduling processes in many operating systems, Quality-of-Service in routers, and A* (path-finding algorithm used in AI applications, including robotics and video games). Also used in heap-sort. Huffman Coding Tree (Chip Uni) - Used in compression algorithms, such as those used by the .jpeg and .mp3 file-formats. GGM Trees - Used in cryptographic applications to generate a tree of pseudo-random numbers. Syntax Tree - Constructed by compilers and (implicitly) calculators to parse expressions. Treap - Randomized data structure used in wireless networking and memory allocation. T-tree - Though most databases use some form of B-tree to store data on the drive, databases which keep all (most) their data in memory often use T-trees to do so.

---

二叉树比n-ary树更常用于搜索的原因是n-ary树更复杂，但通常不会提供真正的速度优势。

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