Creating a treemap with C# 2.0

• Download source project [C#] - 11.8 Kb

Introduction

A simple collection is in most cases sufficient. But sometimes you need to index something faster than average. The treemap is an algorithm to speed things up a little. The treemap I created is a treemap that can contain any value, but must have an IComparable key. I used generics, to make it easier to work with.

What does a treemap look like?

A treemap is a list of linked items that have a tree-like relation to each other. You will have one root and several branches and eventually leaves. If you add a new item to the map, it will find a suitable place for the item and insert it there.

Inserting items into the treemap

When the treemap hasn’t got a root, the first item will be inserted there. When the treemap is inserted, the key of the new value that has to be inserted will be compared to the key of the root. If it is greater than that of the root, it will be added to the right node of the root. If it is less than that of the root, it will be added to the left node. If the left or right node is occupied by an item, it will be added to that item.

int result = (key as IComparable).CompareTo(this.key);
if (result < 0)
{
  if (leftNode == null)
  {
    leftNode = new TreeItem<K, V>(key, value);
    leftNode.Parent = this;
    leftNode.Root = root;
  }
  else
  {
    leftNode.Add(key, value);
  }
}
else
{
  if (rightNode == null)
  {
    rightNode = new TreeItem<K, V>(key, value);
    rightNode.Parent = this;
    rightNode.Root = root;
  }
  else
  {
    rightNode.Add(key, value);
  }
}

Removing items from the treemap

Removing items from the treemap is a little more tricky. If you remove an item in the middle of a branch, say with three more items connected to that item, it would normally remove those three items also. That’s not what you want. Instead of removing those three items, we pop them back into the treemap by getting the left and right node of the item that is about to be removed and inserting them as an argument into the function Add. This will add those items and the connected ones to the treemap again into the right position.

public void Add(TreeItem<K,V> item)
{
  int result = (item.Key as IComparable).CompareTo(this.key);

  if (result < 0)
  {
    if (leftNode == null)
    {
      leftNode = item;
      leftNode.Parent = this;
      leftNode.Root = root;
    }
    else
    {
      leftNode.Add(item);
    }
  }
  else
  {
    if (rightNode == null)
    {
      rightNode = item;
      rightNode.Parent = this;
      rightNode.Root = root;
    }
    else
    {
      rightNode.Add(item);
    }
  }
}

Combining the treemap with other collections

The treemap is a good way to find stuff quickly in memory, but you can’t iterate through the items. There is a way to overcome this. You could create a normal collection that internally not only holds the collection, but also holds a treemap. This doesn’t cost anymore memory, since you can add the same items to the list as well to the treemap. This way, you use pointers/references to reduce memory size and still get fast search results when searching on keys.

Conclusion

I hope this helps you fellow programmers/developers/designers/what-else-more-is- creating-computer-software people with creating great computer software.

This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here