你说的是C(k)那个递归式吗?如果是的话请看下面的一张图片
我们将(a)那一层想象成第k层,下面的(b)看作是k-1层。我们把第k层删掉,那么第k-1层就变成了顶层。
k-1层有两个分支,一左一右。你应该不难看出,顶层的查找长度(也就是一次查找成功的查找长度)必然是2。
那么对于左面的k-1层来说它的顶层是3,右面的顶层是4。稍加观察你会发现左面的k-1层的所有元素的查找长度都会相对于以k-1层为顶层时的查找长度多1。同样右面的k-1层的所有元素查找长度会相对于以k-1层为顶层时的查找长度多2。所以C(k)中需要把这些长度补上,然后在加上第k层的查找长度2即为C(k).