https://stackoverflow.com/questions/20734
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian题
我最近读过的几本书中都提到了二叉树和二分搜索，但由于我仍处于计算机科学学习的开始阶段，所以我还没有上过真正涉及算法和数据的课程以严肃的方式进行结构。
我检查了典型的来源（维基百科，谷歌），大多数关于（特别是）红黑树的有用性和实现的描述都变得密集且难以理解。我确信对于具有必要背景的人来说，这是完全有道理的，但目前它读起来几乎就像一门外语。
那么，是什么让二叉树在您在编程时执行的一些常见任务中有用呢？除此之外，您更喜欢使用哪些树（请提供示例实现）以及为什么？
解决方案
红黑树有利于创建平衡良好的树。二叉搜索树的主要问题是很容易使它们不平衡。想象一下你的第一个数字是 15。那么之后的所有数字都越来越小于15。你会得到一棵树，左边很重，右边什么也没有。
红黑树通过在插入或删除时强制树保持平衡来解决这个问题。它通过祖先节点和子节点之间的一系列旋转来实现这一点。该算法实际上非常简单，尽管它有点长。我建议拿起 CLRS（Cormen、Lieserson、Rivest 和 Stein）教科书“算法简介”并阅读 RB 树。
该实现也并不是那么短，因此将其包含在这里可能并不是最好的选择。尽管如此，还是使用了树木 广泛地 适用于需要访问大量数据的高性能应用程序。它们提供了一种非常有效的查找节点的方法，并且插入/删除的开销相对较小。我再次建议您查看 CLRS 以了解它们的使用方式。
虽然 BST 可能不会被明确使用，但几乎每一个现代 RDBMS 中都存在一般使用树的一个例子。类似地，您的文件系统几乎肯定表示为某种树结构，并且文件同样以这种方式索引。树木为谷歌提供动力。树木几乎为互联网上的每个网站提供动力。
其他提示
我只想解决这样一个问题：“那么，是什么让二叉树在您在编程时发现自己执行的一些常见任务中有用？”
这是一个很多人不同意的大话题。有人说计算机科学学位中教授的算法（例如二叉搜索树和有向图）不会在日常编程中使用，因此无关紧要。其他人则不同意，他们说这些算法和数据结构是我们所有编程的基础，理解它们至关重要，即使你永远不需要自己编写。这会渗透到有关良好面试和招聘实践的对话中。例如， 史蒂夫·叶格 有一篇文章关于 谷歌面试 这解决了这个问题。记住这场辩论；有经验的人不同意。
在典型的业务编程中，您可能根本不需要经常创建二叉树甚至树。但是，您将使用许多内部使用树进行操作的类。每种语言中的许多核心组织类都使用树和哈希来存储和访问数据。
如果您参与更高绩效的工作或超出业务编程规范的情况，您会发现树是您直接的朋友。正如另一位发帖者所说，树是各种数据库和索引的核心数据结构。它们在数据挖掘和可视化、高级图形（2d 和 3d）以及许多其他计算问题中很有用。
我使用了以下形式的二叉树 BSP（二进制空间划分）树 在 3D 图形中。我目前正在再次查看树，以对大量地理编码数据和其他数据进行排序，以便在 Flash/Flex 应用程序中实现信息可视化。每当您突破硬件界限或想要在较低的硬件规格上运行时，理解和选择最佳算法可能会决定失败与成功。
没有一个答案提到 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 等内部都使用...
所以树非常有用，你可能经常使用它们而不自知。你很可能永远不会 需要 自己写一个，尽管我强烈推荐它作为一个有趣的编程练习。
红黑树和 B 树用于各种持久存储；因为树是平衡的，所以广度和深度遍历的性能会降低。
几乎所有现代数据库系统都使用树来存储数据。
正如迈克尔所说，BST 让世界运转。如果您正在寻找要实施的好树，请查看 AVL树 （维基百科）。它们有一个平衡条件，因此保证是 O(logn)。这种搜索效率使得投入任何类型的索引过程都是合乎逻辑的。唯一更有效的方法是散列函数，但它们很快就会变得丑陋。另外，你遇到了 生日悖论 （也称为鸽子洞问题）。
你用的是什么教材？我们用了 Java 中的数据结构和分析 作者：马克·艾伦·韦斯。当我打字的时候，我实际上把它放在腿上打开了。它有一个关于红黑树的精彩部分，甚至包括实现它所讨论的所有树所需的代码。
红黑树保持平衡，因此您不必深入遍历即可取出物品。在最坏的情况下，节省的时间使得 RB 树的时间复杂度为 O(log()n))，而不幸的二叉树可能会陷入不平衡的配置，并导致 O(n) 中的检索成为一种糟糕的情况。这在实践中或随机数据上确实会发生。因此，如果您需要时间关键的代码（数据库检索、网络服务器等），您可以使用 RB 树来支持有序或无序列表/集合。
但 RBTree 是为菜鸟准备的！如果你正在做人工智能并且需要执行搜索，你会发现你分叉了很多状态信息。您可以使用持久的红黑在 O(log(n)) 中分叉新状态。持久红黑树在形态操作（插入/删除）之前和之后保留树的副本，但不复制整个树（通常是 O(log(n)) 操作）。我开源了一个用于java的持久红黑树
我见过的对红黑树最好的描述是 Cormen、Leisersen 和 Rivest 的《算法导论》中的一篇。我什至可以充分理解它来部分实现一个（仅插入）。还有不少小程序，例如 这个 在各种网页上，这些网页以动画形式呈现该过程，并允许您观看并逐步执行构建树结构的算法的图形表示。
既然您问人们使用哪种树，您需要知道红黑树本质上是 2-3-4 B 树（即 4 阶 B 树）。B 树是 不是 相当于二叉树（如您的问题中所要求的）。
这里是一个极好的资源，描述了称为对称二叉 B 树的初始抽象，后来演变成 RBTree。在理解 B 树之前，您需要很好地掌握它。总结一下：红黑树上的“红色”链接是表示属于 B 树节点（键范围内的值）一部分的节点的一种方式，而“黑色”链接是在 B 树中垂直连接的节点。
因此，当您将红黑树的规则转换为 B 树时，您会得到以下结果（我使用的格式 红黑树规则 => B 树等效项):
1) 节点要么是红色，要么是黑色。=> b 树中的节点可以是节点的一部分，也可以作为新级别中的节点。
2）根是黑色的。（此规则有时会被省略，因为它不影响分析） => 根节点可以被视为内部根节点的一部分，作为假想父节点的子节点。
3）所有叶子（NIL）都是黑色的。（所有叶子的颜色与根的颜色相同。） => 由于表示 RB 树的一种方法是省略叶子，因此我们可以排除这种情况。
4）每个红色节点的两个孩子都是黑色的。=> B 树中内部节点的子节点始终位于另一层。
5）从给定节点到其任何后代叶子的每条简单路径都包含相同数量的黑色节点。=> B树保持平衡，因为它要求所有叶子节点都处于相同的深度（因此B树节点的高度由从红黑树的根到叶子的黑色链接的数量表示）
此外，Robert Sedgewick 还提供了一个更简单的“非标准”实现 这里: ：（他是这本书的作者 算法 与韦恩一起）
这里有很多很多的热量，但没有太多的光，所以让我们看看我们是否可以提供一些。
第一的, RB 树是一种关联数据结构，与数组不同，数组不能接受键并返回关联值，除非这是连续整数的 0% 稀疏索引中的整数“键”。数组的大小也不能增长（是的，我也知道 realloc()，但在幕后需要一个新数组，然后是一个 memcpy()），因此，如果您有这些要求中的任何一个，则数组将无法满足。数组的内存效率是完美的。零浪费，但不是很智能或灵活 - realloc() 无法承受。
第二, 与元素数组上的 bsearch() 相比（这是一种关联数据结构），RB 树的大小可以动态增长（和收缩）。bsearch() 可以很好地索引已知大小的数据结构，该数据结构将保持该大小。因此，如果您事先不知道数据的大小，或者需要添加或删除新元素，则 bsearch() 就不再适用。Bsearch() 和 qsort() 在经典 C 中都得到很好的支持，并且具有良好的内存效率，但对于许多应用程序来说不够动态。它们是我个人最喜欢的，因为它们快速、简单，而且如果您不处理实时应用程序，通常也足够灵活。此外，在 C/C++ 中，您可以对指向数据记录的指针数组进行排序，例如，您希望比较，指向 struc{} 成员，然后重新排列指针数组中的指针，以便按顺序读取指针在指针末尾排序会按排序顺序生成数据。将其与内存映射数据文件一起使用是非常高效、快速且相当容易的。您需要做的就是在比较函数中添加一些“*”。
第三, 与哈希表不同，哈希表也必须是固定大小，并且一旦填充就无法增长，RB 树会自动增长并自我平衡以维持其 O(log(n)) 性能保证。特别是如果 RB 树的键是 int，它可能比哈希更快，因为即使哈希表的复杂度是 O(1)，1 也可能是非常昂贵的哈希计算。树的多个 1 时钟整数比较通常优于 100 时钟+哈希计算，更不用说重新哈希以及用于哈希冲突和重新哈希的 malloc() 空间。最后，如果您想要 ISAM 访问以及对数据的键访问，则排除散列，因为散列表中没有固有的数据排序，这与任何树实现中的数据自然排序相反。哈希表的经典用途是为编译器提供对保留字表的键控访问。它的内存效率非常出色。
第四, 链接列表或双向链接列表在任何列表中都位于非常靠后的位置，与数组相比，它自然支持元素插入和删除，以及这意味着调整大小。它是所有数据结构中最慢的，因为每个元素只知道如何到达下一个元素，因此您平均必须搜索 (element_knt/2) 个链接才能找到数据。它主要用于列表中间某处的插入和删除很常见的情况，特别是列表是循环的并且提供昂贵的过程，这使得读取链接的时间相对较短的情况。如果您唯一的要求是能够增加大小，我的一般 RX 是使用任意大的数组而不是链表。如果数组的大小用完了，可以 realloc() 一个更大的数组。当您使用向量时，STL 会“在幕后”为您完成此操作。虽然很粗糙，但如果不需要插入、删除或键控查找，速度可能会快 1,000 倍。它的内存效率很差，特别是对于双向链表。事实上，需要两个指针的双向链表与红黑树一样内存效率低下，而且没有其吸引人的快速、有序检索特性。
第五, 与任何其他数据结构相比，树支持对其排序数据进行许多附加操作。例如，许多数据库查询利用这样一个事实，即可以通过指定其公共父代来轻松指定一系列叶值，然后将后续处理集中在父代“拥有”的树部分上。这种方法提供的多线程潜力应该是显而易见的，因为只需要锁定树的一小部分区域 - 即，仅父节点拥有的节点以及父节点本身。
简而言之，树是数据结构中的凯迪拉克。您在使用内存方面付出了高昂的代价，但您获得了完全自我维护的数据结构。正如其他回复中所指出的，这就是为什么事务数据库几乎只使用树。
如果您想了解红黑树的图形外观，我已经编写了红黑树的实现，您可以 在这里下载
IME，几乎没人懂RB树算法。人们可以向你重复规则，但他们不理解 为什么 这些规则以及它们来自哪里。我也不例外:-)
因此，我更喜欢AVL算法，因为它很容易 理解. 。一旦理解了它，您就可以从头开始编写代码，因为它对您来说很有意义。
树可以很快。如果平衡二叉树中有一百万个节点，则平均需要二十次比较才能找到任何一项。如果链表中有一百万个节点，平均需要五十万次比较才能找到相同的项目。
但是，如果树不平衡，它可能会像列表一样慢， 和 还需要更多的内存来存储。想象一棵树，其中大多数节点都有右子节点，但没有左子节点；它 是 一个列表，但是如果出现左节点，您仍然需要保留内存空间来放入左节点。
无论如何， AVL树 是第一个平衡二叉树算法，维基百科上关于它的文章非常清楚。老实说，维基百科关于红黑树的文章清晰如泥。
除了二叉树之外，B 树是每个节点可以有多个值的树。B树是 不是 二叉树，恰好是它的名字。它们对于有效利用内存确实非常有用；树的每个节点的大小都可以调整为适合一个内存块，这样您就不会（慢慢地）在内存中找到大量被分页到磁盘的不同内容。这是一个惊人的例子 B树.
