3.2.7

3.2.7 #

解答 #

平均查找次数 = 树所有结点的深度之和 / 结点个数 + 1。

只要能够获得深度和,就能构造出如下用于计算平均查找次数的方法:

public int AverageCompares()
{
    return DepthSum(_root) / Size() + 1;
}

二叉树的深度之和 = 左子树的深度和 + 右子树的深度和 + 左子树的结点个数 + 右子树的结点个数 (加上根结点会使左右子树所有结点的深度+1)

于是我们可以获得如下递归方法,用于计算一棵树的深度和:

private int DepthSum(Node x)
{
    if (x == null)
        return 0;
    return DepthSum(x.Left) + DepthSum(x.Right) + x.Size - 1;
}

也可以在结点中直接添加一个 DepthSum 属性,用于记录当前结点的深度和。

需要在每次插入新结点时重新计算查找路径上所有结点的 DepthSum

private Node Put(Node x, TKey key, TValue value, int depth)
{
    if (x == null)
        return new Node(key, value, 1, depth);
    var cmp = key.CompareTo(x.Key);
    if (cmp < 0)
        x.Left = Put(x.Left, key, value, depth + 1);
    else if (cmp > 0)
        x.Right = Put(x.Right, key, value, depth + 1);
    else
        x.Value = value;
    x.Size = 1 + Size(x.Left) + Size(x.Right);
    x.DepthSum = depth;
    if (x.Left != null)
        x.DepthSum += x.Left.DepthSum;
    if (x.Right != null)
        x.DepthSum += x.Right.DepthSum;
    return x;
}

在插入结点时需要传入一个参数以记录当前深度,新插入结点的默认深度和就是当前深度。