问题标签 [red-black-tree]

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

我已经检查了典型的来源（维基百科、谷歌），并且大多数关于（特别是）红黑树的有用性和实现的描述都变得密集且难以理解。我敢肯定，对于有必要背景的人来说，这很有意义，但目前它读起来几乎就像一门外语。

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

我试图找到一个没有病毒或限制性许可的有效 C++ 区间树实现（很可能基于红黑树）。任何指向干净的轻量级独立实现的指针？对于我想到的用例，一开始就知道一组间隔（比如说一百万），我希望能够快速获得与给定间隔重叠的间隔列表。因此树一旦构建就不会改变——只需要快速查询。

有人告诉我，Java 类 TreeMap 使用了 RB 树的实现。如果是这种情况，如何在 TreeMap 上进行中序、前序和后序树遍历？

或者这是不可能的？

根据此页面http://www.eternallyconfuzzled.com/tuts/datastructures/jsw_tut_rbtree.aspx “自上而下删除”是红黑树节点删除的实现，通过将红色节点向下推来主动平衡树通过树，以便保证被删除的叶节点是红色的。由于叶子节点保证是红色的，因此您不必担心重新平衡树，因为删除红色叶子节点不会违反任何规则，并且您不必执行任何额外的操作来重新 -平衡并恢复红黑色。

“自下而上删除”涉及在树上进行正常的二分搜索以找到要删除的节点，交换叶节点（如果找到的节点不是叶节点），然后恢复红黑树属性在修复红黑规则违规的同时爬回树上。

自上而下的删除是否最小化了重新平衡操作的数量？自上而下的删除是否有可能在向下的过程中主动进行过多的重新着色和重新平衡？

这个场景怎么样：（x）表示一个红色节点

如果我想删除 16，自下而上的删除不会进行任何重新平衡，但自上而下的删除会一直向下重新着色节点，然后发现重新着色操作是不必要的：

迭代1：

迭代2：

迭代 3：

然后在第 4 次迭代中，您发现不需要下推，因为 16 已经是红色的。那么自上而下的删除是否更节省时间和空间？

我正在寻找所有 AVL 树都可以像红黑树一样着色的证据？任何人都可以提供证据吗？

这是重新草稿，你认为这个会起作用吗，我已经在某些条件下对其进行了测试，并且还没有让我失望

我正在阅读 Steve Yegge 关于单身人士的文章。在其中他提到他的老师告诉他 AVL 树是邪恶的。仅仅是红树和黑树是更好的解决方案吗？

作为程序员，我什么时候应该考虑使用 RB 树、B-树或 AVL 树？在决定选择之前需要考虑哪些关键点？

有人可以为每个树结构解释一个场景，为什么参考关键点选择它而不是其他树结构？

我有一个链表/二叉树方法库，可在标准容器不适合时使用 - 例如，当有不同类型的节点时，或者当我需要从二叉树转换为列表并再次转换回来时。它包括红黑树处理。

其中一种方法将双链表及时转换为完美平衡的简单二叉树O(n)（假设项目数是预先知道的）。该算法被称为“折叠”——它是二叉树再平衡算法的后半部分，曾在 Dobbs 博士上发表过。步骤基本...

• 给定树的大小，决定左右子树的大小

• 左子树的递归

• 从列表中弹出一个节点以用作根

• 递归右子树

• 将子树链接到根

我也有类似的方法可以创建一棵红黑树。原理相同，但递归跟踪节点高度 - 高度为零的节点创建为红色，所有其他节点为黑色。起始高度计算基于树大小中的最高设置位，并且经过调整，以便完美平衡(2^n)-1大小的树只有黑色节点（递归只下降到高度一）。

这里的要点是我在叶级别只有红色节点，最多恰好一半的节点是红色的。

问题是，虽然这是生成有效红黑树的一种简单方法，但它不是唯一的选择。避免让一棵完美平衡的树中的所有叶子都变红是一种随意的选择。我可以有交替的红色和黑色节点层。或者，在某些情况下，我可以通过发现完全平衡的子树并（如果需要红色节点）使子树根而不是其所有叶子变为红色，从而显着减少红色节点的数量。

问题是 - 是否有任何实际理由选择一种有效的红黑树形式而不是另一种？

这纯粹是好奇——我知道我没有任何实际的理由——但有谁知道这个选择很重要的专业应用程序吗？

我正在寻找C# 中红黑树的实现，具有以下功能：

• 在 O(log n) 中搜索、插入和删除。
• 成员类型应该是通用的。
• 支持Comparer(T)，用于按其中的不同字段进行排序T。
• 在树中搜索应该使用特定的字段，所以它不会接受T，但它会接受对它进行排序的字段类型。
• 搜索不应该只是精确值。应该支持搜索较低/较高的。

谢谢你。