The motivation

My current project includes a small maze game with a simple perspective (see screenshot). Each frame the entire screen is redrawn; first the ground tiles, then all sprites with height (trees, pick-up's, characters). Drawing the ground tiles is pretty straightforward. The sprites, however, have to be drawn in the correct order; sorted by their y-position. Since the sprites move around in the maze, their y-position will change and with it, their position in the drawing order.

Screenshot of the game by Three Little Witches

So for this game I needed a data structure with following properties:

• It can be traversed quickly (the drawing loop)
• It is sorted (need the drawing order)
• Elements in the sorted dataset can change value (y position of sprites can change)
  (Changing the sort value of an element in a sorted dataset can be accomplished by deleting the old value and inserting the new one)
• It can have duplicates (sprites can be at the same y position)

Choices

Google came up with a red-black tree, a balanced binary search tree that has quite fast insert and delete operations and is always sorted. Unfortunately, it doesn't allow duplicates and traversing the data in sorted order (done every frame) is fast but involves some calculations.

Combining the doubly linked list with the red-black tree results in a data structure that can have duplicates and has a fast and ordered traversal.

Doubly linked list

The doubly linked list is a basic data structure and plenty of information about it is available on the web. Because universities usually put their lecture slides online in PowerPoint format, a Google search for "site:edu filetype:ppt doubly linked list" results in excellent links to presentations about this data structure.

The individual nodes that make up the list have the following definition

struct DLLNode
{
  int       Key;

  DLLNode * Next;
  DLLNode * First;
};

Binary search tree

Binary search trees have been around for some time and you can find some great presentations for it with a Google.

The problem with a 'normal' binary search tree is imbalance. If we insert the numbers 9, 8, 7, 6, 5, 4, 3, 1 in that order the tree wouldn't look much like a tree. In fact, it looks and acts just as a doubly linked list does and its search and insert operation would be just as slow.

Red-black tree

To prevent this situation, the tree needs to stays balanced (look like a proper upside-down tree). Adelson-Velskii and Landis invented the first self-balancing tree in 1962 (AVL tree) and a red-black tree is much alike. Because the tree stays balanced, search and insert operations are guaranteed to be fast, no matter what order the data is inserted or deleted.

To make this self-balancing work, a red-black tree needs to do some housekeeping each time you insert or delete something from the tree. If the newly inserted or just deleted node upsets the balance, the tree needs to fix it.

Essentially, the red-black tree uses rotations to keep itself balanced. I found it quite confusing and I drew hundreds of little connected circles before it made some sense. It is all very neat though, so do a Google for "site:edu filetype:ppt red black tree".

The individual nodes that make up the tree have the following definition:

struct RBTreeNode
{
  int          Key;

  RBTreeNode * Left;
  RBTreeNode * Right;
  RBTreeNode * Parent;
  int          Color;
};

Red-black tree with a doubly linked list