algorithm - BST 中平均比较的含义

Question

我对 Sedgewick 和 Wayne 合着的“算法”第 4 版中的以下问题感到困惑。

向 BST 添加一个计算平均数的递归方法 avgCompares()给定 BST 中随机搜索命中所需的比较次数(内部路径树的长度除以它的大小，再加一)。开发两个实现:递归方法(采用与高度成比例的线性时间和空间)，以及像 size() 这样的方法，它向树中的每个节点添加一个字段(并采用线性空间和每个查询的固定时间)。

我不清楚作者在这个问题中的平均比较是什么意思。

注意:我不需要编码部分的帮助。

Answer 1

要获得 BST 的平均比较次数，您必须对找到每个节点的比较次数求和，因为每个节点的搜索长度等于该节点的内部路径 + 1。最后得到平均值您必须将总和除以节点总数。所以它只是一个节点搜索的平均长度。