红黑树最坏情况下黑色高度的插入顺序
假设我们正在处理键1-15。为了获得常规BST的最差性能，您应该按如下方式按升序或降序插入键:
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15
那么BST本质上将成为一个链表。
对于BST的最佳情况，您可以按以下顺序插入键，它们的排列方式是，插入的下一个键是要插入的总范围的一半，因此第一个键是15/2=8，然后是8/2=4等。。。
8, 4, 12, 2, 6, 10, 14, 1, 3, 5, 7, 9, 11, 13, 15
那么BST将是一棵高度为3的平衡良好的树。
红黑树的最佳情况也可以用BST的最佳情况来构造。但是我们如何构建一棵红黑树的最坏情况呢？这与BST的最差情况相同吗？有没有一个特定的模式会导致最坏的情况？
共有2个答案
你不可能。红黑树保持自己的“浓密”，所以它会旋转以修复不平衡。上述红黑树最坏情况的长度仅限于两个元素，但这仍然不是“坏”情况；这是所期望的，因为lg（2）＝1，并且你有一层超过根的两个元素。一旦添加第三个元素，就会得到：
B B
\ / \
R => R R
\
R
你在找一棵瘦树，对吗？这可以通过插入< code>[1...，2^(n 1)-2]以相反的顺序。
-
红黑树与AVL的比较： AVL是严格平衡树，因此在增加或者删除节点的时候，根据不同情况，旋转的次数比红黑树要多； 红黑是用非严格的平衡来换取增删节点时候旋转次数的降低； 所以简单说，如果你的应用中，搜索的次数远远大于插入和删除，那么选择AVL，如果搜索，插入删除次数几乎差不多，应该选择RB。 红黑树详解: https://xieguanglei.github.io/blog/post/red-bl
-
本文向大家介绍请介绍一下红黑树？相关面试题，主要包含被问及请介绍一下红黑树？时的应答技巧和注意事项，需要的朋友参考一下 参考回答： 红黑树（Red Black Tree）是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。红黑树和AVL树类似，都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能。 它虽然是复杂的，但它的最坏情况运行时
-
二叉查找树 由于红黑树本质上就是一棵二叉查找树，所以在了解红黑树之前，咱们先来看下二叉查找树。 二叉查找树（Binary Search Tree），也称有序二叉树（ordered binary tree）,排序二叉树（sorted binary tree），是指一棵空树或者具有下列性质的二叉树： 若任意结点的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若任意结点的右子树不空，则右子树
-
本文向大家介绍图解红黑树及Java进行红黑二叉树遍历的方法，包括了图解红黑树及Java进行红黑二叉树遍历的方法的使用技巧和注意事项，需要的朋友参考一下 红黑树 红黑树是一种数据结构与算法课堂上常常提到但又不会细讲的树，也是技术面试中经常被问到的树，然而无论是书上还是网上的资料，通常都比较刻板难以理解，能不能一种比较直观的方式来理解红黑树呢？本文将以图形的方式来解释红黑树的插入与删除操作。 对树结构
-
本文向大家介绍请问红黑树了解吗？相关面试题，主要包含被问及请问红黑树了解吗？时的应答技巧和注意事项，需要的朋友参考一下 参考回答： 参考博客https://blog.csdn.net/tanrui519521/article/details/80980135
-
本文向大家介绍红黑树的插入详解及Javascript实现方法示例，包括了红黑树的插入详解及Javascript实现方法示例的使用技巧和注意事项，需要的朋友参考一下 红黑树的性质 一棵满足以下性质的二叉搜索树是一棵红黑树 每个结点或是黑色或是红色。 根结点是黑色的。 每个叶结点(NIL)是黑色的。 如果一个结点是红色的，则它的两个子结点都是黑色的。 对每个结点，从该结点到其所有后代叶结点的简单路径上
-
由于splay树是一种不平衡的二元搜索树（brilliant.org/wiki/splay树），它不能保证最大高度为O（log（n））。因此，我认为它不能保证最坏情况下的搜索时间为O（log（n））。 但根据bigocheatsheet。通用域名格式： Splay树的最坏情况搜索时间为O（log（n））？？？
-
我知道Dijkstra的算法实际上是使用斐波那契堆实现的。但是，它也可以使用红色的黑树来实现，并且仍然具有O（m log n）的最坏情况运行时间吗？