This section of the archives stores flipcode's complete Developer Toolbox collection, featuring a variety of mini-articles and source code contributions from our readers.

 

  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.

 

Copyright 1999-2008 (C) FLIPCODE.COM and/or the original content author(s). All rights reserved.
Please read our Terms, Conditions, and Privacy information.