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.


  1. The course used C++ so the students could get a feel for something else than Java. I could probably have used something else but I stuck to the syllabus from previous years. Unfortunately, I had never written a line of C++ code before, I had never designed an assignment before, I had never performed a lecture before and I had never spoken to an audience of 50 people before. It was scary as hell. I had bits and pieces of assignments from previous years but in the end, I had to change the syllabus slightly and write quite a bit of C++ from scratch.
  2. The reference implementation was written in Java

Leave a comment

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.