我最近读过几本书，都曾经看到过二进制树和二进制搜索，但是由于我仍在计算机科学学习的初期，所以我还没有上过真正涉及算法和数据的课程严重的结构。

我检查了典型的资源(维基百科，谷歌)，以及大多数关于(尤其是)红黑树的有用性和实现的描述，因为它们密集且难以理解。我敢肯定，对于具有必要背景的人来说，这是很有意义的，但是目前，它几乎像是外语。

那么，什么使二进制树在编程时发现自己要执行的一些常见任务中有用呢？除此之外，我们更喜欢使用哪些树(请提供示例实现)，为什么？

解决方案

回答

红黑树非常适合创建平衡的树。二进制搜索树的主要问题是，我们可以非常轻松地使它们变得不平衡。想象第一个数字是15. 然后所有的数字都越来越小于15. 我们将有一棵树，左侧非常沉重，而右侧没有任何东西。

红黑树通过在插入或者删除时强制树保持平衡来解决此问题。它通过在祖先节点和子节点之间进行一系列旋转来实现此目的。该算法实际上很简单，尽管它有点长。我建议拿起CLRS(Cormen，Lieserson，Rivest和Stein)教科书，"算法简介"，并阅读RB树。

该实现也不是那么短，所以可能最好不要在此处包含它。但是，树被广泛用于需要访问大量数据的高性能应用程序。它们提供了一种查找节点的非常有效的方式，而插入/删除的开销却相对较小。再次，我建议我们查看CLRS，以了解其用法。

虽然可能不会明确使用BST，但是几乎在每个现代RDBMS中，通常都会使用树的一个示例。同样，文件系统几乎可以肯定地表示为某种树结构，并且文件也以这种方式进行索引。树木为Google提供动力。树木几乎为互联网上的每个网站提供动力。

回答

红黑树和B树用于各种持久性存储。因为树木是平衡的，所以宽度和深度遍历的性能得到了缓解。

几乎所有现代数据库系统都使用树来存储数据。

回答

正如Micheal所说，BST使世界运转。如果我们正在寻找一个好的树来实现，请看一下AVL树(维基百科)。它们具有平衡条件，因此可以保证为O(logn)。这种搜索效率使将逻辑放入任何类型的索引过程变得合乎逻辑。唯一会更有效的是哈希函数，但是这些函数变得又快又快，而且很麻烦。此外，我们还会遇到"生日悖论"(也称为"鸽洞问题")。

我们正在使用什么教科书？我们使用了Mark Allen Weiss编写的Java中的数据结构和分析。当我输入此内容时，我实际上已将其打开。它有一个关于红黑树的重要部分，甚至包括实现所讨论的所有树所必需的代码。

回答

我只想回答一个问题："那么，什么使二进制树在我们在编程时发现自己要执行的一些常见任务中有用？"

这是许多人不同意的大话题。有人说，CS学位中讲授的算法(例如二进制搜索树和有向图)没有在日常编程中使用，因此是无关紧要的。其他人则不同意，他们说这些算法和数据结构是我们所有编程的基础，即使我们不必自己编写一个，也必须理解它们。这会过滤掉有关良好面试和雇用实践的对话。例如，史蒂夫·耶格(Steve Yegge)撰写了一篇有关在Google上进行采访的文章，旨在解决这个问题。记住这场辩论；有经验的人不同意。

在典型的业务编程中，我们可能根本不需要创建二进制树，甚至根本不需要创建树。但是，我们将使用许多内部使用树进行操作的类。每种语言的许多核心组织类都使用树和哈希来存储和访问数据。

如果我们从事更多的高性能工作，或者超出业务编程规范的情况，我们会发现树是直接的朋友。正如另一位发布者所说，树是各种数据库和索引的核心数据结构。它们在数据挖掘和可视化，高级图形(2d和3d)以及许多其他计算问题中很有用。

我在3D图形中以BSP(二进制空间分区)树的形式使用了二进制树。我目前正在再次查看树，以对大量经过地理编码的数据和其他数据进行排序，以在Flash / Flex应用程序中进行信息可视化。每当我们突破硬件界限或者想在较低的硬件规格上运行时，了解和选择最佳算法都会使失败与成功有所不同。

回答

我见过的关于红黑树的最好描述是Cormen，Leisersen和Rivest的"算法简介"中的描述。我什至可以理解它，足以部分实现一个(仅插入)。在各个网页上也有很多applet(例如"一个")可以动画化该过程，并允许我们观看并逐步完成构建树结构的算法的图形表示。

回答

如果我们想了解一棵红黑树的图形显示方式，我已对红黑树的实现进行了编码，我们可以在此处下载

回答

IME，几乎没有人了解RB树算法。人们可以将规则重复给我们，但他们不明白这些规则的原因以及其来源。我也不例外:-)

因此，我更喜欢AVL算法，因为它很容易理解。一旦了解了它，就可以从头开始编写代码，因为它对我们有意义。

回答

没有答案提到BST到底有什么用。

如果我们只想按值查找，则哈希表要快得多，可以使用O(1)插入和查找(分摊的最佳情况)。

BST将是O(log N)查找，其中N是树中的节点数，插入也是O(log N)。

RB和AVL树非常重要，就像提到的另一个答案一样，因为该属性，如果使用顺序值创建普通的BST，则树的数量将与插入的值的数量一样多，这对查找性能不利。

RB和AVL树之间的差异在于插入或者删除后重新平衡所需的旋转次数，AVL树为O(log N)进行重新平衡，而RB树为O(1)。这种恒定复杂性的好处的一个例子是，如果我们保持一个持久的数据源，那么如果我们需要跟踪更改以回滚，则必须使用AVL树跟踪O(log N)可能的更改。

我们为什么愿意为哈希表上的一棵树付出代价？命令！哈希表没有顺序，另一方面，BST总是凭借其结构自然而有序。因此，如果我们发现自己将大量数据扔到数组或者其他容器中，然后再对其进行排序，则BST可能是更好的解决方案。

树的order属性为我们提供了许多有序的迭代功能，有序，深度优先，广度优先，前置，后置。如果要查找它们，这些迭代算法在不同的情况下很有用。

红黑树几乎在语言库，C ++ Set和Map，.NET SortedDictionary，Java TreeSet等的每个有序容器中内部使用。

因此，树木非常有用，我们甚至可能在不知道的情况下经常使用它们。尽管我强烈建议我们将它作为一个有趣的编程练习，但是我们很可能永远不需要自己写一个。

回答

树木可以很快。如果在平衡的二叉树中有一百万个节点，则平均需要二十次比较才能找到任何一项。如果链接列表中有一百万个节点，则平均需要五十万次比较才能找到相同的项目。

但是，如果树不平衡，则其速度可能与列表一样慢，并且还会占用更多的内存来存储。想象一棵树，其中大多数节点都有一个右子节点，但没有左子节点；它是一个列表，但是如果显示一个节点，我们仍然必须保留内存空间才能放入左节点。

无论如何，AVL树是第一个平衡二叉树算法，有关它的Wikipedia文章很清楚。老实说，维基百科上有关红黑树的文章很清楚。

除了二叉树，B树是每个节点可以具有许多值的树。 B树不是二叉树，只是它的名字。它们对于有效利用内存确实很有用。可以调整树的每个节点的大小以适合一个内存块，以便我们不会(缓慢地)在内存中找到分页到磁盘的大量不同内容。这是B树的一个惊人例子。