二叉搜索树的平均高度 [英] Average height of a binary search tree

问题描述

当添加1000个随机整数时，如何计算二叉搜索树的平均高度?平均高度是多少?

How do you compute the average height of a binary search tree when adding 1000 random ints? What is the average height?

推荐答案

您可以使用以下递归定义来计算二叉树的高度:

You can compute the height of a binary tree using this recursive definition:

height(empty) = 0
height(tree) = 1 + max(height(tree.left), height(tree.right))

一种以经验方式测量此类树的平均高度的方法是重复创建一棵空树，并向其中添加1000个随机项.使用上述功能测量每个试验的高度，并将其平均.

One way to empirically measure the average height of such a tree is to repeatedly create an empty tree and add 1000 random items to it. Measure the height of each trial using the above function, and average them.

我怀疑您的任务可能是为二叉树的平均高度找到一个公式.

I suspect your task is probably to find a formula for the average height of a binary tree.

这篇关于二叉搜索树的平均高度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！