二叉排序树等概论情况下的平均查找长度

在二叉排序树等概率情况下，节点的排列是随机的，假设树的深度为d，则总共有2^d-1个节点。平均查找长度ASL就是每个节点被查找的概率乘以节点的深度之和，再除以总节点数。在二叉排序树中，每个节点被查找的概率都是1/(2^d-1)，因此ASL=（1*1+2*2+...+d*(2^d-1)）/（2^d-1）。这个式子比较复杂，没有直接的通用公式。但是通过计算可以得到，当节点数n较大时，ASL约为1.39*log2(n+1)-1.08。