c++ - 为什么在树中插入顺序元素比在树中插入随机元素需要更多时间？

Question

这不是作业我正在上数据结构课，我们最近完成了树。下课时，我的教授展示了这张图片。

ConcreteBTree 是一种不自平衡的二叉树。我对完成这些程序所花费的时间有一些疑问。

1. 为什么将 100,000 个顺序元素插入 ConcreteBTree 所花费的时间比将随机元素插入其中所花费的时间多得多？我的直觉是，由于元素是连续的，因此插入 1,000,000 个随机元素所需的时间应该更少。

2. 为什么随机元素的ConcreteBTree的insert()和find()的时间相差这么近？是因为两者具有相同的时间复杂度吗？我以为 insert 是 O(1) 而 find 是 O(n)

我真的很想了解这里发生了什么，任何解释将不胜感激。谢谢

Answer 1

将顺序项(1,2,3,4...)插入二叉树将导致它始终将节点添加到同一侧(例如左侧)。当您插入随机项目时，您将在左右随机添加节点。

顺序添加将导致列表表现为普通链表(对于顺序项)，因为新项将必须访问每个先前添加的项，这将花费 O(n) 步，而随机添加将花费 O ( log N) 平均步数。