为什么在有N个结点且为完全二叉树的二叉搜索树中查找一个键值，其平均比较次数的数量级为

log2(N)？

对于完全二叉树的二叉搜索树，每个结点最多有两个子结点，且左子树中的所有键值小于该结点的键值，右子树中的所有键值大于该结点的键值。因此，在查找某个键值时，我们可以从根结点开始，每次比较当前结点的键值和要查找的键值，然后继续向左子树或右子树搜索，直到找到该键值或搜索到叶子结点为止。

由于完全二叉树的深度为log2(N)，因此在最坏情况下，需要比较log2(N)次才能找到要查找的键值。但是，在平均情况下，由于二叉搜索树的键值是随机分布的，每个结点的左右子树的大小也是随机的，因此每次比较的次数并不是固定的。根据概率论的知识，可以证明在平均情况下，每次比较的次数的期望值为log2(N)。因此，平均比较次数的数量级为log2(N)。