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


当前回答

它们可以作为一种快速排序数据的方法。在O(log(n))处将数据插入二叉搜索树。然后遍历树,对它们进行排序。

其他回答

我认为“纯”二叉树没有任何用处。(教育用途除外) 平衡二叉树,如红黑树或AVL树更有用,因为它们保证O(logn)运算。普通的二叉树最终可能是一个列表(或几乎是列表),在使用大量数据的应用程序中并没有真正的用处。

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

也可以用于搜索/插入/删除哈希表,它通常比二叉搜索树(平衡与否)有更好的性能。

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

也许它们在一些复杂的算法中也很有用,但说实话,我什么也想不起来。如果我发现更多,我会编辑我的帖子。

其他树如f.e.b +树也广泛应用于数据库中

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

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

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

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

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

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


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

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

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

java.util.Set的实现