可以说我们正在处理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]
来产生。