二分搜索树密度？

Question

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

Answer 1

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