咨询BST中avgCompares()方法的平均比较含义

我来帮你把这个概念掰扯清楚，当初学这本《Algorithms》的时候我也纠结过这个点～

核心概念：随机搜索命中的平均比较次数 #

题目里提到的公式「树的内部路径长度除以大小再加1」，是从等概率搜索假设推导出来的：

• 首先，「随机搜索命中」的定义是：每次搜索的目标都是BST中已存在的节点，且每个节点被搜索到的概率完全相等（也就是每个节点的被搜概率是 1/N，N为树的总节点数）。
• 其次，每个节点的搜索比较次数等于它的深度+1：比如根节点深度为0（从根到自己的路径边数是0），找根节点只需要1次比较；根的子节点深度为1，找它需要2次比较（先比根，再比它自己），以此类推。
• 平均比较次数就是所有节点的比较次数的平均值：

  平均值 = (所有节点的比较次数之和) / N = (所有节点的深度之和 + N) / N = (内部路径长度 / N) + 1
  这里的「内部路径长度」就是所有节点到根节点的路径长度（边的数量）之和，刚好等于所有节点的深度之和。

两种实现思路的对应逻辑 #

结合题目里的两种实现方式，你能更直观理解这个指标的计算逻辑：

• 递归实现（线性时间，空间与树高成正比）：
  这种方式不需要额外存储节点字段，只通过递归遍历整棵树，累加所有节点的深度得到内部路径长度，再除以总节点数加1即可。递归时栈的深度等于当前遍历的树的高度，所以空间复杂度和树高成正比；每个节点仅遍历一次，时间为线性的O(N)。
• 带节点字段的实现（线性空间，查询常数时间）：
  这个思路和size()方法类似——给每个节点额外维护两个字段：一是该节点为根的子树的内部路径长度，二是子树的节点总数。在BST执行插入、删除等修改操作时，同步更新这些字段。这样每次查询平均比较次数时，直接用根节点的内部路径长度除以总节点数加1，一步就能得到结果，时间为O(1)；但因为每个节点都要存储额外字段，空间复杂度是O(N)的线性空间。

内容的提问来源于stack exchange，提问作者Shikhar