4回答
可能重复：
我开始在麻省理工学院的红黑树上看，15分钟后就放弃了.
当然，我以前没有看过10次讲座，但是为什么在进入理论之前没有真实世界的例子呢？
有人能给出一个例子并解释为什么红黑树是一种基本的数据结构吗？
浏览 4提问于2012-01-06得票数 5
6回答
除了节点中的红色和黑色之外，AVL和红色黑色树都是自平衡的。选择红黑树而不是AVL树的主要原因是什么？红黑树的应用是什么？
浏览 1提问于2012-12-13得票数 137
3回答
本文研究的是在链路上使用红黑树数据结构的文件系统的调度算法
我的问题是:在CFS中使用红黑树的目的是什么，为什么不能使用AVL树？
浏览 2提问于2012-06-27得票数 2
回答已采纳
2回答
有人看到STL的实现吗? stl::set不是作为红黑树实现的吗？
我问的原因是，在我的实验中，B树的性能比std::set (和其他红黑树实现)高出2到4倍，这取决于B的值。我很好奇，当数据结构看起来更快的时候，是否有令人信服的理由使用红黑树。
浏览 2提问于2014-10-24得票数 8
回答已采纳
2回答
红黑树是如何工作的？
、、、
有很多关于红黑树的问题，但没有一个回答它们是如何工作的。为什么叫红黑呢？这如何保持树的平衡(从而提高不平衡的正常二进制搜索树的性能)？我只是想了解一下它的工作原理和原因。
浏览 4提问于2011-04-28得票数 20
回答已采纳
3回答
的第三段说：“由于AVL树更严格地平衡，所以对于查找密集型应用程序，它们比红黑树更快。”
那么，不应该使用AVL树而不是红黑树来实现吗(因为基于散列的数据结构将有更多的查找密集型应用程序)？
浏览 0提问于2013-02-18得票数 13
回答已采纳
1回答
平衡二叉树的比较
、、、
我读过一些关于自平衡二叉树的问答，但我并不完全熟悉它们。
我认识的第一个是AVL，第二个是红黑树。
有一件事我不太明白:根据一些书籍和文章，AVL可以比红黑树更快地进行搜索，这是可以理解的。
，那么，红黑树相对于AVL的边缘是什么?在AVL中的，可能在每次插入之后，我们必须检查平衡，但是在红黑树中，我们不需要经常这样做，对吗？
PS:我搜索类似的东西，但没有得到满意的答案。希望一些朋友能给我一个详细的比较，自我平衡的树木。
浏览 2提问于2011-08-27得票数 3
回答已采纳
3回答
我目前正在实现一个红黑树数据结构，以执行一些应用程序的优化。
在我的应用程序中，在给定的点上，我需要从树中删除小于或等于给定值的所有元素(您可以假设这些元素是整数)。
我可以一个接一个地删除元素，但我希望有更快的东西。因此，我的问题是:如果我删除了一棵红黑树的整个子树，我如何修复这棵树来恢复高度和颜色不变量？
浏览 7提问于2011-04-14得票数 6
回答已采纳
1回答
我知道红黑树只是一个平衡的二进制搜索树。所以我计算了元素数量为2^n的数据集的平均搜索成本(基本上是比较次数)。数据的设计方式是，它将形成完美的二进制搜索树。然而，在计算了平均成本后，我意识到红黑树的计算平均搜索成本略高于完全平衡的二进制搜索树。下面是我的表格：
# of elements Binary S. Tree Red-Black Tree
1 | 1 | 1
3 | 1.66667 | 1.6667
7 | 2.42857 |
浏览 0提问于2018-04-08得票数 1
1回答
在当前的C++ STL中，红黑树在哪里使用？(我假设地图和集合做？)红黑树使用2-3树(即只有左或右可以是红色的)还是2-3-4树(即左、右都可以是红色的)？在STL中有红黑树库吗？
浏览 4提问于2022-07-30得票数 1
回答已采纳
2回答
我想更好地理解这种差异，但还没有找到一个可以将其分解到我的水平的来源。
我知道两棵树每次插入最多需要2次旋转。那么如何在红黑树中插入得更快呢？
在avl树中插入要求O(log )旋转，而O(1)在红-黑中如何插入？
浏览 7提问于2014-09-01得票数 5
回答已采纳
在过去的一次考试中，我们曾被要求通过观察一棵树的形状来判断它是否是红黑平衡的。我还没有找到任何关于如何做到这一点的信息，只有一种说法是，如果最长路径不超过最短路径的两倍，则二叉树是红黑平衡的，但我非常确定这也是空路径平衡树的要求。对吗？有没有办法判断一棵树的形状是不是红黑平衡的？
浏览 1提问于2015-05-11得票数 5
3回答
红黑树的直觉
、、
我想知道红黑树是怎么工作的。我理解算法，如何修复插入和删除操作后的属性，但有些事情我不清楚。为什么红黑树比二叉树更平衡？我想要理解的直觉，为什么旋转和固定树属性使红黑树更加平衡。
谢谢。
浏览 0提问于2015-04-23得票数 4
回答已采纳
1回答
为什么在红黑树上使用堆？
、、、、
与堆的O(n)清除相比，红黑树可以支持O(logn)去除。
但是，看起来所有针对红黑树的操作都更快/等于堆的操作。所以我的问题是，为什么我们用堆在红黑树上？在我看来，一棵红黑树可以做堆能做的任何事情，但速度更快/相当。
谢谢。
浏览 3提问于2019-03-21得票数 3
长期以来，我一直在学习数据结构和算法，对于红黑树、显示树等著名数据结构的实际应用还不确定。
我知道B树已经被广泛地应用于数据库中。对于其他树的数据结构，如红黑树、展树等，
它们在实践中是否得到了广泛的应用？如果有的话，举个例子。
与B树不同，B树的结构可以保留并保存在磁盘中，红黑和显示树不能做到这一点，它们只是内存结构，对吗？那么他们怎么能像B树那样受欢迎呢？
浏览 1提问于2011-09-06得票数 2
回答已采纳
2回答
红黑树平衡吗？
、、、
我正在研究红黑树，我正在读科门的“算法入门”一书。现在，我正在尝试创建数字1-10的红黑树，使用书中描述的伪代码-RB-插入-补丁(T，z)。这是截图
一切都很好，直到我把"6“号插入到树中。根据伪代码，我得到以下结果
正如你所看到的，所有的红黑树都满足了要求，但我很困惑，因为我知道红黑树应该在每一步上都保持平衡。
我可以手动执行“左旋转”程序与"2“和"4”，并改变颜色。在这种情况下，我将得到以下结果，这是适当平衡的
所以我的问题是：
有不平衡的树可以吗?还是我在插入节点时遗漏了什么？
浏览 8提问于2015-02-15得票数 6
回答已采纳
2回答
我读过许多关于红黑树的文章，其中O(log )运算所用的时间不太清楚，.I不清楚它是如何工作的，以及树映射是如何使用红黑树算法来平衡树的，而不是二叉树搜索树。
参考链接
有谁能用一个例子解释一下这个算法是如何工作的吗？
浏览 9提问于2015-08-03得票数 8
回答已采纳
2回答
堆还是红黑树？
、、、、
我愿意使用数据结构作为常量空间的溢出缓冲区。我希望有有效的插入，但最重要的是高效删除min元素。我考虑使用堆，因为我有O( log(n) )、find_min()和log(N)插入和删除。另一方面，我知道与红黑树相比，我不理解它的优势，因为它还有O(log(n))、insert和delete，以及O(1)查找min/max。以及排序输出的优点(我不关心这个)。
这个问题与：有关
既然我有std::map和boost：：堆这两种结构，为什么我更喜欢使用堆而不是红黑树呢？最后，使用红黑树，我还有O(log(n))搜索条目的时间，而堆的搜索时间是O(n)，这一点很重要，因为存在重复。
浏览 3提问于2013-07-17得票数 10
回答已采纳
1回答
Avl树与红黑树的比较
、、、、
我明天要考试，我的笔记上有3道题我听不懂。
1- #搜索>> #插入和#deletions=0，这是哪一棵树？(Avl或红黑树)(答案是Avl)
2- #insertions>0和#searches=#deletions=0，那是哪棵树？(Avl或红黑树)(答案是红黑)
3- #insertions=#deletions和#searches=0，那是哪棵树？(Avl或红黑树)(答案是红黑)
你能解释一下吗？谢谢你的帮助
浏览 3提问于2015-01-08得票数 1
回答已采纳
1回答
嗨，我以前对红黑树知之甚少，也许这是个愚蠢的问题。
下面是一棵4节点的树：
这是合法的红树吗？在我看来，它实际上违反了红黑树的规则：
每一个红色节点都有两个颜色为黑色的子节点。从根到树叶的每条路径都包含相同数目的黑色节点(“黑高”)。
如果不是，4节点的红黑看起来应该是什么样子？
谢谢
浏览 4提问于2021-02-19得票数 1
回答已采纳
3回答
我知道Dijkstra的算法实际上是使用斐波那契堆实现的。但是，它是否也可以使用红黑树实现，并且仍然具有O(m log n)的最坏情况下的运行时间？
浏览 2提问于2013-01-24得票数 3
回答已采纳
3回答
使用STL内部实现红黑树
、、、
我知道我的STL (随g++ 4.x.x一起提供)使用红黑树来实现诸如地图之类的容器。是否可以直接使用STL内部的红黑树。如果是这样的话，是怎么做的？如果不是，为什么不呢?为什么STL不暴露红黑树呢？
令人惊讶的是，我用谷歌找不到答案。
编辑:我正在研究使用红黑树作为插入时额外的分配器构造函数调用的解决方案。参见。我的STL使用红黑树来实现map。
浏览 3提问于2012-07-08得票数 12
回答已采纳
1回答
我对红黑树和2-3-4树都有基本的理解，以及它们是如何保持高度平衡的，以确保最坏的操作是O(n logn)。
但是，我无法理解的这篇文章
2-3-4树是红黑树的等距，这意味着它们是等价的数据结构，换句话说，每2-3-4树至少存在一棵具有相同数据元素的红-黑树。此外，对2-3-4树的插入和删除操作会导致节点扩展、分裂和合并，这与红黑树中的颜色翻转和旋转是等价的。
我看不出这些行动是如何等同的。这句话在维基百科上准确吗？如何才能看出这些操作是等价的呢？
浏览 1提问于2012-01-06得票数 6
2回答
我们知道堆和红黑树都有以下特性：
最坏的搜索成本是lgN；
最坏的情况下插入成本是lgN。
那么，既然红黑树的实现和操作很困难，我们为什么不直接用堆代替红黑树呢？我很困惑。
浏览 3提问于2013-05-14得票数 8
2回答
红黑树的缺点是什么？
、、、
从我所读到的关于红黑树的所有内容来看，它们似乎是存储数据的最好的数据结构。
我正在尝试建立一个数据库，我想知道，在红黑树实现方面，我应该在哪里更小心，我不应该做什么。
红黑真的那么完美吗？
浏览 1提问于2011-05-10得票数 2
1回答
，所以我有以下问题：
你有一组数字，S，你储存在一棵红黑树里.您正在尝试将minDiff添加到红黑树中，这给出了S中最接近的两个数字之间的绝对差异，例如，如果S= {1，18，23，62，79,100} minDiff将返回5(x-23-18)
( A)演示如何增强红黑树以有效支持此操作，同时保持O(lgn)用于插入、搜索和删除的运行时间。
( B)演示如何输出创建MinDiff的两个数字的值。对于上面的例子，您将输出23和18。
我的困惑：
我只停留在问题的开头部分，即补充什么内容。我可以想到简单而低效的解决方案，比如让每个节点保持其自身与其父节点之间的绝对差异。但是，似乎应该有一些优雅的解
浏览 0提问于2020-11-12得票数 0
回答已采纳
1回答
这是一棵AVL还是红黑树？
、、、、
我有一个简单的问题，主要是因为我的大脑放弃了我。这能被认为是一棵AVL树吗？这也能被认为是一棵红黑树吗？
我相信这不会是一棵AVL树，因为它看起来不平衡，但我不确定这是否正确。
我也不确定这是否是一棵红黑树同样的道理。
浏览 5提问于2020-11-19得票数 0
回答已采纳
具有n个内部节点的红黑树的高度最多为2×O(ln，n+ 1).换句话说，红黑树的高度最多是最优的两倍.
有人能直观地解释一下为什么会这样吗？我不是在找归纳证明(我可以在网上找到)。这只是一个直观的原因吗？我想不出一个例子，一个R树的高度最多为2* O(ln，n+ 1)。
浏览 0提问于2013-07-18得票数 2
1回答
据我所知，在红黑树中，当我插入一个新节点时，当我遇到一个黑色节点时，我需要反转颜色，即将父节点和它的两个子节点设置为黑色(从根节点除外)。
我在维基百科上看到了这张图片：
为什么8和17不是黑色的？
我还检入了一个，取自Lafore的"Data Structures and Algorithms in Java“；同样的，这些节点变黑了。
这棵红黑树有多个版本吗？
浏览 3提问于2013-03-24得票数 2
2回答
我知道最佳匹配算法必须遍历整个列表才能找到需要O(n)的最佳内存块，所以我在考虑使用红黑树将运行时间提高到O(logN)。是否会出现红黑树不适合最佳状态的情况？如果是这样的话，谁能给我举个例子？谢谢。
浏览 5提问于2020-07-10得票数 1
维基百科：
红黑树是一种自平衡二叉树，一种用于计算科学的数据结构，通常用于实现关联数组。
有人知道用redblack树实现关联数组的语言吗？
浏览 2提问于2010-09-11得票数 3
回答已采纳
3回答
我在几个地方读过它，avl树搜索速度更快，但不能理解。据我所知:红黑树的最大高度=2*对数(N+1)树的高度= 1.44*logo(N+1)
是不是因为AVL比较短？
浏览 0提问于2011-05-21得票数 10
3回答
CFS调度器基于最小虚拟时间选择下一个进程，为了有效地得到这个值，它使用红-黑树( rbtree )，使用rbtree，我们将得到最小O(h)，这里h是rbtree的高度。但是，使用最小堆只能在O(1)时间内得到最小虚拟时间进程.我只想知道为什么在CFS实现中不考虑min-堆，在内核级别上使用min-堆有什么困难吗？
浏览 14提问于2015-10-17得票数 11
回答已采纳
这是中在红黑树中插入节点时的情况4。
如所示，节点"U“似乎不是NIL，因为它有子节点。
但它是一棵红黑相间的树吗？
是图片错了还是我漏掉了什么？
浏览 1提问于2018-12-15得票数 1
我正在遵循的参考资料来学习算法。我不能弄清楚红黑树中的删除，任何帮助都是很好的。这本书谈到了按照2-3个树的方式对删除进行编码。我不能让correlation.thanks
浏览 1提问于2013-06-30得票数 1
1回答
例如，我知道2-3树和红黑树的概念和想法，但你能给我一些情况，他们中的一个比另一个更好吗？我应该问自己什么问题？
由于问题不仅仅是关于2-3树和红黑树，请随意给出其他自平衡树的示例，我将对它们进行研究。我只是想从一般的角度来问这个问题，以便其他想知道类似或相同问题的人可以很容易地用谷歌搜索。
浏览 16提问于2020-08-05得票数 0
回答已采纳
1回答
std::map::erase(iterator)的复杂性被摊销为O(1) (例如，参见 )。虽然标准库没有指定实现，但这实际上意味着红黑树所需的再平衡操作的数目被摊销为O(1)。事实上，维基百科上的红黑树条目
恢复红黑属性需要少量(O(log )或摊销O(1))的颜色变化(在实践中非常快速)和不超过三个树的旋转(两个用于插入)。
但似乎没有链接(而且我在其他地方找不到)。
由于旋转的次数是恒定的，摊销是在节点-根路径上所需的重复次数上进行的。虽然平衡树中的大多数节点都指向树的底部(因此平均路径是对数的)，但它显然是摊销的O(1)，这是令人惊讶和有趣的。如何证明摊销常数成本？
浏览 6提问于2016-03-17得票数 6
回答已采纳
我想知道一棵红色的黑色树是否应该至少有一个红色节点。此外，给定BST，如果我们可以将其转换为RBT，是否有独特的方法将此树转换为红黑树？
浏览 0提问于2013-03-23得票数 0
回答已采纳
我有一个问题要解释为什么这棵平衡的树不能是一棵红色的黑树，还想用一次旋转就把它转换成一棵红色的黑树：
为什么这个二叉树不能是一棵红黑树呢？
浏览 0提问于2018-11-14得票数 0
回答已采纳
3回答
我是在一次考试中被问到这个问题的，但我并不完全相信老师的回答，我想问你对此有何看法。
红黑树上的旋转.
保留所有节点的黑色高度。
保持有序订购。
上面的陈述是正确的：
A. (1)
B. (2)
C. (1)和(2)
D.非(1)或(2)。
老师声称旋转并不能保持黑色的高度，答案是B：它只保留顺序排序。然而，我坚信它保留了所有节点的黑色高度，答案是C，而不是B。
我是对的还是我的老师是对的？
浏览 3提问于2021-04-08得票数 0
1回答
在Linux内核中，为了存储进程的内存区域，Linux同时使用链表和红黑树。是一个函数，它通过红黑树定位vm_end字段大于传递地址的第一个内存区域。但是，我发现在find_vma()中没有对红黑树的保护(比如锁)。如果另一个线程同时调用函数来删除树上的某些元素，该怎么办？
浏览 0提问于2015-11-27得票数 5
云服务器
ICP备案
对象存储
腾讯会议
实时音视频
腾讯云开发者
