二叉树的应用是什么？

#1 楼

争论二叉树的性能毫无意义-它们不是数据结构，而是一系列具有不同性能特征的数据结构。尽管不平衡的二叉树的确比自平衡的二叉树搜索性能差很多，但是有许多二叉树（例如二叉尝试）对它们而言“平衡”没有任何意义。

的应用二进制树



二进制搜索树-在许多不断输入/离开数据的搜索应用中使用，例如许多语言库中的map和set对象。

二进制空间分区-几乎在每个3D视频游戏中用于确定需要渲染的对象。

二进制尝试-在几乎每个高带宽路由器中用于存储路由器表。

哈希树-在p2p程序和专用图像签名中使用，其中需要验证哈希，但是整个文件不可用。

堆-用于实现高效的优先级队列，这些优先级队列又可用于调度许多操作系统中的进程，路由器中的服务质量以及A *（路径查找AI应用程序（包括机器人和视频游戏）中使用的算法）。

霍夫曼编码树（Chip Uni）-用于压缩算法，例如.jpeg和.mp3文件格式所使用的算法。

GGM树-用于加密应用程序中以生成伪随机数树。

语法树-由编译器和（隐式）计算器构造以解析表达式。

处理-用于无线网络和内存分配的随机数据结构。

T-树-尽管大多数数据库使用某种形式的B-树将数据存储在驱动器上，但保留所有（大部分）数据的数据库内存中经常使用T树来做到这一点。


二元树比n元树更常用于搜索的原因是n元树更复杂，但通常没有实际的速度优势。

在（平衡）二叉树中从一个级别转移到下一个级别的m节点需要一个比较，并且存在log_2(m)个级别，总共需要log_2(m)比较。

相反，一元树将需要log_2(n)比较（使用a二进制搜索）以进入下一个级别。由于总共有log_n(m)个水平，因此搜索将需要总共log_2(n)*log_n(m) = log_2(m)个比较。因此，尽管n元树比较复杂，但是它们在进行必要的总比较方面没有任何优势。

（然而，n元树在小生境中仍然很有用。这些例子马上出现要记住的是四叉树和其他空间划分树，其中在每个级别仅使用两个节点来划分空间将使逻辑不必要地复杂；以及在许多数据库中使用的B树，其中限制因素是不进行多少次比较每个级别，但一次可以从硬盘驱动器加载多少个节点）

#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可以通过直接查找X * record_length来找到）。
例如，如果指针大小为4个字节，密钥大小为10，则512字节节点中的密钥数为36。这是36个密钥（360字节）和37个指针（148字节），总共508个字节，每个节点浪费了4个字节。
多路键的使用引入了两阶段搜索的复杂性（多路搜索以找到正确的节点，再加上小的顺序（或线性二进制）搜索以在节点中找到正确的键）但是减少磁盘I / O的优势却不足以弥补这一点。
我认为没有必要针对内存结构进行此操作，最好还是坚持平衡的二叉树并保持您的代码简单。
还请记住，当数据集较小时，O(log N)比O(N)的优势并没有真正显现出来。如果您使用多向树将15个人存储在通讯录中，则可能是过大的了。当您存储过去十年来来自十万个客户的每个订单之类的东西时，优势就来了。
big-O表示法的全部要点是表明N接近无穷大时会发生什么。某些人可能会不同意，但是如果您确定数据集将保持在一定大小以下，并且只要没有其他可用数据，就可以使用冒泡排序，也可以:-)

关于其他用途对于二叉树，有很多，例如：

二叉堆，其中高键位于或等于低键，而不位于（或低于或等于右）键的左侧；
哈希树，类似于哈希表；
用于计算机语言编译的抽象语法树；
用于数据压缩的霍夫曼树；
用于网络流量的路由树。

鉴于我为搜索树生成了多少解释，我不愿透露其他详细信息，但只要您愿意，就足以对它们进行研究。

#3 楼

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

#4 楼

二叉树是一种树数据结构，其中每个节点最多具有两个子节点，通常被区分为“左”和“右”。具有子节点的节点是父节点，子节点可能包含对其父节点的引用。在树外，通常存在对“根”节点（所有节点的祖先）的引用（如果存在）。数据结构中的任何节点都可以通过从根节点开始并反复遵循对左或右子节点的引用来访问。在二叉树中，每个节点的度数最多为两个。



二叉树非常有用，因为如您在图片中所见，如果要查找任何一个在树中的节点上，您最多只需要查看6次。例如，如果要搜索节点24，则应从根节点开始。


根的值为31，该值大于24，因此您将转到左侧节点。
左侧节点的值为15，小于24，因此您转到右侧节点。
右节点的值为23，小于24，因此您将转到右节点。
右节点的值为27，该值大于24，因此您转到左节点。
左节点的值为25，该值大于24，因此您将转到左节点。
该节点的值为24，这是我们正在寻找的关键。

该搜索结果如下图所示：


您可以看到，您可以在第一遍排除整个树的一半节点。左子树的一半在第二个。这使得搜索非常有效。如果对40亿个元素执行此操作，则最多只需搜索32次。因此，树中包含的元素越多，搜索的效率就越高。

删除会变得很复杂。如果节点有0或1个子节点，则只需移动一些指针以排除要删除的节点即可。但是，您无法轻松删除具有2个子节点的节点。因此，我们采取捷径。假设我们要删除节点19。



由于要确定将左指针和右指针移至何处并不容易，我们找到了一个替换它的地方。 。我们转到左侧的子树，然后尽可能向右走。这为我们提供了要删除的节点的下一个最大值。



现在我们复制18的所有内容（左指针和右指针除外）并删除原始的18个节点。




为了创建这些图像，我实现了AVL树，即自平衡树，以便在任何时间点，树在叶节点（无子节点）之间最多有一个差异级别。这可以防止树倾斜，并保持最大搜索时间，但要花费更多的时间进行插入和删除。

下面的示例显示了我的AVL树如何保持自身的状态



在排序数组中，查找仍然像树一样占用O(log n)，但是随机插入和删除将占用O（n）而不是树的O(log(n))。一些STL容器充分利用了这些性能特征，因此插入和移除时间最多需要O(log(n))，这非常快。其中一些容器是O(log n)，map，multimap和set。

有关AVL树的示例代码可在http://ideone.com/MheW8
上找到。

#5 楼

主要应用是二进制搜索树。这些是数据结构，其中搜索，插入和删除都非常快（关于log(n)操作）

#6 楼

二叉树用于霍夫曼编码中，用作压缩代码。
二叉树用于二进制搜索树中，可用于维护数据记录而无需太多空间。

#7 楼

尚未提及的二叉树的一个有趣示例是递归评估的数学表达式。从实际的角度来看，这基本上是没有用的，但是考虑这种表达式是一种有趣的方法。

基本上，树的每个节点都有一个自身固有的值或通过操作递归地评估例如，表达式(1+3)*2可以表示为：

    *
   / \
  +   2
 / \
1   3

要求该表达式，我们要求为父母的价值。该节点依次从其子级，加号运算符和仅包含“ 2”的节点获取其值。加号运算符反过来从值为'1'和'3'的子级中获取其值，并将它们相加，将4返回到乘法节点，该乘法节点返回8。

使用二叉树类似于在某种意义上，反向抛光表示法是指执行操作的顺序相同。还有一点要注意的是，它不一定必须是二进制树，而只是最常用的运算符是二进制。从最基本的角度来看，这里的二叉树实际上只是一种非常简单的纯函数式编程语言。

#8 楼

二叉树的应用：




在路由器中实现路由表。
数据压缩代码
表达式解析器和表达式求解器的实现

解决诸如索引之类的数据库问题。

表达评估

#9 楼

我认为“纯”二叉树没有任何用处。 （出于教育目的除外）
平衡二叉树（例如红黑树或AVL树）更加有用，因为它们可以保证O（logn）操作。普通的二叉树最终可能只是一个列表（或几乎是列表），在使用大量数据的应用程序中并不是真正有用。

平衡树通常用于实现映射或集合。
它们可以还可以用于O（nlogn）的排序，即使有更好的方法也可以。

还可以用于搜索/插入/删除哈希表，该哈希表通常比二进制搜索具有更好的性能。树（是否平衡）。

如果需要搜索/插入/删除和排序，则使用（平衡）二进制搜索树的应用程序。给定就绪的构建平衡树，排序可以就地进行（几乎忽略了递归所需的堆栈空间）。它仍然是O（nlogn），但常数因子较小，并且不需要额外的空间（新数组除外，假设必须将数据放入数组中）。另一方面，哈希表无法排序（至少不能直接排序）。

也许哈希表在某些复​​杂的算法中也很有用，但是我却一无所获。如果我发现更多信息，将编辑我的帖子。

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

#10 楼

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

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

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

通常，二叉树是基于特定树的数据结构的一般概念，并且可以构造具有不同属性的各种特定类型的二叉树。 />

#11 楼

在C ++ STL和许多其他语言的标准库中，例如Java和C＃。二叉搜索树用于实现集合和映射。

#12 楼

二进制树最重要的应用之一是平衡的二进制搜索树，例如：


红黑树
AVL树
替罪羊树

这类树的性质是，每次插入或删除节点时，通过进行旋转等操作，可以使左子树和右子树的高度差保持较小。

树的整体高度保持为log n的顺序，并且节点的搜索，插入和删除等操作均在O（log n）时间内执行。 C ++的STL还以集合和映射的形式实现这些树。

#13 楼

它们可以用作对数据进行排序的快速方法。将数据插入到O（log（n））的二叉搜索树中。然后遍历树以对其进行排序。

#14 楼

在现代硬件上，由于不良的缓存和空间行为，二叉树几乎总是次优的。 （半）平衡变体也是如此。如果您发现它们，那就是性能不重要（或由比较功能控制）的地方，或者是出于历史或无知的原因更可能的地方。

#15 楼

您的程序语法，或者其他很多事情，例如自然语言，都可以使用二叉树来解析（尽管不是必须的）。

#16 楼

java.util.Set的实现

#17 楼

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

#18 楼

几乎所有数据库（和类似数据库的程序）都使用二叉树来实现其索引系统。

#19 楼

使用二叉树表示AST的编译器可以使用已知算法来像后顺序一样解析树。程序员无需提出自己的算法。
因为源文件的二进制树比n元树高，它的构建需要更多时间。
进行以下生产：
selstmnt：=“ if”“（” expr“）” stmnt“ ELSE” stmnt
在二叉树中将具有3个级别的节点，但是n叉树将具有1个级别的节点。

这就是为什么基于Unix的OS-s较慢的原因。