1999年清华大学 · 二叉排序树 · 考研题

在分析二叉查找树性能时常加入失败结点,即外结点,从而形成扩充的二叉树。若设失败结点i所在层次为li,那么查找失败到达失败结点时所做的数据比较次数是多少?

答案

查找失败到达失败结点所做的数据比较次数,等于根结点到外结点的路径上内部结点的个数,即li-1。

笔记