Red-black tree with a doubly linked list

(red lines show the doubly linked list connections)

When the doubly linked list is combined with the red-black tree the new node definition looks like this:

struct CombinedNode
{
  int            Key;
 
  CombinedNode * Left;
  CombinedNode * Right;
  CombinedNode * Parent;
  int            Color;

  CombinedNode * Next;
  CombinedNode * Prev;
};

Every node is linked in both the tree (Left, Right, Parent) and in the list (Next, Prev). This results in two traversal methods through the data; using the tree links (slower) or the list links (faster). The tree traversal can be used to traverse only the unique values and comes in use when inserting a new node in the doubly linked list. The list traversal can be used to run through all the data in a sorted order, including duplicates.

The usual insert and delete operation of a red-black tree need to be changed:

Insert operation

First a regular insert in the tree is done. There are three possible outcomes:

1. Insert failed because a duplicate is present in the tree
   
   If a duplicate is found in the tree (3) the new node isn't inserted in the tree but it still needs to get linked in the list. Get the next node of the existing duplicate using the tree traversal (4). Insert the new node before it.
2. The new element is a left leaf in the tree
   
   
   Link the new element (1) in the list before the parent (3).
3. The new element is a right leaf in the tree
   
   Since the new node (7) is already inserted in the tree, we can use the tree traversal to get the next (8). Insert the new node in the list before it.

Delete operation

Before we delete a node from the tree check for three situations:

1. The node has duplicates and is not in the tree
   Simply delete the node from the list. The tree hasn't changed.
2. The node has duplicates and is linked in the tree (first of the duplicates)
   Delete the node from the list. The tree structure isn't changed as the next duplicate takes the place of the deleted node in the tree.
3. The node has no duplicates
   Delete the node from the list and delete it from the tree.

Definition

For my maze game I needed to store sprites by their y position. With the tree/list combination in mind I came up with the following class definition:

class TStorage
{
  public:
    TStorage();
    ~TStorage();

    TStorageNode * Insert(int key, TSprite * data);
    void           Delete(TStorageNode * node);

    void           ReplaceKey(TStorageNode * node, int newkey);
    void           Clear();

    TStorageNode * GetFirst();
    TStorageNode * GetLast();

  private:
    TStorageNode * First;
    TStorageNode * Last;
    TStorageNode * Root;
    …
};

Notice that the Insert(…) method returns a TStorageNode *. We need that node to refer to it later if we want to change the key or delete it. Insert(int key, Tsprite * sprite) also takes a TSprite * as a parameter that is stored with the key.

Since the data contained in TStorageNode should only be changed by TStorage, I protected them and declare TStorage a friend. Here's the definition:

class TStorageNode
{
  public:
    TStorageNode * GetNext()        { return Next; }
    TStorageNode * GetPrev()        { return Prev; }

    int            GetKey()         { return Key; }

    TSprite *      GetSprite()      { return Sprite; }
    void           SetSprite(TSprite * newspr)  { Sprite = newspr; }

  private:
    friend class TStorage;

    TStorageNode * Next;
    TStorageNode * Prev;
    TStorageNode * Left;
    TStorageNode * Right;
    TStorageNode * Parent;
    TStorageColor  Color;

    int            Key;
    TSprite *      Sprite;
};

Using it

At the start of the game all sprites are added to the storage object:

void SpriteAdd(TStorage * storage, TSprite * sprite)
{
  TStorageNode *  node;
  
  node = storage->Insert(sprite->ypos, sprite);
  sprite->Node = node;
}

Because the y position of the sprite (the key in the storage) can change during the game, the created node is stored in the sprite so we can refer to it later. This happens in the game's update loop where the sprite positions get updated:

void SpriteChanged(TStorage * storage, TSprite * sprite)
{
  if (sprite->Node->GetKey() != sprite->ypos)
    storage->ReplaceKey(sprite->node, sprite->ypos);
}

If sprites get deleted we have to take then out of the storage before they are freed:

void SpriteRemove(TStorage * storage, TSprite * sprite)
{
  storage->Delete(sprite->Node);
}

Finally, in the drawing loop, we need to traverse through all the sprites and draw them:

void SpriteDrawSorted(TStorage * storage)
{
  TStorageNode *    node;

  for (  node = storage->GetFirst(); 
         node != NULL; 
         node = node->GetNext())
  {
    node->GetSprite()->Draw();
  }
}

The code snippets above solved the drawing order problem in the maze.

The template bit

The current definition of TStorage uses an int as key type and a Tsprite * as userdata. This makes the data structure only useful for the drawing problem. To make it more flexible a template can be used.

I've mixed feelings about templates. They seem very useful and can solve many type related issues especially with container classes such as TStorage. However, in my experience, many programmers get confused by them and the compiler errors and warnings look very daunting. The STL (Standard Template Library) in C++ isn't used as much as would be expected from a library full of so many useful structures. It's like the washing machine issue; the manufacturers, after years of research, claim the new interface is the most user friendly possible. Men still generally don't use them, claiming they can't operate them. Who's wrong?

Rewriting TStorage for templates

See the full source code for the complete implementation but to show the changes:

template <class K, class D> class TStorage
{
  public:
    TStorage();
    ~TStorage();

    TStorageNode<K,D> *  Insert(const T &key, const D &data);
    void                 Delete(TstorageNode<K,D> * node);
        …
}

Looks ugly, doesn't it? And TStorageNode now looks like this:

template <class K, class D> class TStorageNode
{
  public:
    TStorageNode<K,D> *  GetNext()    { return Next; }
    TStorageNode<K,D> *  GetPrev()    { return Prev; }

    K     GetKey()         { return Key; }
    D     GetData()        { return Data; }
    void  SetData(const D &userdata)  { Data = userdata; }


  private:
    friend class TStorage<K,D>;

    TStorageNode<K,D> *  Next;
    TStorageNode<K,D> *  Prev;
    TStorageNode<K,D> *  Left;
    TStorageNode<K,D> *  Right;
    TStorageNode<K,D> *  Parent;
    TStorageColor        Color;

    K        Key;
    D        Data;
};

To get the original class that stores TSprite * with the integer key:

typedef TStorage<int, TSprite *>    TSpriteStorage;
typedef TStorageNode<int, TSprite *>  TspriteStorageNode;

Note that the TStorage uses the operators < and > to compare the keys. So the type you define as key must have those operators implemented. If not, you will get a compiler error in the template code.

About the speed

There is an overhead for keeping the tree balanced, sorted and maintaining the list. As the amount of nodes increase, the overhead increases. However, the extra overhead is only slightly dependent on the number of nodes. Slightly meaning Olog₂N, where O is a constant and N is the number of nodes.

If there is overhead Q at 1000 nodes, and you then use 100 times as many nodes, there won't be a overhead of 100*Q but only 1.7*Q.

So whether a TStorage object holds large or small amounts of data, its Insert(…), Delete(…) and ReplaceKey(…)GetPrev() and GetNext() always execute in constant time (=independent of the number of nodes).

The source code

I borrowed freely from Emin Martinian (http://www.csua.berkeley.edu/~emin/index.html) for the implementation of the red-black tree.

The final implementation includes some extra methods (such as Find) that I didn't discuss in this article. You can download the source code here and you may use it as you wish but at your own risk.

Arjan van den Boogaard
arjan@threelittlewitches.nl
www.threelittlewitches.nl