binary-search-tree - 二叉搜索树密度？

Question

我正在做一个处理二叉搜索树的家庭作业，我遇到了一个我不太明白的问题。该问题询问密度如何影响搜索二叉树所需的时间。我了解二叉搜索树和大 O 表示法，但我们以前从未处理过密度。

Answer 1

二叉搜索树的密度可以定义为累积到一个级别的节点数。一棵完美的二叉树将具有最高的密度。所以这个问题基本上是问你每个级别的节点数量如何影响树中的搜索时间。如果不清楚，请告诉我。