[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)$.
1
对于有 $N$ 个结点的二叉树, 设其左子树的结点个数是 $i$, 则右子树结点个数是 $N-i-1$. 于是
\[
D(N)=D(i)+D(N-i-1)+N-1.
\]
这里加上 $N-1$ 是因为左子树、右子树这 $N-1$ 个结点的深度在原来的树中要加深一.
对于二叉查找树, 由于子树的大小只依赖于第一个插入到树中的元素的相对的秩, 因此所有子树的大小都是等可能地出现. （这对于二叉树来说不成立.）
因此 $D(i)$ 和 $D(N-i-1)$ 的平均值 （仍记为 $D(i)$ 和 $D(N-i-1)$）都是
\[
\frac{1}{N}\sum_{j=0}^{N-1}D(j).
\]
于是
\[
D(N)=\frac{2}{N}\biggl[\sum_{j=0}^{N-1}D(j)\biggr]+N-1.
\]