flipcode - Templated Splay Tree Class

Templated Splay Tree Class
Submitted by

This is a templated splay tree class (amortized complexity of O(log n)) I wrote up. STL doesn't provide a template tree class of any type, and after writing like 4 different tree classes for different applications, I decided to write a templated OOP splay tree class.

The insert function to the tree takes a pointer to a datatype which the user has already allocated and created. I designed this to use pointers because this allows me to sort the same items into different trees based on different characteristics of the object. For example, If there are two trees filled with derivatives of the CPerson classes, which is defined as follows:

//Person struct
class CPerson
{
public:
  char name[80];
  int age;
};

and the derivatives are:

//This derived class provides the operators to sort by age
class CAgeComp : public CPerson
{
public:
  bool operator<(CAgeComp &c) { return age<c.age; }
  bool operator==(int n) { return age==n; }
  bool operator<(int n) { return age<n; }
};

//This derived class provides the operators to sort by name
class CNameComp : public CPerson
{
public:
  bool operator<(CNameComp &c) { return strcmp(name, c.name)<0; }
  bool operator==(char * c) { return strcmp(name, c)==0; }
  bool operator<(char * c) { return strcmp(name, c)<0; }
};

the definitions of the trees are as follows:

CTree<CNameComp, char * nametree(TRUE);
CTree<CAgeComp, int agetree(FALSE);

The tree that uses CAgeComp will be sorted by age, while the tree that uses CNameComp will be sorted by the name. If I wanted to insert an item into both trees:

CPerson * Bilbo=new CPerson;
Bilbo-age=111;
strcpy(Bilbo-name, "Bilbo");
nametree.Insert((CNameComp *)Bilbo);
agetree.Insert((CAgeComp *)Bilbo);

The TRUE and FALSE after the constructers state whether or not the item pointers inserted in the tree should be deleted when the tree is destroyed. So If I remove Bilbo from the nametree, and change his name to Gumbo and reinsert it, the name is changed in agetree as well. Another reason I chose to use pointers is because copy constructers on some of my objects in my current project are expensive. The tree code also supports tree traversal call back functions. If I wanted to print the agetree in order of age, I could use:

//Callback func to print a hobbit (for age tree)
void WINAPI PrintAgeFunc(CAgeComp * pCharacter, void * pData)
{
  cout << pCharacter-name << "\t" << pCharacter-age << endl;
}

//traverse the tree and call the callback function. the 2nd argument
//is any extended data that you want to send
HobbitAgeTree.InFixCallback(PrintAgeFunc, NULL);

There are further examples in the source code package. Koushik Dutta
koushik_dutta@yahoo.com

Currently browsing [splay.zip] (4,789 bytes) - [main.cpp] - (5,951 bytes)

#include <stdio.h>
#include <iostream.h>
#include <string.h>
#include <time.h>
#include "Tree.h"

//NOTE: rand() only ranges from 0 to RAND_MAX,
//so this should not exceed RAND_MAX who's value is 0x7fff.
#define TREE_INTEGRITY_TEST_SIZE          30000

//Person struct
class CPerson
{
public:
  char name[80];
  int age;
};

//This derived class provides the operators to sort by age
class CAgeComp : public CPerson
{
public:
  bool operator<(CAgeComp &c) { return age<c.age; }
  bool operator==(int n) { return age==n; }
  bool operator<(int n) { return age<n; }
};

//This derived class provides the operators to sort by name
class CNameComp : public CPerson
{
public:
  bool operator<(CNameComp &c) { return strcmp(name, c.name)<0; }
  bool operator==(char * c) { return strcmp(name, c)==0; }
  bool operator<(char * c) { return strcmp(name, c)<0; }
};


//Callback func to print a hobbit (for age tree)
void WINAPI PrintAgeFunc(CAgeComp * pCharacter, void * pData)
{
  cout << pCharacter->name << "\t" << pCharacter->age << endl;
}

//Callback func to print a hobbit (for name tree)
void WINAPI PrintNameFunc(CNameComp * pCharacter, void * pData)
{
  cout << pCharacter->name << "\t" << pCharacter->age << endl;
}

//Return a filled CPerson struct based on the params
CPerson * MakeChar(char * name, int age)
{
  CPerson * c=new CPerson;
  c->age=age;
  strcpy(c->name, name);
  return c;
}


//integrity test callback
void WINAPI IntCountFunc(int * n, void * pData)
{
  int * p=(int *)pData;
  (*p)++;
}


void main()
{
  //this tree sorts by age. it is also responsible
  //for deleting the items added.
  //the int in the template declaration allows me to sort
  //by int instead of filling another CAgeComp class to search
  CTree<CAgeComp, int> HobbitAgeTree(TRUE);
  
  //this tree sorts by name using the same Item pointers as
  //the Age sorted tree
  //char * to search by string..
  CTree<CNameComp, char *> HobbitNameTree(FALSE);

  CPerson * c;

  //make 5 people and add them to be sorted by both trees
  c=MakeChar("Frodo", 33);
  HobbitAgeTree.Insert((CAgeComp *)c);
  HobbitNameTree.Insert((CNameComp *)c);

  c=MakeChar("Bilbo", 111);
  HobbitAgeTree.Insert((CAgeComp *)c);
  HobbitNameTree.Insert((CNameComp *)c);
  
  c=MakeChar("Pippin", 26);
  HobbitAgeTree.Insert((CAgeComp *)c);
  HobbitNameTree.Insert((CNameComp *)c);

  c=MakeChar("Sam", 27);
  HobbitAgeTree.Insert((CAgeComp *)c);
  HobbitNameTree.Insert((CNameComp *)c);

  c=MakeChar("Merry", 25);
  HobbitAgeTree.Insert((CAgeComp *)c);
  HobbitNameTree.Insert((CNameComp *)c);

  cout << "Printing the initial Hobbit trees:" << endl << endl;
  cout << "Printing Hobbits sorted by ages:" << endl;
  HobbitAgeTree.InFixCallback(PrintAgeFunc, NULL);

  cout << endl << "Printing Hobbits sorted by name:" << endl;
  HobbitNameTree.InFixCallback(PrintNameFunc, NULL);

  //now when Bilbo's name is changed in one tree, it is changed in
  //the other as well
  cout << endl << endl << "Removing Bilbo from the name tree and \
    changing his name to Gumbo." << endl;
  c=HobbitNameTree.Delete("Bilbo");
  strcpy(c->name, "Gumbo");
  cout << "Reinserting \"Gumbo\" to the name tree." << endl;
  HobbitNameTree.Insert((CNameComp *)c);

  cout << endl << endl << "Printing the modified Hobbit trees:"
    << endl << endl;
  cout << "Printing Hobbits sorted by ages:" << endl;
  HobbitAgeTree.InFixCallback(PrintAgeFunc, NULL);

  cout << endl << "Printing Hobbits sorted by name:" << endl;
  HobbitNameTree.InFixCallback(PrintNameFunc, NULL);

/*------------------------------------------------------------

  The below is just there to test the tree code and integrity

------------------------------------------------------------*/

  //Insert TREE_INTEGRITY_TEST_SIZE random elements between 0 and
  //TREE_INTEGRITY_TEST_SIZE-1.
  //If the number already exists, the collision counter
  //is incremented.
  //Then delete 1000 using DeleteMin, delete 1000 using DeleteMax
  //and (try) Deleting 1000 using Delete (log how many were actually deleted)
  //At the end, the the number of collisions + tree item count + number
  //deleted should total TREE_INTEGRITY_TEST_SIZE

  srand((unsigned)time(NULL));
  //used by callback to count tree elements
  int gettotal=0;               
  ///used by callback to count how many times items were found (collisions)
  int findcount=0;              
  int numdeleted=2000;          

  CTree<int> nums(TRUE);

  int * n;
  for (int i=0;i<TREE_INTEGRITY_TEST_SIZE;i++)
  {
    n=new int;
    *n=rand()%TREE_INTEGRITY_TEST_SIZE;

    if (nums.Find(*n))
    {
      delete n;
      findcount++;
    }
    else
      nums.Insert(n);
  }

  //Make sure the tree has atleast 3000 elements to delete
  //otherwise the following will result in an access violation.
  //Probability states it will though...
  //dont rely on nums.ItemCount() to get a total..
  //that will always return the correct total number,
  //instead calculate it using a tree traverse callback.
  nums.InFixCallback(IntCountFunc, &gettotal);
  if (gettotal<3000)
  {
    cout << "The impossible has happenned..." << endl;
    return;
  }

  //Try to delete 3000 elements. Log the number actually deleted by
  //nums.Delete(...)
  gettotal=0;
  for (i=0;i<1000;i++)
  {
    delete nums.DeleteMin();
    delete nums.DeleteMax();
    n=nums.Delete(rand()%TREE_INTEGRITY_TEST_SIZE);
    if (NULL!=n)
    {
      numdeleted++;
      delete n;
    }
  }

  nums.InFixCallback(IntCountFunc, &gettotal);

  if (findcount+gettotal+numdeleted!=TREE_INTEGRITY_TEST_SIZE)
    cout << endl << "Tree integrity test failed." << endl;
  else
    cout << endl << "Tree integrity test passed." << endl;

  cout << endl << "Press any key to exit." << endl;
  getchar(); // pause
}

Currently browsing [splay.zip] (4,789 bytes) - [Tree.h] - (4,772 bytes)

#ifndef TEMPLATE_TREE
#define TEMPLATE_TREE

//necessary for callback functions
#include <windows.h>
#include <windef.h>

//type is the class of the object being stored and comp is the class
//that is used to compare for a item when calling Delete
//or Find.
template<class type, class comp=type>
class CTree
{
public:
  typedef void (FAR WINAPI *ENUMTREEPROC)(type * pItem, void * pData);

private:
  class CNode
  {
  public:
    CNode * Left;
    CNode * Right;
    type * Item;

    CNode(type * i) : Left(NULL), Right(NULL), Item(i) {}
    
    ~CNode()
    {
    }

    void InFixCallback(ENUMTREEPROC proc, void * pData)
    {
      if (NULL!=Left)
        Left->InFixCallback(proc, pData);
      proc(this->Item, pData);
      if (NULL!=Right)
        Right->InFixCallback(proc, pData);
    }

    void Cleanup(bool DeleteItem)
    {
      if ((DeleteItem==TRUE) && (NULL!=Item))
      {
        delete Item;
        Item=NULL;
      }

      if (NULL!=Left)
      {
        Left->Cleanup(DeleteItem);
        delete Left;
        Left=NULL;
      }

      if (NULL!=Right)
      {
        Right->Cleanup(DeleteItem);
        delete Right;
        Right=NULL;
      }
    }

    void Insert(CNode * NewNode)
    {
      if (*NewNode->Item<*Item)
      {
        if (NULL==Left)
          Left=NewNode;
        else
          Left->Insert(NewNode);
      }
      else
      {
        if (NULL==Right)
          Right=NewNode;
        else
          Right->Insert(NewNode);
      }
    }

    void Zig()
    {
      type * itmp=Item;
      Item=Right->Item;
      Right->Item=itmp;
      CNode * r=Right->Right;
      Right->Right=Right->Left;
      Right->Left=Left;
      Left=Right;
      Right=r;
    }

    void Zag()
    {
      type * itmp=Item;
      Item=Left->Item;
      Left->Item=itmp;
      CNode * l=Left->Left;
      Left->Left=Left->Right;
      Left->Right=Right;
      Right=Left;
      Left=l;
    }

    void Splay(comp SearchItem)
    {
      if (*Item==SearchItem)
        return;

      if (*Item<SearchItem)
      {
        if (NULL!=Right)
        {
          Right->Splay(SearchItem);
          Zig();
        }
      }
      else
      {
        if (NULL!=Left)
        {
          Left->Splay(SearchItem);
          Zag();
        }
      }
    }

    void DeleteMin()
    {
      if (Left==NULL)
        return;
      Left->DeleteMin();
      Zag();
    }

    void DeleteMax()
    {
      if (Right==NULL)
        return;
      Right->DeleteMax();
      Zig();
    }

  };

  CNode * Head;
  int Count;
  bool DeleteItem;

  void Splay(CNode *& Start, comp SearchItem)
  {
    Start->Splay(SearchItem);
  }


public:
  CTree(bool DeleteOnDestroy)
    : Count(0), Head(NULL), DeleteItem(DeleteOnDestroy) {}
  CTree() : Count(0), Head(NULL), DeleteItem(true) {}
  ~CTree()
  {
    if (NULL!=Head)
    {
      Head->Cleanup(DeleteItem);
      delete Head;
      Head=NULL;
    }
  }

  int ItemCount()
  {
    return Count;
  }

  void Insert(type * Item)
  {
    Count++;
    CNode * NewNode = new CNode(Item);
    if (NULL==Head)
      Head=NewNode;
    else
      Head->Insert(NewNode);
  }

  type * Find(comp SearchItem)
  {
    if (NULL==Head)
      return NULL;

    Splay(Head, SearchItem);

    if (*Head->Item==SearchItem)
      return Head->Item;
    else
      return NULL;
  }

  type * DeleteMin()
  {
    if (NULL==Head)
      return NULL;
    Head->DeleteMin();
    CNode * NewHead=Head->Right;
    type * ret=Head->Item;
    delete Head;
    Head=NewHead;
    Count--;
    return ret;
  }

  type * DeleteMax()
  {
    if (NULL==Head)
      return NULL;
    Head->DeleteMax();
    CNode * NewHead=Head->Left;
    type * ret=Head->Item;
    delete Head;
    Head=NewHead;
    Count--;
    return ret;
  }

  void SetDelete(bool Delete)
  {
    DeleteItem=Delete;
  }

  bool GetDelete()
  {
    return DeleteItem;
  }

  void InFixCallback(ENUMTREEPROC proc, void * pData)
  {
    if (NULL!=Head)
      Head->InFixCallback(proc, pData);
  }

  type * Delete(comp item)
  {
    if (NULL==Head)
      return NULL;

    Splay(Head, item);
    
    if (*Head->Item==item)
    {
      CNode * OldHead=Head;
      type * ret=OldHead->Item;

      if (Head->Left)
      {
        if (Head->Right)
        {
          Splay(Head->Left, item);
          Head->Left->Insert(Head->Right);
        }
        Head=Head->Left;
      }
      else
        Head=Head->Right;

      Count--;
      delete OldHead;
      return ret;
    }
    return NULL;
  }
};

#endif

The zip file viewer built into the Developer Toolbox made use of the zlib library, as well as the zlibdll source additions.