Using the right data structure or algorithm for the situation is an important aspect of programming. In computer science literature, many data structures and algorithms have been researched and extensively documented. However, there is still no standard library in Ruby implementing useful structures and algorithms like Splay Trees, Red/Black Trees, tries, graphs, different sorting algorithms, etc. This project will create such a library with documentation on when to use a particular structure/algorithm. It will also come with a benchmark suite to compare performance in different situations.

By leveraging the flexibility of Ruby’s duck typing, the structures and algorithms can be used on all classes of objects as long as a few methods are defined, much like the Enumerable mix-in. The library will be written in Ruby so that it can be used by all the different Ruby implementations, but will also be implemented in C and Java for performance.

Possible data structures and algorithms:

-Trees (AVLTree, SplayTree, Red/Black Tree)
-Heaps
-Tries (Radix Tree, Suffix Tree)
-Graphs (Adjacency List, Kruskal’s Algorithm, Djikstra’s Algorithm)
-Sorting (Mergesort, Quicksort, Radix Sort, Insertion Sort)
-Searching (Knuth-Morris-Pratt, Breadth-first tree search, depth-first tree search)