3.2.40

上次更新:2019-12-23
发现了题解错误/代码缺陷/排版问题?请点这里:如何:提交反馈

解答

书中的结论是 1986 年 L. Devroye 给出的,原式为 $H_n \rightarrow c\log(n)$。

其中 $c$ 是方程 $c\log \frac{2e}{c}=1$ 的最大解,约为 $4.31107$。

2002 年 Michael Drmota 给出了一个跟精确的公式:$\mathrm{E}(H_n)=c\log n-\frac{3c}{2(c-1)}\log \log n + O(1)$。

测试结果如下,误差基本稳定在一个常数。

代码

static void Main(string[] args)
{
    var n = 10000;
    var trials = 100;

    for (var i = 0; i < 3; i++)
    {
        var items = new int[n];

        for (var j = 0; j < n; j++)
        {
            items[j] = j;
        }

        var aveHeight = 0d;
        for (var j = 0; j < trials; j++)
        {
            var bst = new BST<int, int>();
            Shuffle(items);
            foreach (var item in items)
            {
                bst.Put(item, item);
            }

            aveHeight += bst.Height();
        }

        aveHeight /= trials;
        var c = 4.31107d;
        var expectHeightLuc = c * Math.Log(n);
        var expectHeightMichael = c * Math.Log(n) - (3 * c / (2 * (c - 1))) * Math.Log(Math.Log(n));
        Console.WriteLine("n:" + n);
        Console.WriteLine("Actual Height:" + aveHeight);
        Console.WriteLine("Devroye: " + expectHeightLuc + "\tDiff: " + (float)(expectHeightLuc - aveHeight));
        Console.WriteLine("Michael: " + expectHeightMichael + "\tDiff: " + (float)(expectHeightMichael - aveHeight));

        n *= 10;
    }
}

static void Shuffle<T>(T[] a)
{
    var random = new Random();
    for (var i = 0; i < a.Length; i++)
    {
        var r = i + random.Next(a.Length - i);
        var temp = a[i];
        a[i] = a[r];
        a[r] = temp;
    }
}

另请参阅

A note on the height of binary search tree

Note The Variance of the height of binary search trees00006-8)

BinarySearchTree 库

上一题 下一题