After reading about splay trees here: http://en.wikipedia.org/wiki/Splay_tree, I decided to implement one to get a better sense of them. My splay tree class in ruby effectively implements an Integer indexed Array externally but internally it stores the values in a linked structure. The tree implementation itself is in the the tree.rb. Since I really wanted to see the structure of these trees, I made a script that runs a few random operations on a tree taking graphviz "snapshots" of the structure throughout the process then compiles the resulting images into a simple JQuery app. The script can be run at the command line with:

It will produce an out.html file which can be view in any web browser.

In class we mentioned the Dictionary of Algorithms and Data Structures .

http://cs.marlboro.edu/ courses/ spring2012/jims_tutorials/ sam/ Splay_Trees
last modified Wednesday March 28 2012 10:09 am EDT

name last modified size

---

display.rb Mar 28 2012 9:16 am 2.05kB sample_run/ Mar 28 2012 9:51 am - splayTest.rb Mar 28 2012 9:16 am 578B tree.rb Mar 28 2012 9:16 am 6.62kB