可以说我们正在处理1-15键。为了获得常规BST的最坏情况的性能,您可以按如下所示的升序或降序插入 key :

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的最坏情况一样吗?是否有特定的模式会导致最坏的情况?

最佳答案

您正在寻找一棵瘦树,对吗?这可以通过以相反的顺序插入[1 ... , 2^(n+1)-2]来产生。

10-07 19:16
查看更多