我在最近读过的几本书中看到了二叉树和二叉搜索，但由于我仍处于计算机科学学习的初期，我还没有上过真正涉及算法和数据的课程结构严重。
我已经检查了典型的来源（维基百科、谷歌），并且大多数关于（特别是）红黑树的有用性和实现的描述都变得密集且难以理解。我敢肯定，对于有必要背景的人来说，这很有意义，但目前它读起来几乎就像一门外语。
那么，是什么让二叉树在您发现自己在编程时执行的一些常见任务中有用呢？除此之外，您更喜欢使用哪些树（请提供示例实现）以及为什么？
wfarr
问问题
14569 次
12 回答
54
红黑树有利于创建平衡良好的树木。二叉搜索树的主要问题是您可以很容易地使它们不平衡。想象你的第一个数字是 15。然后之后的所有数字都越来越小于 15。你会有一棵树，左边很重，右边什么都没有。
红黑树通过在插入或删除时强制树平衡来解决这个问题。它通过祖先节点和子节点之间的一系列旋转来实现这一点。该算法实际上非常简单，尽管它有点长。我建议拿起 CLRS（Cormen、Lieserson、Rivest 和 Stein）教科书“算法简介”并阅读 RB 树。
实现也不是那么短，所以在这里包含它可能不是最好的。尽管如此，树被广泛用于需要访问大量数据的高性能应用程序。它们提供了一种非常有效的查找节点的方法，插入/删除的开销相对较小。同样，我建议查看 CLRS 以了解它们的使用方式。
虽然 BST 可能没有被明确使用 - 通常使用树的一个例子几乎在每一个现代 RDBMS 中。同样，您的文件系统几乎可以肯定地表示为某种树结构，并且文件也以这种方式被索引。树木为 Google 提供动力。树木几乎为互联网上的每个网站提供动力。
于 2008-08-21T18:56:16.917 回答
17
我只想解决一个问题“那么，是什么让二叉树在您发现自己在编程时所做的一些常见任务中有用？”
这是一个很多人不同意的大话题。有人说，在 CS 学位中教授的算法，例如二叉搜索树和有向图，并没有用于日常编程，因此是无关紧要的。其他人不同意，他们说这些算法和数据结构是我们所有编程的基础，理解它们是必不可少的，即使你永远不必为自己编写一个。这会过滤到有关良好面试和招聘实践的对话中。例如，Steve Yegge有一篇关于Google 面试的文章解决了这个问题。记住这场辩论；有经验的人不同意。
在典型的业务编程中，您可能根本不需要经常创建二叉树甚至树。但是，您将使用许多在内部使用树进行操作的类。每种语言中的许多核心组织类都使用树和散列来存储和访问数据。
如果您参与了更高性能的工作或有些超出业务编程规范的情况，您会发现树是直接的朋友。正如另一位海报所说，树是各种数据库和索引的核心数据结构。它们在数据挖掘和可视化、高级图形（2d 和 3d）以及许多其他计算问题中很有用。
我在 3d 图形中使用了BSP（二进制空间分区）树形式的二叉树。我目前正在再次查看树，以对大量地理编码数据和其他数据进行排序，以便在 Flash/Flex 应用程序中进行信息可视化。每当您突破硬件界限或希望在较低的硬件规格上运行时，了解和选择最佳算法可以决定成败。
于 2008-08-21T19:27:33.067 回答
11
没有一个答案提到 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 属性为您提供了许多有序的迭代功能，in-order、depth-first、breadth-first、pre-order、post-order。如果您想查找它们，这些迭代算法在不同的情况下很有用。
几乎每个有序的语言库容器、C++ Set 和 Map、.NET SortedDictionary、Java TreeSet 等都在内部使用了红黑树。
所以树非常有用，你可能会经常使用它们，甚至不知道它。你很可能永远不需要自己写一个，尽管我强烈推荐它作为一个有趣的编程练习。
于 2009-12-02T06:46:23.133 回答
4
红黑树和 B 树用于各种持久存储；因为树是平衡的，所以降低了广度和深度遍历的性能。
几乎所有现代数据库系统都使用树来存储数据。
于 2008-08-21T19:09:12.363 回答
2
正如 Micheal 所说，BST 让世界运转起来。如果您正在寻找一个好的树来实现，请查看AVL 树（维基百科）。它们有一个平衡条件，所以它们保证为 O(logn)。这种搜索效率使得放入任何类型的索引过程都是合乎逻辑的。唯一更有效的方法是散列函数，但那些变得丑陋的快、快、匆忙。此外，您还会遇到生日悖论（也称为鸽子洞问题）。
你用的是什么教材？我们使用了 Mark Allen Weiss的 Java 数据结构和分析。在我打字的时候，我实际上把它放在我的腿上。它有一个关于红黑树的精彩部分，甚至包括实现它所讨论的所有树所需的代码。
于 2008-08-21T19:12:56.270 回答
2
我见过的对红黑树的最佳描述是 Cormen、Leisersen 和 Rivest 的“算法简介”中的那棵。我什至可以理解它以部分实现一个（仅插入）。在各种网页上也有很多小程序，例如This One ，它们可以动画处理过程，并允许您观看和逐步通过构建树结构的算法的图形表示。
于 2008-09-18T16:40:06.247 回答
2
红黑树保持平衡，因此您无需深入遍历即可取出物品。节省的时间使 RB 树在最坏情况下为 O(log()n))，而不幸的二叉树可能会进入不平衡的配置并导致 O(n) 中的检索成为坏情况。这确实发生在实践中或随机数据上。因此，如果您需要时间关键代码（数据库检索、网络服务器等），您可以使用 RB 树来支持有序或无序列表/集。
但是 RBTrees 是为新手准备的！如果你在做人工智能并且你需要执行搜索，你会发现你分叉了很多状态信息。您可以使用持久的红黑在 O(log(n)) 中分叉新状态。持久的红黑树在形态学操作（插入/删除）之前和之后保留树的副本，但不复制整个树（通常和 O(log(n)) 操作）。我已经为 java 开源了一个持久的红黑树
于 2011-07-25T20:17:11.000 回答
1
既然你问人们使用哪棵树，你需要知道红黑树本质上是一个 2-3-4 B-树（即 4 阶 B-树）。B树不等同于二叉树（如您的问题中所问）。
这是一个很好的资源，描述了被称为对称二叉 B 树的初始抽象，后来演变成 RBTree。在它有意义之前，您需要很好地掌握 B 树。总结一下：红黑树上的“红色”链接是表示作为 B 树节点一部分的节点（键范围内的值）的一种方式，而“黑色”链接是在 B 中垂直连接的节点-树。
因此，当您将红黑树的规则转换为 B 树时，您会得到以下结果（我使用的格式为红黑树规则=> B 树等效）：
1) 一个节点不是红色就是黑色。=> b-tree 中的节点可以是节点的一部分，也可以作为新级别中的节点。
2）根是黑色的。（这条规则有时会被省略，因为它不影响分析） => 根节点可以被认为是内部根节点的一部分，也可以被认为是虚构父节点的子节点。
3) 所有叶子 (NIL) 都是黑色的。（所有叶子与根的颜色相同。） => 由于表示 RB 树的一种方法是省略叶子，我们可以排除这种情况。
4）每个红色节点的两个孩子都是黑色的。=> B 树中内部节点的子节点总是位于另一个级别。
5）从给定节点到其任何后代叶子的每条简单路径都包含相同数量的黑色节点。=> B-tree 保持平衡，因为它要求所有叶节点处于相同的深度（因此 B-tree 节点的高度由从根到红黑树的叶的黑色链接的数量表示)
此外，Robert Sedgewick在这里有一个更简单的“非标准”实现：（他是《算法》一书的作者和韦恩）
于 2013-01-17T13:19:46.417 回答
1
这里有很多热量，但光线不多，所以让我们看看我们是否可以提供一些。
首先，RB 树是一种关联数据结构，不像数组，它不能接受一个键并返回一个关联的值，除非那是连续整数的 0% 稀疏索引中的整数“键”。数组的大小也不能增长（是的，我也知道 realloc()，但在幕后需要一个新数组，然后是 memcpy()），所以如果你有这些要求中的任何一个，数组不会做. 数组的内存效率是完美的。零浪费，但不是很聪明或灵活 - realloc() 无法承受。
第二，与元素数组上的 bsearch() 相比，bsearch() 是一种关联数据结构，RB 树可以动态增长（和缩小）自身的大小。bsearch() 可以很好地索引已知大小的数据结构，该数据结构将保持该大小。因此，如果您事先不知道数据的大小，或者需要添加或删除新元素，则使用 bsearch()。Bsearch() 和 qsort() 在经典 C 中都得到了很好的支持，并且具有良好的内存效率，但对于许多应用程序来说不够动态。不过，它们是我个人的最爱，因为它们快速、简单，而且如果您不处理实时应用程序，它们通常足够灵活。此外，在 C/C++ 中，您可以对指向数据记录的指针数组进行排序，指向 struc{} 成员，例如，您希望比较，然后重新排列指针数组中的指针，以便在指针排序结束时按顺序读取指针，从而按排序顺序生成数据。将其与内存映射数据文件一起使用是非常节省内存、快速且相当容易的。您需要做的就是在比较函数中添加几个“*”。
第三，与哈希表不同，哈希表也必须是固定大小，一旦填充就不能增长，RB 树会自动增长并平衡自身以保持其 O(log(n)) 性能保证。特别是如果 RB 树的键是 int，它可以比散列更快，因为即使散列表的复杂度是 O(1)，1 也可能是非常昂贵的散列计算。树的多个 1 时钟整数比较通常优于 100 时钟 + 哈希计算，更不用说重新散列，以及用于散列冲突和重新散列的 malloc()ing 空间。最后，如果您想要 ISAM 访问以及对数据的密钥访问，则排除哈希，因为哈希表中没有固有的数据排序，这与任何树实现中的数据自然排序相反。散列表的典型用途是为编译器提供对保留字表的键控访问。它的内存效率非常好。
第四，并且在任何列表中都非常低的是链接或双向链接列表，与数组相比，它自然支持元素插入和删除，并且这意味着调整大小。它是所有数据结构中最慢的，因为每个元素只知道如何到达下一个元素，因此您必须平均搜索 (element_knt/2) 链接才能找到您的数据。它主要用于在列表中间某处的插入和删除很常见的地方，尤其是在列表是循环的并且提供昂贵的过程的地方，这使得读取链接的时间相对较短。如果您唯一的要求是能够增加大小，我的一般 RX 是使用任意大的数组而不是链表。如果数组的大小用完了，可以重新分配（）更大的数组。STL 为您执行此操作“
第五，与任何其他数据结构相比，树支持对其排序数据的许多附加操作。例如，许多数据库查询利用这样一个事实，即可以通过指定它们的公共父级轻松指定一系列叶值，然后将后续处理集中在父级“拥有”的树的部分上。这种方法提供的多线程潜力应该是显而易见的，因为只需要锁定树的一小部分区域——即只有父节点拥有的节点和父节点本身。
简而言之，树是数据结构的凯迪拉克。你在使用的内存方面付出了高昂的代价，但你得到了一个完全自我维护的数据结构。这就是为什么，正如这里的其他回复所指出的，事务数据库几乎完全使用树。
于 2013-09-03T21:19:36.537 回答
0
如果您想查看红黑树的图形外观，我编写了一个红黑树的实现，您可以在此处下载
于 2008-12-08T16:06:36.103 回答
0
IME，几乎没人懂RB树算法。人们可以向你重复这些规则，但他们不明白为什么这些规则以及它们来自哪里。我也不例外:-)
出于这个原因，我更喜欢 AVL 算法，因为它很容易理解。一旦你理解了它，你就可以从头开始编写它，因为它对你有意义。
于 2009-03-24T21:04:04.837 回答
0
树可以很快。如果您在平衡二叉树中有一百万个节点，则平均需要进行 20 次比较才能找到任何一项。如果您在链表中有一百万个节点，则平均需要 50 万次比较才能找到相同的项目。
但是，如果树不平衡，它可能和列表一样慢，并且需要更多的内存来存储。想象一棵树，其中大多数节点都有右孩子，但没有左孩子；它是一个列表，但如果出现一个左节点，您仍然必须保留内存空间才能放入左节点。
无论如何，AVL 树是第一个平衡二叉树算法，关于它的 Wikipedia 文章非常清楚。老实说，维基百科上关于红黑树的文章一清二楚。
除了二叉树之外，B 树是每个节点可以有许多值的树。B-Tree不是二叉树，只是它的名字而已。它们对于有效利用内存非常有用；树的每个节点都可以调整大小以适应一块内存，这样你就不会（慢慢地）在内存中找到大量不同的东西，这些东西被分页到磁盘。这是B-Tree的一个显着示例。
于 2010-07-09T19:57:41.320 回答