提问者:小点点

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


假设我们正在处理键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个答案

匿名用户

你在找一棵瘦树,对吗?这可以通过插入< code>[1...,2^(n 1)-2]以相反的顺序。

匿名用户

你不可能。红黑树保持自己的“浓密”,所以它会旋转以修复不平衡。上述红黑树最坏情况的长度仅限于两个元素,但这仍然不是“坏”情况;这是所期望的,因为lg(2)=1,并且你有一层超过根的两个元素。一旦添加第三个元素,就会得到:

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