The Ultimate Tree
The Ultimate Tree is the fastest Tree data structure ever built. Trees are one of the most powerful data structures in Computer Science. They are fast. They allow you to have a well-structured, total ordered view of your data with fast retrieval (search), insertion and deletion. There are many different types of Trees, and when I say fast, what I mean is O(Log(n)), which IS fast. Check this out: As you can see, all sophisticated trees above have retrieval, insertion and deletion in O(Log(n)). The question then becomes: is it possible to come up with The Ultimate Tree , a Tree capable of search, insertion and deletion in constant time (O(1))? The claim in this post is that yes, there IS a way to do that. Here is how it will work: 1) First, no free lunch here! Such a massive speed up in search, insertion and deletion will require extra space, hence we’ll not be optimizing for space here, and will tolerate up to O(n)-space. Space is c...