n 个不同键上随机填充的二叉搜索树的预期高度为 O(log(n))

Question

我正在为学校做一个项目，作业有我们：

在二叉搜索树上实现 Tree-Insert(T,z) 操作。
在二叉搜索树中重复插入n个随机选择的数字并收集高度h。
在同一图上绘制数量 h/lg(n) 与 n.

我有一个完整的程序，它输出 n 的值从 250-50K，我随机填充的 BST 的平均高度，以及 height 的值(n)/log₂(n). 如果需要，我可以提供代码，但程序的伪代码如下所示：

collectData()
for n = 250 to 10,000 by 250 // 250, 500, 750, …. 10,000
    sum_heightn = 0
    for j = 1 to 10 do //Take 10 measurements mj for j=1 to 10
        for i = 1 to n
           pick randomly a number p in the range [0,n]
           create a node z
           set z.key = p
           Tree-Insert(T,z)
        Measure the height hj of the tree
        Discard Tree
        sum_height += hj
collect Height(n)= sum_heightn/10 // Average height for n
Write in a file F the value n and Height(n)/log_2(n).

我正在努力理解计算 h(n)/log₂(n) 时得到的值是什么意思。谁能帮忙解释一下？谢谢

Answer 1

一棵高度为 h 的二叉树最多可以有 2^h - 1 个节点。

上面这棵树的高度是2，这棵树最多可以有的节点数是2^2 - 1 = 3.

log_2(n) 对于大 n 表示（大约）完全填充树的高度。同样，您可以渐进地说，具有 n 个节点的平衡树的高度将为 O(log_2(n)).

height / log_2(n) 只是一个可以达到

的比率

最大 n / log_2(n) 当树倾斜时（当插入顺序增加或减少时）。
当树完全平衡并且树的高度变为 log_2(n).

1

您可以通过以下方式查看此比率：它描述了给定树的偏斜程度。如果此比率接近 n/log_2(n)，则树非常偏斜，如果比率足够接近 1，则树 much ] 平衡。

n 个不同键上随机填充的二叉搜索树的预期高度为 O(log(n))

The expected height of a randomly filled binary search tree on n distinct keys is O(log(n))

computer-science

binary-search-tree