https://i.imgur.com/bKHQI7V.jpg
请问一下这一题
为什么Total cost is dominated by leaves?
那内部节点的overhead不用一起考虑吗

要阿 你画个递回树 把东西加一加看看前n-1层的数量跟第n层的树叶数是一样的等级就画个满满的树应该能轻易看的出来然后树叶之前的都是O(1) 树叶则是O(M)不要太严谨的话这样想一下比较容易如果有L个树叶那内部节点有L-1个(满的树内部节点都是O(1) 而树叶是O(M) 就只是这样而已@@豁然想到我讨论的是二元树不过这个递回是degree 8的不过我相信没有差就是了degree越大前n-1层的数量和跟第n层的只会差更大

感谢T大的详细解说!!大概了解了!