这不是作业我正在上数据结构课,我们最近完成了树。下课时,我的教授展示了这张图片。
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) 平均步数。
关于c++ - 为什么在树中插入顺序元素比在树中插入随机元素需要更多时间?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/17038901/