Mih*_*lin 2 algorithm complexity-theory binary-search-tree
我是计算机科学大学的新生,所以请给我一个可以理解的理由.
我有一个由高度平衡的二叉树,有635个节点.在最坏的情况下会发生什么比较？为什么？
这是思考这个问题的一种方法.每次在二叉搜索树中进行比较时,都会发生以下情况之一:
这里的关键观察是,在每一步之后,你要么终止(yay!),要么在树的下方下降.在每个点上,您进行一次比较.由于你不能永远下降,你只能做很多比较 - 具体来说,如果树有高度h,你可以做的最大比较数是h + 1,如果你每个级别进行一次比较就会发生这种情况. .
在你的问题中,你被赋予了一个635个节点的平衡二叉搜索树.在这种情况下,"平衡"意味着什么并不是100%明确,因为有许多不同的方法来确定树是否平衡并且它们都导致不同的树高.我将假设您有一个完整的二叉搜索树,其中除了最后一个之外的所有级别都被填充.
这一点很重要的原因是,如果你有一个高度为h的完整二进制搜索树,它最多可以有2 h + 1 - 1个节点.如果我们尝试根据节点数求解树的高度,我们得到:
n = 2 小时+ 1 - 1
n + 1 = 2 小时+ 1
lg(n + 1)= h + 1
lg(n + 1) - 1 = h
因此,如果您有节点数n,则可以确定包含n个节点的完整二叉搜索树的最小高度.在你的情况下,n = 635,所以我们得到
lg(635 + 1) - 1 = h
lg(636) - 1 = h
9.312882955 - 1 = h
8.312882955 = h
因此,树的高度为8.312882955.当然,树木不能具有分数高度,因此我们可以采取天花板来发现树的高度为9.由于最大比较数为h + 1,因此在进行时最多进行10次比较查找.
希望这可以帮助!