binary-search-tree - 红黑树最坏情况黑色高度的插入顺序

Question

假设我们正在处理键 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 的最坏情况相同吗？是否有一种特定的模式会产生最坏的情况？

Answer 1

你在找一棵瘦树，对吧？这可以通过插入 [1 ... , 2^(n+1)-2] 产生以相反的顺序。