这不是家庭作业，我正在学习数据结构课程，我们最近完成了树。下课时，我的教授展示了这张照片。
ConcreteBTree 是一种不会自平衡的二叉树。关于完成这些程序所需的时间，我有几个问题。
为什么将 100,000 个顺序元素插入到 ConcreteBTree 中比在其中插入随机元素需要更多的时间？我的直觉是，由于元素是连续的，因此插入 1,000,000 个随机元素所需的时间应该更少。
为什么带有随机元素的ConcreteBTree的insert()和find()时间如此接近？是因为两者具有相同的时间复杂度吗？我认为 insert 是 O(1) 而 find 是 O(n)
我真的很想了解这里发生了什么，任何解释将不胜感激。谢谢
将顺序项（1,2,3,4...）插入二叉树将导致它始终将节点添加到同一侧（例如左侧）。当您插入随机项目时，您将左右随机添加节点。
顺序添加将导致列表表现为普通链表（对于顺序项），因为新项将必须访问每个先前添加的项，这将采取 O(n) 步骤，随机添加时将需要 O(log N ) 平均步数。
Armin 回答了 Q1。
2.为什么带有随机元素的ConcreteBTree的insert()和find()的时间如此接近？是因为两者具有相同的时间复杂度吗？我认为 insert 是 O(1) 而 find 是 O(n)
insert并且find必须做同样的工作——他们通过你放在一起的任何奇怪的树来寻找最后一个节点，在这个节点下，值要么被链接，要么将是（并且将在的情况下insert），所以他们做同样的事情比较和节点遍历的次数，花费相似的时间。
在平衡树中插入随机元素是 O(log 2 N)。您将随机值插入到不自动重新平衡的树中会有点但不会显着更糟，因为某些分支最终会比其他分支长得多 - 您可能会得到某种分支长度的钟形曲线。 insert如果您已经知道要在其中完成插入的树中的节点（即通常需要上面的查找步骤），则只有 O(1)。 find如果必须访问树中的每个节点，则只有 O(n)，这仅适用于病态不平衡树，有效地形成链表，正如您已经被告知的那样，您可以通过插入预排序来生成元素。