7

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

4

2 回答 2

2

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

于 2013-08-02T18:51:01.580 回答
0

你将无法做到。红黑树保持自己“浓密”，因此它会旋转以修复不平衡。红黑树的上述最坏情况的长度仅限于两个元素，但这仍然不是“坏”情况；这是预期的，因为 lg(2) = 1，并且您在根之后有 1 层，其中包含两个元素。添加第三个元素后，您将得到以下信息：

B                   B
 \                 / \
  R       =>      R   R
   \
    R
于 2013-05-16T21:27:56.777 回答