使用STL的红黑树内部实现
我知道我的STL（随g++ 4.x.x提供）使用红黑树来实现诸如map之类的容器。是否可以直接使用STL内部的红黑树？如果可以，如何使用？如果不行，为什么不行——为什么STL没有暴露红黑树？ 令人惊讶的是，我在谷歌上找不到答案。 编辑：我正在研究使用红黑树作为解决插入时额外分配构造函数调用...
在红黑树中，自顶向下的删除操作比自底向上的删除操作更快且空间利用率更高吗？
根据此页面 http://www.eternallyconfuzzled.com/tuts/datastructures/jsw_tut_rbtree.aspx，“自顶向下删除(Top-down deletion)”是红黑树节点删除的一种实现，通过将红色节点沿着树向下推送，使得要删除的叶子节点...
为什么CFS调度程序使用红黑树？
CFS调度器根据最小虚拟时间选择下一个进程，为了有效地获取此值，它使用红黑树(rbtree)，使用rbtree可以在O(h)的时间内获得最小值，其中h是rbtree的高度。但是，使用min-heap我们可以仅在O(1)时间内获得最小虚拟时间进程。我想知道为什么CFS实现中没有考虑min-hea...
为什么Java TreeMap选择基于红黑树的实现？
维基百科上的AVL树条目的第三段说：“由于AVL树更加严格平衡，因此在查找密集型应用中比红黑树更快。” 因此，对于使用哈希的数据结构来说，在实现TreeMap时，不应该使用红黑树而应该使用AVL树。
使用红黑树进行排序
红黑树 插入的最坏情况运行时间是 O(lg n)。如果我在树上执行 中序遍历(in-order walk)，我基本上会访问每个节点，因此打印排序集合的总最坏运行时将是 O(n lg n)。 我很好奇，为什么不使用红黑树进行排序而改用 快速排序（其平均运行时间为 O(n lg n)）。 我认...
为什么TreeMap不允许使用null键？
我正在尝试理解Java集合框架背后的概念，并遇到了这个问题 - 为什么TreeMap不允许空键？ 如果我们尝试将null键添加到TreeMap中，它会引发NullPointerException。 我尝试通过谷歌内部工作原理来了解TreeMap，并发现它使用红黑树算法，但我现在很难理解，正...
使用《Delphi圣典》中的红黑树实现时，Promote() 函数存在问题。
我正在使用Julian Bucknall在他著名的书籍The Tomes Of Delphi中编写的Red-Black树实现。源代码可以从此处下载，我在Delphi 2010中使用原始代码，并对TdBasics.pas进行修改，以便它在现代版本的Delphi中编译（大部分注释掉 - 树代码只需...
每个合法的红黑树都能存在吗？
假设您有一棵红黑树，它是一个有效的二叉搜索树，不违反任何规则： 节点是红色或黑色。 根是黑色的。 所有叶子（NIL）都是黑色的。 每个红色节点的两个子节点都是黑色的。 从给定节点到其任何后代叶子的每条简单路径包含相同数量的黑色节点。 这样的红黑树看起来像这样： 符合这些限制的每个可...
使用红黑树的字典——删除错误
我正在尝试使用红黑树实现一个字典。 我已经测试了插入方法，似乎工作得很好，RBtree似乎保持了正确的形状和颜色。执行二叉树节点删除的方法似乎是正确的，但是在删除后调用的deleteFixUp方法上出现了巨大的问题。 您是否愿意帮助我找出我做错了什么？当然，如果您有任何改进代码的建议，将不胜...
在Scala中使用的标准二叉搜索树结构是什么？
什么是Scala 2.10.x中应该使用的标准平衡二叉搜索树实现？我正在寻找，看起来 AVLTree 已被删除，而 RedBlack 已被弃用，并显示消息（自版本2.10.0以来）改用TreeMap或TreeSet。但是， TreeMap 和 TreeSet 不提供我需要的功能，因为我需要...