This is the archived website of SI 486H from the Spring 2016 semester. Feel free to browse around; you may also find more recent offerings at my teaching page.

Problem 64

Randomized search tree vs language built-in

Due: March 8
Points: 4

Implement a randomly-structured binary search tree that we talked about in class, either the rBST or a treap. You don't have to implement complete functionality, but you should have at least a way of inserting into the tree and performing searches. It's OK with me if the keys for your tree are just integers.

You should use C++, Java, or Python, and do this implementation "the right way" for your language. By that I mostly mean, you should write an actual class for your rBST or treap type.

Finally, make a main method that compares your implementation to the built-in balanced search tree in your programming language. In Java this is java.util.TreeMap; in C++ it's the map class in the STL. Actually you could do java.util.TreeSet or C++'s set class as well; they're the same. In Python it's a little bit trickier since the usual dictionary type is actually a hashtable, but you can get it with the OrderedDict class in the collections module.

For whatever your chosen language and standard tree representation is, your main method should do the following: * Take an integer \(n\) as a command-line argument * Start a timer. * Insert the integers \(1\) up to \(n\), in that order, into the language's built-in balanced search tree. * Stop the timer, and report the time for the language's built-in data structure. * Start a new timer * Insert the same integers \(1\) up to \(n\), in that order, into YOUR randomized search tree. * Stop the timer, and report the running time for YOUR data structure.

If you need help on the timers or anything else for this, of course don't hesitate to ask Dr. Roche about it!

Submit your program according to the instructions on the submit page.