问题标签 [red-black-tree]

我知道我的 STL（g++ 4.xx 附带）使用红黑树来实现地图等容器。是否可以直接使用STL内部的红黑树。如果是这样，怎么做？如果不是，为什么不——为什么 STL 不暴露红黑树？

令人惊讶的是，我无法使用谷歌找到答案。

编辑：我正在研究使用红黑树作为插入时额外分配器构造函数调用的解决方案。看到这个问题。我的 STL 使用红黑树来实现地图。

在网上很难找到红黑树的实现，尤其是学习。

我在哪里可以找到一个简单的红黑树实现（首选 C#）？

考虑N一个圆圈中的和弦，每个和弦都由它的端点决定。描述一种O(nlogn)确定在圆内相交的弦对数的解决方案。

假设：没有两个和弦共享一个端点。

根据我的书，在 AVL 树中从偶数高度的节点到奇数高度的节点的红色链接着色给出了（完全平衡的）2-3-4 树，其中红色链接不一定是左倾的。但我不知道具体如何。当我尝试一些例子时，我一直卡住。有人可以为我说明一下吗？

假设你有一棵红黑树，它是一个有效的二叉搜索树并且不违反任何这些规则：

• 一个节点要么是红色的，要么是黑色的。
• 根是黑色的。
• 所有叶子 (NIL) 都是黑色的。
• 每个红色节点的两个孩子都是黑色的。
• 从给定节点到其任何后代叶子的每条简单路径都包含相同数量的黑色节点。

这样一棵红黑树看起来像这样：

满足这些限制的每棵可能的树是否都有插入和删除的序列，从而生成红黑树？

_{我问这个问题是因为我想写一篇关于红黑树的博客文章，我想举一些例子。}

如果你想测试一个反例：这是一个在 python 中实现的红黑树，其中实现了生成图像的函数。

澄清问题：我们制作游戏。

• 我画了一棵符合所有限制的红黑树。
• 你必须找到插入和删除的序列，这样你才能得到我的红黑树。

我可以画一棵红黑树，让你赢不了吗？

颜色很重要！如果树有不同的形状或不同的颜色，它就不是同一棵红黑树。

您至少应该知道如何生成这两个红黑树：

请注意，这只是对您的检查，如果它可以工作。如果你只知道如何得到这两个红黑树，你是无法回答这个问题的！

我知道这个类使用红黑树，但这是否意味着获得最少元素是 O(log(n)) 还是 O(1) 或其他什么？

谢谢！

我在这里有一个非常简单的问题：红黑树是否必须按排序顺序排列？我问这个是因为维基百科页面右侧的小方框 (http://en.wikipedia.org/wiki/Red–black_tree) 说搜索时间是 O(log(n)); 但是，这不仅是对树进行排序的情况。但另一方面，属性 s

显然你可以做任何一个，但前者更常见。

你为什么会选择后者，它是如何工作的？

我读到这个：http ://www.drdobbs.com/cpp/stls-red-black-trees/184410531 ；这让我觉得他们做到了。它说：

insert_always 是一个状态变量，它告诉 rb_tree 是否允许同一键值的多个实例。此变量由构造函数设置，并由 STL 用于区分 set 和 multiset 以及 map 和 multimap。set 和 map 只能出现一次特定键，而 multiset 和 multimap 可以出现多次。

虽然现在我认为这并不一定意味着。他们可能仍在使用容器。

我认为具有相同键的所有节点都必须排成一行，因为您必须将所有具有相同键的节点存储在右侧或左侧。因此，如果您将相等的节点存储在右侧并插入 1000 个 1 和一个 2，那么您基本上会有一个链表，这会破坏红黑树的属性。

为什么我找不到太多关于它的原因是它只是一个坏主意？

我很清楚为什么 QMap 是通过 skiplist 数据结构而不是 rb-tree 实现的？有一个非常有趣的SO 线程，关于并发数据结构和跳过列表对 rb-tree 的好处，优点和缺点。它确实是非常有趣的对话，带有有用的链接，但 QMap 不是线程安全的，它不做任何互斥锁来同步访问开箱即用。它需要包装器或子类化。

对我来说，编写“手工制作的”跳过列表而不是 rb-tree 并不简单，所以这也不明显。

在非线程安全的 Qt 容器的上下文中是否有任何终止功能？

提前Tnx。

背景：我将插入大约十亿个键值对。我需要一个内存索引，我可以使用它同时查找（唯一的，64 位整数）键的（32 位整数）值。没有更新，没有删除，没有遍历。键通常随着时间逐渐增加。

什么索引结构最适合处理这个问题？

我能想到的要求是：

• 由于密钥的增加，它需要进行有效的再平衡
• 它需要有效地使用内存以适应内存，最好 < 28GB
• 它需要有非常有效的查找