最近,我正在尝试解决CLRS中的所有练习.但有一些我无法弄清楚.这是其中之一,来自CLRS练习12.4-2:
描述n个节点上的二叉搜索树,使得树中节点的平均深度为Θ(lg n),但树的高度为ω(lg n).给出n节点二分搜索树高度的渐近上界,其中节点的平均深度为Θ(lg n).
任何人都可以分享一些想法或参考来解决这个问题吗？谢谢.
algorithm binary-tree asymptotic-complexity clrs data-structures
algorithm ×1
asymptotic-complexity ×1
binary-tree ×1
clrs ×1
data-structures ×1