二叉排序树的不成功的平均查找长度怎么求?

2025-12-14 06:35:48

推荐回答（1个）

回答1：

按二叉树的公式求。

1.就你的BST，结果如下：15的左右子树都为空，也就是左右子树都是外结点，失败时需要比较62、30、15一共3次。

2.48的左右子树都为空，也就是左右子树都是外结点，失败时需要比较62、30、15、48一共4次。

3.56的右子树为空，也就是右子树是外结点，失败时需要比较62、30、56一共3次。

4.74的左右子树都为空，也就是左右子树都是外结点，失败时需要比较62、74一共2次。

5.因此外结点总数为2 *3 + 1 = 7 （其实这个数量一定是关键字个数加1）。

6.所以ASL = (2 * 3 + 2 * 4 + 1 * 3 + 2 * 2) / 7 = 21 / 7 = 3。