二叉树有哪些应用？

Question

我想知道二叉树的具体应用是什么。你能举几个实际的例子吗？

- Jichao

Answer 1

争论二叉树的性能是毫无意义的 - 它们不是一种数据结构，而是一类数据结构，具有不同的性能特点。虽然不平衡的二叉树在搜索方面表现比自平衡的二叉树差得多，但有许多二叉树（例如二进制试图），对于它们来说，"平衡"没有意义。

二叉树的应用

• 二叉搜索树 - 在许多搜索应用程序中使用，其中数据不断进出，例如许多语言库中的map和set对象。
• 二叉空间分割 - 在几乎所有3D视频游戏中使用，以确定需要渲染哪些对象。
• 二进制数字查找树 - 在几乎所有高带宽路由器中用于存储路由表。
• 哈希树 - 在种子和专业图像签名中使用，其中需要验证哈希值，但整个文件不可用。也用于区块链，例如比特币。
• 堆 - 用于实现有效的优先队列，在许多操作系统中用于进程调度，路由器中的服务质量以及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叉树仍然很有用。我想到的例子是quad-trees和其他空间划分树，在这些情况下，只使用每个层级的两个节点来划分空间会使逻辑变得不必要地复杂；还有许多数据库中使用的B-trees，在这些情况下，限制因素不是在每个层级上执行多少次比较，而是可以一次从硬盘加载多少个节点）。

- BlueRaja - Danny Pflughoeft

---

Treap是一种随机化数据结构，被用于无线网络和内存分配中。它们在内存分配中的具体使用方式以及在无线网络中的应用可以如何实现并不清楚，需要更多的上下文信息。 - frp

有很多有用的数据结构和算法使用了“二进制”这个词，而“二叉搜索树”实际上就是其中之一，但这不是被问到的问题。一个普通的“二叉树”，不是排序的、不是平衡的、也不是满的，它有什么用处呢？ - Michael Erickson

你好，@MichaelErickson，你有没有读这个答案？因为我回答的正是你问的问题。 - BlueRaja - Danny Pflughoeft

@nbro：这个回答没有提到哈希表，你似乎误读了什么。 - BlueRaja - Danny Pflughoeft

我相信哈希树在比特币、以太坊社区、IPFS等地方通常被称为默克尔树。 - Duke

Answer 2

当大多数人谈论二叉树时，他们往往想到的是二叉 搜索 树，因此我将首先介绍它。

非平衡的二叉搜索树实际上只有在为学生讲授数据结构时才有用。这是因为，除非数据以相对随机的顺序进入，否则树很容易变成其最坏情况，即链表，因为简单的二叉树不是平衡的。

举个例子：我曾经需要修复一些软件，它把数据加载到二叉树中进行操作和搜索。它按排序形式将数据写出：

Alice
Bob
Chloe
David
Edwina
Frank

因此，当读回它时，最终得到以下树形结构：

  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），即可找到Frank。

当然，当您将它们变成平衡的多路树而不是二叉树时，它们可以变得更加有用。这意味着每个节点保存多个项目（技术上，它们保存N个项目和N+1个指针，二叉树是一种特殊情况的1路多路树，具有1个项目和2个指针）。

通过使用三路树，您最终会得到：

  Alice Bob Chloe
 /     |   |     \
=      =   =      David Edwina Frank
                 /     |      |     \
                =      =      =      =

这通常用于维护项目索引的键。我编写了针对硬件进行优化的数据库软件，其中节点恰好是磁盘块大小（例如，512字节），并且将尽可能多的键放入单个节点中。在这种情况下，指针实际上是记录号，而该记录号是与索引文件分开的固定长度记录直接存取文件中的位置（因此可以通过只查找到X * record_length来找到记录号X）。

例如，如果指针为4字节，键大小为10，则512字节节点中的键数为36。这是36个键（360字节）和37个指针（148字节），总共508字节，每个节点浪费4个字节。

多路键的使用引入了两阶段搜索的复杂性（多路搜索以找到正确的节点，再加上一个小的顺序（或线性二进制）搜索以找到节点中的正确键），但减少磁盘I / O的优势胜过这一点。

我认为没有理由为内存结构做这个操作，最好坚持使用平衡的二叉树，并保持代码简洁。

也要记住，对于数据集较小时，“O（log N）”比“O（N）”的优势并没有真正显现出来。如果您正在使用多路树存储地址簿中的十五个人，则可能过度设计。优势在于存储过去十年内来自您十万名客户的每个订单之类的内容时才会出现。

大O符号的整个意义在于表示随着“N”趋近于无穷大会发生什么。有些人可能不同意，但是即使数据集将保持在某个特定大小以下，使用冒泡排序也可以，只要没有其他可用的方法 :-)

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

- 二叉堆，其中较高的键位于低键的上方或相等，而不是在左侧（或下面或相等）和右侧； - 哈希树，类似于哈希表； - 抽象语法树用于编译计算机语言； - Huffman树用于数据压缩； - 路由树用于网络流量。

- paxdiablo

---

谢谢你写了这么好的答案，同时还向我介绍了平衡多路搜索树，这是我以前没有接触过的。 - Tony

我不同意你的说法，认为它们不仅仅对教育学生有用。它们非常有用，甚至作为一个简单的静态数据结构也很实用。不过，你的回答写得非常好，并且图文并茂，所以其他方面加一分。 :-) - Benson

在现代硬件上，几乎所有的树都应该是多路树。 - Stephan Eggermont

@Benson 我不同意你的观点。需要注意的是他谈论的是不平衡的二叉搜索树。相较于普通数组，这有什么优势呢？ - Adam Burley

Answer 3

摩尔斯电码的组织结构是一棵二叉树。

- IliasT

---

这是我最喜欢的答案。它直接说明了在到达列表更远处的字符所需的计算复杂度的降低。 - Moustache

Answer 4

二叉树是一种树形数据结构，每个节点最多只有两个子节点，通常称为“左”和“右”。有子节点的节点是父节点，子节点可能包含对其父节点的引用。在树之外，如果存在，通常会有一个对“根”节点（所有节点的祖先）的引用。可以通过从根节点开始重复跟随左或右子节点的引用来访问数据结构中的任何节点。在二叉树中，每个节点的度数最大为两。

二叉树非常有用，因为如图片所示，如果要查找树中的任何节点，您只需要最多查找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上找到。

- Drise

---

如果您正在处理一棵二叉搜索树（本身是平衡的），那么您只需搜索O（log n）即可。任意的二叉树没有排序约束，而随机的二叉搜索树具有搜索复杂度O（log h）。 - dlev

这些不是存储在相关标准容器中的类型。 - Puppy

但是这在编程中如何表示呢？使用一个包含左值和右值的对象数组。 - undefined

通常情况下，我们在引用中使用引用。在基本的学术环境中，你实际上不需要任何存储介质来保存对象。每个树节点对象都会引用其左右子节点，它们本身也是另一个树节点对象。通常情况下，我们会将这些成员变量定义为T& left, right，其中T表示节点类型。 - undefined

@Drise但是这些对象会存储在文件还是数据库中呢？我对二叉树还不太熟悉，只是想弄清楚整个系统是如何工作的。我理解二叉树的性能优势，并且知道如何遍历它。但是树应该存储在哪里呢？还有，如何创建它呢？ - undefined

@Wayne 你的树只是元素本身，通过各种“左右”指针连接在一起。你并不是在任何地方“存储”它们（除了内存之外）。当你创建一个新节点时，你使用一个现有节点来存储指向新节点的指针。现在它是树的一部分了。只要你不“删除”节点，你的树就会保持完整。不需要容器/文件/数据库。 - undefined

Answer 5

一个有趣的未被提及的二叉树示例是递归计算数学表达式。从实用角度来看，它基本上是无用的，但它是一种有趣的思考这类表达式的方式。

基本上，树的每个节点都有一个值，该值要么固有自身，要么通过对其子节点的值进行递归计算得出。

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

    *
   / \
  +   2
 / \
1   3

为了求出这个表达式的值，我们要求父节点的值。这个父节点又从它的孩子节点中获得值，其中一个是加号操作符，另一个节点仅包含数字'2'。加号操作符又从它的两个子节点（值为'1'和'3'）获取值并将它们相加，返回4给乘法节点，最终返回8。

这种使用二叉树的方法类似于逆波兰表达式，因为操作顺序相同。还要注意的一点是，并不一定非要使用二叉树，只是大多数常用操作符是二元的。在最基本的层次上，这里的二叉树实际上只是一种非常简单的纯函数编程语言。

- Clueless

Answer 6

主要应用是二叉搜索树。它是一种数据结构，其中搜索、插入和删除都非常快（大约需要log(n)次操作）。

- BlueRaja - Danny Pflughoeft

---

二叉搜索树不是一个应用程序，而是一种特定类型的二叉树。 - nbro

@nbro：你在争论毫无意义的语义学问题，这两种说法都是有效的。请注意，“应用程序”在这里并不意味着“计算机应用程序”。 - BlueRaja - Danny Pflughoeft

我认为问题更多地涉及实际应用而不是特定实现或特定类型的二叉树。顺便说一句，提问者并没有询问哪些数据结构是特定的二叉树。在我看来，这并不是毫无意义的。但我同意它仍然存在歧义。例如，在你的另一个答案中，你提到了语法树，这是一个将树（但不一定是二叉树）数据结构应用于实际应用程序的例子。基于你的推理，那么我可以列举我所知道的所有二叉树，我们都会因为项目数量而感到高兴。 - nbro

Answer 7

我认为“纯”的二叉树（除了教育目的）没有实际用途。相比之下，平衡二叉树，如红黑树或AVL树更加有用，因为它们保证O(logn)操作。普通的二叉树可能会变成列表（或几乎成为列表），在处理大量数据的应用场景中并不是真正有用的。

平衡树通常用于实现映射表或集合。它们还可以用于O(nlogn)排序，尽管存在更好的方法来完成排序。

此外，在搜索/插入/删除方面，可以使用哈希表，其通常比二叉搜索树（平衡或非平衡）具有更好的性能。

如果需要搜索/插入/删除和排序，则(平衡)二叉搜索树在某些应用场景下很有用。排序可以就地进行（几乎忽略递归所需的堆栈空间），只要提供一个已构建好的平衡树即可。虽然时间复杂度仍为O(nlogn)，但常数因子更小，不需要额外空间（除了新数组，假设数据必须放入数组中）。另一方面，哈希表不能直接进行排序。

也许它们在某些复杂算法中也很有用，但是说实话，我想不到什么。如果我想到更多的应用场景，我会编辑我的文章。

其他树，如B+树在数据库中被广泛使用。

- George

Answer 8

二叉树的应用：

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

- S.VenkatachalamMCA

Answer 9

• 二叉树用于哈夫曼编码，这是一种压缩代码的方法。
• 二叉树用于二叉搜索树，它们有助于在没有过多额外空间的情况下维护数据记录。

- Chip Uni

Answer 10

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

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

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

通常，二叉树是特定基于树的数据结构的概括性概念，不同属性的各种具体类型的二叉树可以被构建出来。

- mloskot