问题

[Def] 内部路径长(internal path length)

一棵树的所有结点的深度之和称为内部路径长.

设 $D(N)$ 是具有 $N$ 个结点的某棵树 $T$ 的内部路径长. $D(1)=0$.

对于二叉查找树, 其平均内部路经长（仍记为 $D(N)$, 确切地应该记为 $E[D(N)]$）满足

\[
D(N)=\frac{2}{N}\biggl[\sum_{j=0}^{N-1}D(j)\biggr]+N-1.
\]

由此求出 $D(N)=O(N\log N)$.