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

Question

这不是家庭作业我正在上一个数据结构课,我们最近完成了树.课程结束时,我的教授展示了这张照片.

ConcreteBTree是一个不自平衡的二叉树.关于完成这些程序所花费的时间,我有几个问题.

1. 为什么在ConcreteBTree中插入100,000个连续元素所需的时间比插入随机元素要多得多？我的直觉是,因为元素是连续的,所以它应该花费比插入1,000,000个随机元素所花费的时间更少的时间.

2. 为什么ConcreteBTree的insert()和find()的时间与随机元素如此接近？是因为两者具有相同的时间复杂度吗？我认为插入是O(1),发现是O(n)

我真的很想了解这里发生了什么,任何解释都会非常感激.谢谢

Answer 1

将顺序项(1,2,3,4 ...)插入二叉树将使其始终将节点添加到同一侧(例如,左侧).插入随机项时,将随机左右添加节点.

顺序添加将导致列表表现为普通链表(对于顺序项),因为新项必须访问每个先前添加的项,并且将花费O(n)步,当随机添加时将需要O(log N )平均步数.