算法导论18.2-4

作者：知新_RL | 2024-04-07 01:15:02

踩

算法导论18.2-4

                    
                    问题描述 
 假设关键字{1,2,…,n}被插入一棵最小度数为2的空B树中，那么最终的B树有多少个结点？
问题求解 
 把关键字{1,2,…,11}一次插入B树中的变化如下所示： 
  
 可以发现，由于每次插入的树都比前面的大，因此新关键字永远是放到了最右边的结点中。除了最右边一直往下的路径上的结点（记为R）中的关键字数有可能大于1外，其他所有结点的关键字数量都是1.当所有的R结点都有三个关键字时，有最少的节点数。此时n=2h+1−1+2(h+1)n=2h+1−1+2(h+1)，其中hh是B树的高度，结点数是2h+1−12h+1−1。而2h+1−1=n−2(h+1)2h+1−1=n−2(h+1)，其中h=θ(lgn)h=θ(lgn)，因此节点数为θ(n)θ(n)。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/知新_RL/article/detail/375479