什么时候选择RB树、B-Tree或AVL树?
作为程序员，我什么时候应该考虑使用 RB 树、B 树或 AVL 树?在决定选择之前需要考虑哪些关键点? 有人可以为每个树结构解释一个场景，为什么会参考关键点选择它而不是其他树结构吗? 解决方案 加点盐: 当您管理超过数千个项目并从磁盘或某些慢速存储介质对它们进行分页时，请使用 B 树. RB 树，当您在树上进行相当频繁的插入、删除和检索时. 当您的插入和删除相对于您
..
red-black-tree相关内容
红黑树和AVL树的区别
谁能解释一下这两种数据结构之间的主要区别是什么?我一直试图在网上找到一个突出差异/相似之处的来源，但我没有找到任何信息量太大的信息.在什么情况下，一种会比另一种更受欢迎?什么实际情况使一个比另一个“更好"使用? 解决方案 AVL 树比红黑树保持更严格的平衡.在 AVL 树中从根到最深叶的路径最多为 ~1.44 lg(n+2)，而在红黑树中最多为 ~2 lg(n+1). 因此，在 AV
..
红黑树再平衡
我想在我的树中插入 7 个项目 -3、-2、-1、0、1、2 和 3.当我按以下顺序插入时，我得到了高度为 3 的均衡树，无需进行旋转:0，-2, 2, -1, 1, -3, 3. 但是当我按升序插入所有项目时，根节点的右侧部分会重新平衡，但根节点的左侧部分不会.我见过的所有重新平衡算法都是从插入的节点重新平衡到根节点，然后停止.他们不应该继续到根节点的另一部分吗?如果我按升序(例如 0 到 10
..
树图如何使用红黑树算法
我已经阅读了很多关于红黑树的文章，其中操作需要 O(log n) 时间.我不太清楚它是如何工作的，以及与二分搜索相比，树图实际上如何使用红黑树算法来平衡树树. 参考链接https://www.topcoder.com/community/data-science/data-science-tutorials/an-introduction-to-binary-search-and-red-b
..
使用STL内部实现的红黑树
我知道我的 STL(随 g++ 4.x.x 一起提供)使用红黑树来实现诸如地图之类的容器.是否可以直接使用STL内部的红黑树.如果是这样，如何?如果没有，为什么不 - 为什么 STL 不公开红黑树? 令人惊讶的是，我无法使用谷歌找到答案. 编辑:我正在研究使用红黑树作为插入时额外分配器构造函数调用的解决方案.请参阅这个问题.我的 STL 使用红黑树来实现地图. 解决方案 实际上
..
一棵全黑节点的树是一棵红黑树吗?
似乎Wiki上的定义不准确: http://en.wikipedia.org/wiki/Red-black_tree#Properties 一棵带有所有黑色节点的树是一棵红黑树吗? 更新 由于rbtree的定义不是很严格，我们如何决定将黑色节点的子节点打印为红色还是黑色? 解决方案 红黑树只是
..
警告C4715:并非所有控制路径都返回值c ++
我制作了两个函数，一个在红黑树中查找并返回最小键，另一个函数以该节点的键作为输入返回指向特定节点的指针.最高键和最低键.程序停止运行，并发出C4716警告.关键是int array [] = {50，26，45，34，23，78，84，93，14，16，100，57，62}; int Tree :: findsmallest(){返回findsmallestprivate(root);}int
..
deleteMin左倾斜红黑树需要更多说明
我正在阅读Robert Sedgewick编写的算法第4版中的“左斜红黑树".我花了几天的时间来尝试理解deleteMin，以此作为对delete的热身，这是我最后一个关于deleteMin的问题. 公共无效的deleteMin(){根= deleteMin(根);root.color =黑色;}私有节点deleteMin(节点h){如果(h.left == null)返回null;if(！is
..
红黑树:以log(n)时间分割/连接
根据罗恩·温(Ron Wein)，您能够在O(log(n))时间内对红黑树进行拆分和串联.请参阅他的文章:有效实施红黑树具有拆分和分类操作 但是我仍然不相信split的运行时间确实是正确的. 这个想法是split使用最坏情况的log(n)串联.这些连接的速度很快，因为我们可以通过记住上一个连接的p来找到p的节点. 问题在于，级联会启动修正(平衡)算法，据我所知，该算法需要O(lo
..
红黑树中的前哨节点的好处?
我创建了一个双向链接列表，并且前哨节点的好处很明显-在列表边界没有空检查或特殊情况. 现在我正在写一棵红黑树，试图弄清楚这种概念是否有好处. 我的实现基于 任何人都可以详细说明前哨节点在红黑树中的用处吗? 解决方案 红黑树实现几乎总是对所有叶子使用一个黑哨兵. 当您可以检查颜色而无需先检查null时，它将节省大量的null检查. 当然，这在使用父指针的实现中不起作
..
高度为h的红黑树中最小节点数的公式是什么?
我已阅读到log是(n + 1)
..
哈希表v自平衡搜索树
我很想知道与使用哈希表相比，使用自平衡树技术存储项目可能会超出什么原因? 我看到哈希表不能保持插入顺序，但是我总是可以在顶部使用链表来存储插入顺序. 我看到对于较小的值，散列函数会增加成本，但是我总是可以将散列函数与键一起保存，以加快查找速度. 我知道哈希表比红黑树的直接实现更难实现，但是在实际实现中，人们不愿意为此加倍努力吗? 我看到使用哈希表发生冲突是很正常的，但是使用
..
TreeMap的时间复杂度；操作:get()和subMap()
基于此帖子， TreeMap操作的时间复杂度-subMap，headMap，tailMap subMap()本身是O(1)，而O(n)来自迭代子图. 那么，为什么还要使用get(key)? 我们可以改用subMap(key，true，key，true) 是O(1)，并且迭代此子映射也是O(1). 比get(key)更快，它是O(log(n)).这里出了点问题...
..
是否有任何stl :: set实现都不使用红黑树？
有没有人看到过STL的实现，其中stl :: set不是作为红黑树实现的？ 原因我想问的是，在我的实验中，B-2B树的表现优于stl :: set（以及其他红黑树实现），其结果取决于B的值，为2到4倍。我很好奇是否存在引人注目的在出现更快的数据结构时使用红黑树的原因。 解决方案 Google的一些人实际上建立了一个基于B树的C ++实现标准库容器。它们似乎比标准二叉树实现要好得多。
..
JavaScript中是否有类似mulitiSet的内容?
我知道JavaScript现在具有设置，但是我想知道是否有什么东西可以实现 multiSet 的功能，或者我是否真的需要一些具有multiset功能的框架. 还是我必须自己编写代码才能进行红黑树的研究? 解决方案 没有内置的多集结构，但是 助记符→ TSTL → 在此问题中随时添加您喜欢的库.
..
多次使用相同键的红黑树:将集合存储在节点中还是将它们存储为多个节点?
显然，您可以执行任何一种操作，但是前者更常见. 您为什么选择后者?它如何工作? 我读了这篇文章: http://www.drdobbs.com/cpp/stls-red-black-trees/184410531 ;这让我认为他们做到了.它说: insert_always是一个状态变量，它告诉rb_tree是否允许使用同一键值的多个实例.此变量由构造函数设置，STL使用它来区分s
..
红黑树平衡了吗
我正在研究红黑树，正在阅读Cormen的“算法简介”这本书。现在，我尝试使用书中描述的伪代码RB-INSERT-FIXUP（T，z）创建数字1-10的红黑树。这是屏幕快照 一切都很好，直到我在树中插入数字“ 6”。根据伪代码，我得到以下结果 我可以手动执行“ 2”和“ 4”的“左旋转”过程并更改颜色。在那种情况下，我将得到以下结果，该结果是适当平衡的 所以我的问题是： 是不
..
在线性时间内从排序数组构建红黑树
我知道如何用n个插入来构建它（每个插入具有O（log（n））效率） （n * log（n））总体 ，我也知道还可以使用线性时间从排序数组构建2-3-4树。 谁能提供有关红黑版本的简单说明？ 解决方案 无论您要构建哪种BST。算法将是相同的。只需构建平衡的二叉树。 将中间元素放置到当前位置 放置[开始; 将元素（居中；结束）放置在右侧子树中。 这是O（N）算法。可以证明
..
是否可以在不删除和插入的情况下更新红黑树中的节点密钥？
通常，通过移除然后重新插入节点来对红黑树中的密钥进行更改。 是否可以执行密钥更新 解决方案 使用[搜索，如果需要+ ]删除+插入 1-删除键 O（log n） 2-插入新节点使用新键 O（log n） 即使您首先搜索键，它也是 O（log n）。 请参见此页面有关RBT的更多详细信息。
..
红黑树 - 如何找到节点的父节点？
在红黑树中，旋转时，您需要知道谁是特定节点的父节点。 但是，节点只能引用右子或左子。 我想给一个节点实例变量“parent”但是因为这个原因我不认为这样做是值得的，而且它也太复杂了每次轮换更改父引用。 public class Node { private left; 私权; private isRed; 私人父母; //我认为这不是个好主意 } 所以，
..