Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Why does inserting sequential elements in a tree require more time than inserting random elements into a tree?

Tags:

This is not homework I'm taking a data structures class and we recently finished trees. At the end of class, my professor showed this image. Tree Times

ConcreteBTree is a binary tree that doesnt self balance. I have a few questions about the times it took to complete these procedures.

  1. Why does it take so much more time to insert 100,000 sequential elements into ConcreteBTree than it takes to insert random elements into it? My intuition would be that since elements are sequential, it should take less time than it takes to insert 1,000,000 random elements.

  2. Why are the times of insert() and find() of ConcreteBTree with random elements so close together? Is it because both have the same time complexity? I thought insert was O(1) and find was O(n)

I'd really like to understand what is going on here, any explanation would be greatly appreciated. Thanks