红黑树
我已经看到了最近几本书中提到的二叉树和二进制search，但由于我还在计算机科学的学习之初，我还没有select一门真正处理algorithm和数据的课程结构严重。
我已经检查了典型的资料来源（维基百科，谷歌），大部分描述了红黑树（特别是红黑树）的用途和实施，已经变得密集而难以理解。 我确信有必要的背景的人，这是完全合理的，但目前它几乎像一门外语。
那么是什么让二叉树在编程时发现自己在做的一些常见任务中有用呢？ 除此之外，你更喜欢使用哪些树（请包括一个示例实现），为什么？
红黑树适合创造均衡的树木。 二叉search树的主要问题是你可以很容易地使它们不平衡。 想象一下，你的第一个数字是15.然后所有数字越来越小于15.你将有一棵树，在左侧非常沉重，右侧没有任何东西。
红黑树解决这个问题，只要你插入或删除，强制你的树被平衡。 它通过祖先节点和子节点之间的一系列旋转来实现这一点。 algorithm实际上非常简单，虽然有点长。 我build议selectCLRS（Cormen，Lieserson，Rivest和Stein）教科书，“Introduction to Algorithms”，并阅读RB树。
实现也不是那么简短，所以在这里包括它可能不是最好的。 尽pipe如此，树被广泛用于需要访问大量数据的高性能应用程序。 它们提供了一种查找节点的非常有效的方法，插入/删除的开销相对较小。 再次，我build议看看CLRS来了解它们是如何使用的。
虽然BST可能不被明确地使用 – 一般来说树的使用的一个例子几乎在每个现代的RDBMS中。 同样，你的文件系统几乎可以肯定地表示为某种树形结构，并且文件同样以这种方式被索引。 树木为谷歌提供力 互联网上的每一个网站都支持树木。
我只想解决这个问题：“那么在编程时，你发现自己在做的一些常见任务中，二叉树是否有用呢？
这是很多人不同意的大话题。 有人说，在CS学位教授的algorithm如二叉search树和有向图不在日常编程中使用，因此是不相关的。 其他人则不同意，认为这些algorithm和数据结构是我们所有编程的基础，即使你不必为自己编写一个程序和数据结构，也必须理解它们。 这将过滤到关于良好的面试和招聘实践的谈话。 例如， Steve Yegge 在Google上有一篇关于面试的文章。 记住这个辩论; 有经验的人不同意。
在典型的商业编程中，您可能不需要经常创build二叉树甚至树。 但是，您将使用许多内部使用树的类。 每种语言中的许多核心组织类都使用树和哈希来存储和访问数据。
如果你参与更高性能的工作，或者在业务编程规范之外的情况下，你会发现树木是直接的朋友。 另一个海报说，树是数据库和各种指标的核心数据结构。 它们在数据挖掘和可视化，高级graphics（2D和3D）以及其他许多计算问题中很有用。
我用三维graphics的BSP（二进制空间分区）树的forms使用二叉树。 我目前正在查看树木，以便在Flash / Flex应用程序中对大量的地理编码数据和其他数据进行信息可视化分类。 无论何时你推动硬件的边界，或者你想要在较低的硬件规格上运行，理解和select最佳的algorithm都可以在失败和成功之间做出区别。
没有一个答案提到什么是BSTs的好处。
如果你想要做的只是按值查找，那么哈希表要快得多，O（1）插入和查找（摊销最好的情况）。
BST将是O（log N）查找，其中N是树中节点的数量，插入也是O（log N）。
RB和AVL树是非常重要的，因为这个属性提到了另外一个答案，如果一个普通的BST是用有序值创build的，那么这棵树将会和插入的值一样高，这对于查找性能是不利的。
RB和AVL树之间的区别在于在插入或删除之后重新平衡所需的旋转，AVL树是用于重新平衡的O（log N），而RB树是O（1）。 这种持续复杂性的好处的一个例子是，如果您需要保留持久数据源，如果您需要跟踪更改以回滚，则必须使用AVL树跟踪O（log N）个可能的更改。
为什么你愿意花费在哈希表上的树的成本？ 订购！ 哈希表没有顺序，另一方面，BST通常依靠其结构自然sorting。 因此，如果您发现自己将一堆数据放入数组或其他容器中，然后将其sorting，则BST可能是更好的解决scheme。
树的order属性为您提供了一些有序的迭代function，按顺序，深度优先，宽度优先，预先sorting，后序排列。 这些迭代algorithm在不同的情况下是有用的，如果你想查找它们。
几乎每个有序的语言库容器，C ++ Set和Map，.NET SortedDictionary，Java TreeSet等都使用红黑树。
所以树木是非常有用的，你甚至可以不经常地使用它们。 你很可能永远不需要自己写一个，虽然我会强烈推荐它作为一个有趣的编程练习。
红黑树和B树被用于各种持久存储; 由于树木平衡，宽度和深度遍历的性能得到缓解。
几乎所有的现代数据库系统都使用树来存储数据。
正如迈克尔所说，BST让世界变得圆满。 如果你正在寻找一个好的树来实现，看看AVL树 （维基百科）。 他们有一个平衡的条件，所以他们保证是O（logn）。 这种search效率使得在任何一种索引过程中都是合乎逻辑的。 唯一能提高效率的就是哈希函数，但是这些函数会很快，很快，而且很匆忙。 此外，你遇到生日悖论 （也被称为鸽子洞问题）。
你在用什么课本？ 我们使用了Mark Allen Weiss的“ 数据结构和Java分析” 。 当我打字的时候，我已经把它打开了。 它有一个很大的关于红黑树的部分，甚至还包括了实现所有树的代码。
红黑树木保持平衡，所以你不必穿越深处去获取物品。 节省的时间在最坏的情况下使得RB树O（log（）n）），而不幸的二叉树可以进入偏好的configuration并且导致在O（n）中的检索不好的情况。 这在实践中或随机数据中发生。 所以如果你需要时间关键的代码（数据库检索，networking服务器等），你可以使用RB树来支持有序或无序的列表/集合。
但RBTrees是小菜一碟！ 如果你正在做人工智能，你需要执行search，你会发现你叉状态信息很多。 你可以使用一个持久的红黑来在O（log（n））中分出新的状态。 持久的红黑树在形态操作（插入/删除）之前和之后保留树的副本，但不复制整个树（通常和O（log（n））操作）。 我已经为java开源了一个持久的红黑树
我所见过的红黑树最好的描述是Cormen，Leisersen和Rivest的“algorithm导论”。 我甚至可以理解它，部分实现一个（仅插入）。 在不同的网页上也有不less小应用程序，例如This One ，可以为stream程添加animation，让您观看并逐步完成构build树结构的algorithm的graphics表示。
这里有很多很多的热量，但是没有太多的光线，所以让我们看看能否提供一些。
首先 ，一个RB树是一个关联的数据结构，不像一个数组，它不能取一个键并返回一个相关的值，除非在连续整数的0％稀疏索引中是一个整数“键”。 一个数组的大小也不能增长（是的，我也知道realloc（），但是在需要一个新的数组，然后是一个memcpy（））的覆盖下，所以如果你有这些需求中的任何一个，数组将不会。 一个数组的内存效率是完美的。 零浪费，但不是很聪明，或灵活 – realloc（）不能承受。
其次 ，与一个元素数组（它是一个关联数据结构）上的bsearch（）相比，一个RB树可以dynamic增长（AND缩小）它自己的大小。 bsearch（）适用于索引已知大小的数据结构，该数据结构将保持该大小。 因此，如果您事先不知道数据的大小，或者需要添加或删除新的元素，那么将会出现一个bsearch（）。 经典C中Bsearch（）和qsort（）都得到很好的支持，并且具有良好的内存效率，但是对于许多应用程序来说，它们不够dynamic。 他们是我个人最喜欢的，但是因为他们快速，简单，而且如果你不处理实时应用程序，通常是足够灵活的。 此外，在C / C ++中，您可以对指向数据logging的指针数组进行sorting，指向struc {}成员，例如，您希望进行比较，然后重新排列指针数组中的指针，以便按顺序读取指针在指针sorting的最后，按sorting顺序生成数据。 在内存映射的数据文件中使用这个function是非常有效的，快速而且相当容易的。 所有你需要做的就是添加一些“*”到你的比较函数。
第三 ，与哈希表相比，哈希表也必须是固定的大小，并且一旦填充就不能生长，RB树将自动自我增长并自我平衡以保持其O（log（n））性能保证。 特别是如果RB树的键是一个int，它可以比散列更快，因为即使散列表的复杂性是O（1），那么1可能是一个非常昂贵的散列计算。 树的多个1时钟整数的比较往往胜过100时钟+散列计算，更不用说重新散列，而malloc（）空间用于散列冲突和重排。 最后，如果你想要ISAM访问以及对你的数据的键入访问，排除一个散列，因为散列表中固有的数据没有sorting，与任何树实现中的数据的自然sorting相反。 哈希表的经典用法是为编译器提供对保留字表的键控访问。 它的记忆效率非常好。
第四 ，在任何列表中都很低，是链接列表或双向链接列表，与数组相比，它自然支持元素的插入和删除，并且这意味着resize。 这是所有数据结构中速度最慢的，因为每个元素只知道如何到达下一个元素，因此您必须平均search（element_knt / 2）链接来查找您的数据。 它主要用于在列表中间某个地方插入和删除的地方，尤其是列表是循环的，并且提供了一个昂贵的过程，使得阅读链接的时间相对较less。 我的一般RX是使用一个任意大的数组而不是一个链表，如果你唯一的要求是它能够增加大小。 如果用数组大小不足，则可以重新分配（）更大的数组。 当你使用一个向量时，STL为你做了“下”的工作。 原油，但如果不需要插入，删除或键控查找，速度可能会快上千倍。 这是记忆效率差，特别是双链表。 实际上，需要两个指针的双向链表与红黑树一样没有效率，而没有任何快速，有序的检索特性。
第五 ，树比其他任何数据结构支持许多额外的操作。 例如，许多数据库查询利用这样一个事实：通过指定它们的公共父项，可以容易地指定一系列叶值，然后将后续处理的重点放在父“拥有”的树部分上。 这种方法提供的multithreading的潜力应该是显而易见的，因为只有树的一小部分需要被locking – 即只有父节点拥有的节点和父节点本身。
总之，树木是数据结构的凯迪拉克。 您使用的内存支付很高的价格，但您得到一个完全自我维护的数据结构。 正如其他答复所指出的，这就是为什么交易数据库几乎完全使用树木的原因。
既然你问哪个树人使用，你需要知道一棵红黑树根本上是一个2-3-4的B树（即4阶B树）。 B树不等同于二叉树（正如您的问题所述）。
这里有一个非常好的资源，描述了最初的抽象，即对称二叉B-树，后来演变为RBTree。 在有意义之前，你需要很好的把握B树。 总结：红黑树上的“红”链接是一种表示属于B树节点（键范围内的值）的节点的方式，而“黑”链接是在B中垂直连接的节点-树。
所以，当你翻译一棵红黑树的规则时，你会得到一个B树（我使用红黑树规则 => B树的等价格 ）：
1）节点是红色或黑色。 => B树中的节点可以是节点的一部分，也可以是新层次中的节点。
2）根部是黑色的。 （这个规则有时会被省略，因为它不影响分析）=>根节点可以被认为是内部根节点的一部分，作为一个虚构父节点的子节点。
3）所有叶子（NIL）都是黑色的。 （所有的叶子和根的颜色相同。）=>由于表示RB树的一种方法是通过省略树叶，我们可以排除这一点。
4）每个红色节点的孩子都是黑色的。 => B树中的内部节点的孩子总是躺在另一层。
5）从给定节点到其任何后代树叶的每条简单path都包含相同数目的黑色节点。 => B树保持平衡，因为它要求所有叶节点处于相同的深度（因此，B树节点的高度由从红黑树的根到叶的黑链接的数量表示）
而且，Robert Sedgewick 在这里还有一个更简单的“非标准”实现:(他是Wayne的algorithm书的作者）
如果你想看看红黑树应该如何用graphics来看，我已经编写了一个红黑树的实现，你可以在这里下载
IME，几乎没有人理解RB树algorithm。 人们可以重复规则给你，但他们不明白为什么这些规则和他们来自哪里。 我也不例外:-)
出于这个原因，我更喜欢AVLalgorithm，因为它很容易理解 。 一旦你理解了，你可以从头开始编码，因为它对你有意义。
树木可以快速。 如果在一个平衡的二叉树中有一百万个节点，则平均需要二十个比较才能find任何一个项目。 如果在链表中有一百万个节点，平均需要五十万次比较才能find相同的项目。
如果树不平衡，它可能会像列表一样慢，也需要更多的内存来存储。 想象一下，大多数节点有一个正确的孩子，但没有离开孩子的树; 它是一个列表，但是如果出现的话，你仍然需要占用内存空间来放置左边的节点。
无论如何， AVL树是第一个平衡的二叉树algorithm，维基百科的文章很清楚。 维基百科的红黑树上的文章老实说是泥土。
除了二叉树，B树是每个节点可以有许多值的树。 B树不是一棵二叉树，恰好是它的名字。 它们对于有效利用内存非常有用; 树的每个节点都可以resize以适应一块内存，这样就不会（缓慢地）去寻找被分页到磁盘的内存中的大量不同的东西。 这是B树的一个惊人的例子。
如果你想看看我的红黑树的实现。 http://code.google.com/p/cstl/source/browse/src/c_rb.c
