关于算法：红黑树

Red-Black Trees

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

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

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

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

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

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

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

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

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

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

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

我在3d图形中使用了BSP(二进制空间分区)树形式的二进制树。我目前正在再次查看树，以对大量经过地理编码的数据和其他数据进行排序，以在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树用于各种持久性存储。因为树木是平衡的，所以宽度和深度遍历的性能得到了缓解。

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

红黑树保持平衡，因此您不必遍历所有东西即可取出物品。所节省的时间使RB树在最坏的情况下成为O(log()n))，而不幸的二叉树会陷入偏侧配置并导致在O(n)中进行检索的糟糕情况。实际上，这确实发生在随机数据上。因此，如果您需要时间紧迫的代码(数据库检索，网络服务器等)，则可以使用RB树来支持有序或无序列表/集合。

但是RBTrees适合新手！如果您正在执行AI，并且需要执行搜索，则会发现您有很多状态信息。您可以使用持久的红黑色在O(log(n))中派生新状态。持久性红黑树在形态操作(插入/删除)之前和之后保留树的副本，但不复制整个树(通常和O(log(n))操作)。我已经为Java开源了一个持久的红黑树

A Java implementation of persistent red-black trees open sourced

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

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

您正在使用什么教科书？我们使用了Mark Allen Weiss编写的Java中的数据结构和分析。我在键入此字时，实际上将其打开。它有很多关于红黑树的章节，甚至包括实现所讨论的所有树所必需的代码。

这里有很多热量，但没有很多光，所以让我们看看是否可以提供一些热量。

好。

首先，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会为您"暗中进行"。粗略，但如果不需要插入，删除或键控查找，则可能会快1000倍。它的内存效率很差，尤其是对于双链表。实际上，需要两个指针的双向链表与红黑树一样，在存储效率上也很差，同时又没有吸引人的快速，有序的检索特性。

好。

第五，树比其他任何数据结构都支持对已排序数据进行许多其他操作。例如，许多数据库查询都利用了这样一个事实，即可以通过指定其公共父级，然后将后续处理集中在父级"拥有"的树部分上，来轻松指定一系列叶值。这种方法提供的多线程潜力应该是显而易见的，因为仅需要锁定树的一小部分-即，只有父级拥有的节点以及父级本身。

好。

简而言之，树是数据结构的凯迪拉克。就使用的内存而言，您付出了高昂的代价，但您却获得了一个完全自我维护的数据结构。这就是为什么，如此处其他答复所述，事务数据库几乎只使用树。

好。

由于您要问人们使用哪种树，因此您需要知道一棵红黑树从根本上说是2-3-4 B树(即4阶B树)。 B树不等同于二叉树(如您的问题所问)。

这是一个很好的资源，它描述了称为对称二进制B树的初始抽象，该抽象后来演变为RBTree。您需要对B树有很好的了解，然后才有意义。总结一下：红黑树上的"红色"链接是一种表示B树节点(值在关键范围内)的一部分的节点的方式，而"黑"链接则是在B树中垂直连接的节点-树。

因此，这就是将红黑树的规则转换为B树时得到的结果(我使用的格式为Red Black tree rule => B Tree equival)：

1)节点为红色或黑色。 => b树中的节点可以是节点的一部分，也可以是新级别中的节点。

2)根是黑色的。 (有时会忽略此规则，因为它不会影响分析)=>根节点可以视为内部根节点的一部分，也可以视为虚构父节点的子节点。

3)所有叶子(NIL)均为黑色。 (所有叶子的颜色都与根相同。)=>由于表示RB树的一种方法是省略叶子，因此可以排除这种情况。

4)每个红色节点的子节点均为黑色。 => B树中内部节点的子代始终位于另一个级别。

5)从给定节点到其任何后代叶子的每个简单路径都包含相同数量的黑色节点。 => B树保持平衡，因为它要求所有叶节点的深度都相同(因此，B树节点的高度由从红黑树的根到叶的黑色链接数表示) )

此外，Robert Sedgewick还有一个更简单的"非标准"实现：(他与韦恩一起是《算法》一书的作者)