红黑树的最坏情况黑色高度的插入顺序

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

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

B                   B
 \                 / \
  R       =>      R   R
   \
    R