二叉树的应用是什么?

为…的表现争论 二叉树 毫无意义——它们不是数据结构,而是一系列具有不同性能特征的数据结构。虽然这是真的 不平衡二叉树 表现比 自平衡二叉树 为了搜索,有许多二叉树 (例如二进制尝试) 为此 “平衡” 没有意义。

二叉树的应用

• Binary Search Tree -用于 许多的 搜索数据不断进入/离开的应用程序,例如 map 和 set 许多语言库中的对象。
• Binary Space Partition -几乎在每一个3D视频游戏中使用,以确定需要渲染哪些对象。
• Binary Tries -在几乎所有的高带宽路由器中用于存储路由器表。
• Hash Trees -用于p2p程序和特殊的图像签名,其中需要验证哈希值,但整个文件不可用。
• Heaps -用于实现高效的优先级队列,这些队列依次用于调度许多操作系统中的进程、路由器中的服务质量以及* (人工智能应用中使用的寻径算法,包括机器人和视频游戏) .也用于堆排序。
• Huffman Coding Tree ( Chip Uni )-用于压缩算法,如.jpeg和.mp3文件格式所使用的算法。
• GGM Trees -在密码应用程序中用于生成伪随机数树。
• Syntax Tree -由编译器和(隐式)计算器构造以分析表达式。
• Treap -无线网络和内存分配中使用的随机数据结构。
• T-tree -尽管大多数数据库使用某种形式的B-树来存储驱动器上的数据,但将所有(大部分)数据保存在内存中的数据库通常使用T-树来存储数据。

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

在(平衡的)二叉树中, m 节点,从一个级别移动到下一个级别需要一个比较,并且 log_2(m) 级别,总共为 Log2(m) 比较。

相反,一个n元树需要 log_2(n) 比较 (使用二进制搜索) 移动到下一个级别。既然有 log_n(m) 总级别,搜索将需要 log_2(n)*log_n(m) = Log2(m) 比较总计。因此,尽管n元树更复杂,但它们在必要的总比较方面没有优势。

(然而,N元树在生态位情况下仍然有用。立即想到的例子是 quad-trees 以及其他空间划分树,其中每个级别仅使用两个节点划分空间会使逻辑变得不必要的复杂;以及 B-trees 在许多数据库中使用,其中的限制因素不是在每个级别上进行多少比较,而是可以从硬盘驱动器一次加载多少节点)

当大多数人谈论二叉树的时候,他们经常会想到二叉树。 搜索 树,所以我先盖上。

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

有一个很好的例子:我曾经需要修复一些软件,它将数据加载到一个二进制树中,以便进行操作和搜索。它以排序的形式写出数据:

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 )退化形式给出的。在任何情况下,最高的空值都不为( = )与最低级别的差异不止一个级别。在上面的最后一个树中,您只需查看三个节点就可以找到Frank。( Chloe ,请 Edwina 最后, Frank )

当然,当你使它们平衡的时候,它们会变得更加有用。 多途径 树而不是二叉树。这意味着每个节点包含多个项(从技术上讲,它们包含n个项和n+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 接近无穷大。有些人可能不同意,但如果您确定数据集将保持在某个大小之下,只要没有其他可用的数据集,使用冒泡排序就可以了:-)

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

• 二进制堆,其中较高的键是 大于或等于 较低的,而不是左边(或低于或等于右边);
• 散列树,类似于散列表;
• 汇编计算机语言的抽象语法树;
• 用于数据压缩的哈夫曼树;
• 网络流量的路由树。

考虑到我为搜索树生成了多少解释,我对其他树的很多细节都保持沉默,但如果你愿意的话,这应该足以研究它们。

二叉树是一种树数据结构,其中每个节点最多有两个子节点,通常分为“左”和“右”。具有子节点的节点是父节点,子节点可以包含对其父节点的引用。在树的外部,如果存在“根”节点(所有节点的祖先),通常会有一个对它的引用。数据结构中的任何节点都可以通过从根节点开始并重复引用左或右子节点来访问。在二叉树中,每个节点的度数最多为2。

二叉树很有用,因为正如您在图片中看到的,如果您想在树中找到任何节点,您最多只需要查找6次。例如,如果您想搜索节点24,您可以从根目录开始。

• 根的值为31,大于24,所以您转到左节点。
• 左侧节点的值为15,小于24,因此您转到右侧节点。
• 右节点的值为23,小于24,因此您转到右节点。
• 右节点的值为27,大于24,因此转到左节点。
• 左侧节点的值为25,大于24,因此您转到左侧节点。
• 节点的值为24,这是我们要查找的键。

此搜索如下图所示:

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

删除可能会变得复杂。如果节点有0或1个子节点,那么只需移动一些指针来排除要删除的指针。但是,您不能轻松删除具有两个子节点的节点。所以我们抄近路。假设我们想删除节点19。

morse code morse code is a binary tree.

主要应用是 binary search trees . 这是一种数据结构,其中搜索、插入和删除都非常快(大约 log(n) 操作)

• 二叉树用于 Huffman coding ,用作压缩代码。
• 二叉树用于 Binary search trees ,这对于在没有太多额外空间的情况下维护数据记录很有用。

二叉树的一个有趣的例子是递归计算的数学表达式。从实际的角度来看,它基本上是无用的,但它是一种有趣的方式来思考这种表达。

基本上,树的每个节点都有一个自身固有的值,或者通过对其子节点的值进行操作以递归方式进行计算。

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

    *
   / \
  +   2
 / \
1   3

为了评估表达式,我们要求父级的值。该节点依次从其子节点、加号运算符和仅包含“2”的节点获取其值。然后,加号运算符从值为“1”和“3”的子级获取其值,并将它们相加,将4返回到返回8的乘法节点。

二叉树的这种用法在某种意义上类似于逆波兰表示法,因为执行操作的顺序是相同的。还有一点需要注意的是,它不一定是二叉树,只是最常用的运算符是二叉树。在最基本的层次上,这里的二叉树实际上只是一种非常简单的纯函数编程语言。

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

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

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

一般来说,二叉树是基于特定树的数据结构的一般概念,各种特定类型的二叉树可以用不同的属性构造。

二叉树的应用:

1. Implementing routing table in router .
2. Data compression code
3. Implementation of Expression parsers and expression solvers
4. To solve database problem such as indexing .
5. Expression evaluation

我认为“纯”二叉树没有任何用处。(除教育用途外) 平衡二叉树,如 Red-Black trees 或 AVL trees 更有用,因为它们保证了O(logn)操作。正常的二叉树可能最终成为一个列表(或几乎是列表),在使用大量数据的应用程序中并不真正有用。

平衡树通常用于实现映射或集合。 它们也可以用于O(nlogn)中的排序,即使存在更好的方法。

也用于搜索/插入/删除 Hash tables 可以使用,这通常比二进制搜索树(平衡与否)有更好的性能。

如果需要搜索/插入/删除和排序,那么(平衡的)二进制搜索树将非常有用。如果给定一个就绪的构建平衡树,排序可以就位(几乎忽略递归所需的堆栈空间)。它仍然是O(nlogn),但具有较小的常量因子,不需要额外的空间(除了新的数组,假设数据必须放入一个数组中)。另一方面,哈希表不能排序(至少不能直接排序)。

也许它们在一些复杂的算法中也很有用,但是我什么也没想到。如果我找到更多,我会编辑我的帖子。

其他树,如F.E. B+trees 在数据库中被广泛使用

在C++ STL中,还有许多其他语言的标准库,如Java和C语言。二叉树用于实现集合和映射。

二叉树最重要的应用之一是 平衡的 二进制搜索树如下:

• Red-Black trees
• AVL trees
• Scapegoat trees

这些类型的树具有这样的特性:左子树和右子树的高度差通过每次插入或删除节点时执行旋转之类的操作保持较小。

因此,树的总高度保持对数n的顺序,搜索、插入和删除节点等操作在o(对数n)时间内执行。C++的STL也以集合和映射的形式实现这些树。

它们可以用作快速排序数据的方法。将数据插入到O(日志(n))处的二进制搜索树中。然后遍历树以便对它们进行排序。

您的程序语法,或者其他许多东西,如自然语言,可以使用二进制树来解析(尽管不一定)。

的实现 java.util.Set

在现代硬件上,由于缓存和空间行为不好,二叉树几乎总是次优的。这也适用于(半)平衡变体。如果你找到了它们,那就是性能不重要(或者由比较函数控制),或者更可能是因为历史或无知的原因。

使用二进制树表示ast的编译器可以使用已知的算法 更糟糕的是,程序员不需要想出自己的算法。 因为源文件的二叉树比N叉树高,所以构建它需要更多的时间。 以这部作品为例: selstmnt:=“如果”“(”expr”)“stmnt”else“stmnt 在二叉树中,它将有3层节点,但n叉树将有1层(chids)

这就是基于Unix的OS-S速度慢的原因。