Open-sourcing the past

While studying at the University of Oregon, I worked as a teaching assistant in three different computer science courses. One of them was CIS 323 Data Structures Lab but this course was a bit special because it had its own course number and I was teaching it almost on my own.

It was quite a roller coaster ride1

Anyway, throughout the course, we implemented some classic and often used data structures and algorithms in various forms. In my opinion, the most notable data structure we implemented was a fairly new balanced tree data structure called the left-leaning red-black tree (LLRB), invented by Robert Sedgewick in 2008. Back in the beginning of 2010, I could not find any publicly available C++ implementation of the LLRB tree 2 which made it fun to use in class because it was very new. This means that there is a possibility that my implementation was the first-ever implementation of the LLRB tree in C++. It is a fun thought but it is not very significant, considering it is only a few lines of code, the delete operation was not implemented and it was never released. Until now.

I recently went through some old course material and found the code. So I emailed the University of Oregon and the course supervisor and with their permission, here is the code which I might expand with a few more data structures once I have looked through the material. I have refactored the code from the original but it still has the mark of a C++ beginner. It was fun going through it again though.