C++ Data Structure Implementations

[jrkeller27]

Hi, I'm just wondering if there is a good place where I can find some tree implementations for c++ (Splay trees and Heaps, in particular). Any input on resources where there is source code for different tree implementations would be appreciated, as I don't have the time to write one on my own, and I need to get more experience reading other peoples code

Thanks again

[Ancient Dragon]

where have you looked? Did you try google?

[Narue]

This covers several different trees, including a variation of the heap. I haven't yet gotten around to finishing my splay tree tutorial, but here's a draft of the code (for both top down and bottom up splaying):

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

struct jsw_node {
  int data;
  struct jsw_node *link[2];
};

struct jsw_tree {
  struct jsw_node *root;
};

struct jsw_node *jsw_single ( struct jsw_node *root, int dir )
{
  struct jsw_node *save = root->link[dir];

  root->link[dir] = save->link[!dir];
  save->link[!dir] = root;

  return save;
}

struct jsw_node *jsw_splay_r ( struct jsw_node *root, int *key )
{
  if ( root != NULL && *key != root->data ) {
    int dir = root->data < *key;

    root->link[dir] = jsw_splay_r ( root->link[dir], key );

    if ( root->link[dir] != NULL ) {
      struct jsw_node *zig = root->link[dir]->link[dir];
      struct jsw_node *zag = root->link[dir]->link[!dir];

      if ( zig != NULL && *key == zig->data ) {
        /* Zig-Zig */
        root = jsw_single ( root, dir );
        root = jsw_single ( root, dir );
      }
      else if ( zag != NULL && *key == zag->data ) {
        /* Zig-Zag */
        root->link[dir] = jsw_single ( root->link[dir], !dir );
        root = jsw_single ( root, dir );
      }
    }
    else
      *key = root->data;
  }

  return root;
}

struct jsw_node *jsw_busplay ( struct jsw_node *root, int key )
{
  int dir;

  root = jsw_splay_r ( root, &key );

  dir = root->data < key;

  /* Final Zig if necessary */
  if ( root->link[dir] != NULL && key != root->data )
    root = jsw_single ( root, dir );

  return root;
}

struct jsw_node *jsw_tdsplay ( struct jsw_node *root, int key )
{
  struct jsw_node save = {0};
  struct jsw_node *left = &save;
  struct jsw_node *right = &save;

  if ( root == NULL )
    return root;

  while ( key != root->data ) {
    int dir = root->data < key;
    struct jsw_node **hold;

    if ( root->link[dir] == NULL )
      break;

    if ( ( dir == 0 && key < root->link[dir]->data )
      || ( dir != 0 && key > root->link[dir]->data ) )
    {
      root = jsw_single ( root, dir );

      if ( root->link[dir] == NULL )
        break;
    }

    hold = dir != 0 ? &left : &right;
    (*hold)->link[dir] = root;
    *hold = root;
    root = root->link[dir];
  }

  /* Reassemble */
  left->link[1] = root->link[0];
  right->link[0] = root->link[1];
  root->link[0] = save.link[1];
  root->link[1] = save.link[0];

  return root;
}

int jsw_insert ( struct jsw_tree *tree, int key )
{
  struct jsw_node *walk = malloc ( sizeof *walk );

  if ( walk == NULL )
    return 0;

  walk->data = key;
  walk->link[0] = walk->link[1] = NULL;

  if ( tree->root == NULL ) {
    tree->root = walk;
    return 1;
  }

  tree->root = jsw_busplay ( tree->root, key );

  if ( key == tree->root->data )
    return 0;
  else {
    int dir = key > tree->root->data;

    walk->link[dir] = tree->root->link[dir];
    walk->link[!dir] = tree->root;
    tree->root->link[dir] = NULL;
    tree->root = walk;

    return 1;
  }
}

int jsw_remove ( struct jsw_tree *tree, int key )
{
  struct jsw_node *save;

  if ( tree->root == NULL )
    return 0;

  tree->root = jsw_busplay ( tree->root, key );

  if ( key == tree->root->data ) {
    if ( tree->root->link[0] == NULL )
      save = tree->root->link[1];
    else {
      save = jsw_busplay ( tree->root->link[0], key );
      save->link[1] = tree->root->link[1];
    }

    free ( tree->root );
    free->root = save;
  }

  return 1;
}

#define SPLAY_TREE_TEST_FRAMEWORK
#ifdef SPLAY_TREE_TEST_FRAMEWORK

void dump_r ( struct jsw_node *root, int level )
{
  int i;

  if ( root == NULL ) {
    for ( i = 0; i < level; i++ )
      putchar ( '\t' );
    puts ( "~" );
  }
  else {
    dump_r ( root->link[1], level + 1 );

    for ( i = 0; i < level; i++ )
      putchar ( '\t' );
    printf ( "%d\n", root->data );

    dump_r ( root->link[0], level + 1 );
  }
}

void dump ( struct jsw_tree *tree )
{
  dump_r ( tree->root, 0 );
  puts ( "\n===========" );
}

int main ( void )
{
  struct jsw_tree t = {0};
  int i;

  srand ( (unsigned)time ( NULL ) );

  for ( i = 0; i < 20; i++ ) {
    int r = rand() % 1000;
    printf ( "Insert %d\n", r );
    jsw_insert ( &t, r );
    dump ( &t );
    getchar();
  }

  return 0;
}

#endif  SPLAY_TREE_TEST_FRAMEWORK

And a more formalized version, but it only uses the top down splaying algorithm:

#ifndef JSW_SPLAY_H
#define JSW_SPLAY_H

#ifdef __cplusplus
#include <cstddef>

using std::size_t;

extern "C" {
#else
#include <stddef.h>
#endif

/* Opaque types */
typedef struct jsw_splay     jsw_splay_t;
typedef struct jsw_splaytrav jsw_splaytrav_t;

/* User-defined item handling */
typedef int   (*cmp_f) ( const void *p1, const void *p2 );
typedef void *(*dup_f) ( void *p );
typedef void  (*rel_f) ( void *p );

/* Splay tree functions */
jsw_splay_t     *jsw_splaynew ( cmp_f cmp, dup_f dup, rel_f rel );
void             jsw_splaydelete ( jsw_splay_t *tree );
void            *jsw_splayfind ( jsw_splay_t *tree, void *data );
int              jsw_splayinsert ( jsw_splay_t *tree, void *data );
int              jsw_splayerase ( jsw_splay_t *tree, void *data );
size_t           jsw_splaysize ( jsw_splay_t *tree );

/* Traversal functions */
jsw_splaytrav_t *jsw_splaytnew ( void );
void             jsw_splaytdelete ( jsw_splaytrav_t *trav );
void            *jsw_splaytfirst ( jsw_splaytrav_t *trav, jsw_splay_t *tree );
void            *jsw_splaytlast ( jsw_splaytrav_t *trav, jsw_splay_t *tree );
void            *jsw_splaytnext ( jsw_splaytrav_t *trav );
void            *jsw_splaytprev ( jsw_splaytrav_t *trav );

/* Debugging functions */
#include <stdio.h>
void jsw_splaydump ( jsw_splay_t *tree, FILE *out );
int  jsw_treeassert ( jsw_splay_t *tree );
int  jsw_splayassert ( jsw_splay_t *tree, void *data );

#ifdef __cplusplus
}
#endif

#endif

#include "jsw_splay.h"

#ifdef __cplusplus
#include <cstdlib>

using std::malloc;
using std::free;
using std::size_t;
#else
#include <stdlib.h>
#endif

#ifndef HEIGHT_LIMIT
#define HEIGHT_LIMIT 64 /* Tallest allowable tree */
#endif

typedef struct jsw_splaynode {
  void                 *data;    /* User-defined content */
  struct jsw_splaynode *link[2]; /* Left (0) and right (1) links */
} jsw_splaynode_t;

struct jsw_splay {
  jsw_splaynode_t *root; /* Top of the tree */
  cmp_f            cmp;    /* Compare two items */
  dup_f            dup;    /* Clone an item (user-defined) */
  rel_f            rel;    /* Destroy an item (user-defined) */
  size_t           size;   /* Number of items (user-defined) */
};

struct jsw_splaytrav {
  jsw_splay_t     *tree;               /* Paired tree */
  jsw_splaynode_t *it;                 /* Current node */
  jsw_splaynode_t *path[HEIGHT_LIMIT]; /* Traversal path */
  size_t           top;                /* Top of stack */
};

/* Two way single rotation */
#define jsw_single(root,dir) do {          \
  jsw_splaynode_t *save = root->link[dir]; \
  root->link[dir] = save->link[!dir];      \
  save->link[!dir] = root;                 \
  root = save;                             \
} while (0)

static jsw_splaynode_t *new_node ( jsw_splay_t *tree, void *data )
{
  jsw_splaynode_t *rn = (jsw_splaynode_t *)malloc ( sizeof *rn );

  if ( rn == NULL )
    return NULL;

  rn->data = tree->dup ( data );
  rn->link[0] = rn->link[1] = NULL;

  return rn;
}

static jsw_splaynode_t *jsw_splay ( jsw_splay_t *tree, jsw_splaynode_t *root, void *data )
{
  jsw_splaynode_t  save = {0};
  jsw_splaynode_t *left = &save;
  jsw_splaynode_t *right = &save;

  if ( root == NULL )
    return root;

  while ( tree->cmp ( data, root->data ) != 0 ) {
    int dir = tree->cmp ( root->data, data ) < 0;
    jsw_splaynode_t **hold;

    if ( root->link[dir] == NULL )
      break;

    if ( ( dir == 0 && tree->cmp ( data, root->link[dir]->data ) < 0 )
      || ( dir != 0 && tree->cmp ( data, root->link[dir]->data ) > 0 ) )
    {
      jsw_single ( root, dir );

      if ( root->link[dir] == NULL )
        break;
    }

    hold = dir != 0 ? &left : &right;
    (*hold)->link[dir] = root;
    *hold = root;
    root = root->link[dir];
  }

  /* Reassemble */
  left->link[1] = root->link[0];
  right->link[0] = root->link[1];
  root->link[0] = save.link[1];
  root->link[1] = save.link[0];

  return root;
}

jsw_splay_t *jsw_splaynew ( cmp_f cmp, dup_f dup, rel_f rel )
{
  jsw_splay_t *rt = (jsw_splay_t *)malloc ( sizeof *rt );

  if ( rt == NULL )
    return NULL;

  rt->root = NULL;
  rt->cmp = cmp;
  rt->dup = dup;
  rt->rel = rel;
  rt->size = 0;

  return rt;
}

void jsw_splaydelete ( jsw_splay_t *tree )
{
  jsw_splaynode_t *it = tree->root;
  jsw_splaynode_t *save;

  /* Destruction by rotation */
  while ( it != NULL ) {
    if ( it->link[0] == NULL ) {
      /* Remove node */
      save = it->link[1];
      tree->rel ( it->data );
      free ( it );
    }
    else {
      /* Rotate right */
      save = it->link[0];
      it->link[0] = save->link[1];
      save->link[1] = it;
    }

    it = save;
  }

  free ( tree );
}

void *jsw_splayfind ( jsw_splay_t *tree, void *data )
{
  jsw_splaynode_t *match = jsw_splay ( tree, tree->root, data );

  if ( match != NULL && tree->cmp ( tree->root->data, data ) == 0 )
    return match;

  return NULL;
}

int jsw_splayinsert ( jsw_splay_t *tree, void *data )
{
  jsw_splaynode_t *walk = new_node ( tree, data );

  if ( walk == NULL )
    return 0;

  if ( tree->root == NULL ) {
    tree->root = walk;
    ++tree->size;
    return 1;
  }

  tree->root = jsw_splay ( tree, tree->root, data );

  if ( tree->cmp ( data, tree->root->data ) != 0 ) {
    int dir = tree->cmp ( data, tree->root->data ) > 0;

    walk->link[dir] = tree->root->link[dir];
    walk->link[!dir] = tree->root;
    tree->root->link[dir] = NULL;
    tree->root = walk;
    ++tree->size;

    return 1;
  }

  return 0; /* Data already present */
}

int jsw_splayerase ( jsw_splay_t *tree, void *data )
{
  jsw_splaynode_t *save;

  if ( tree->root == NULL )
    return 0;

  tree->root = jsw_splay ( tree, tree->root, data );

  if ( tree->cmp ( data, tree->root->data ) == 0 ) {
    if ( tree->root->link[0] == NULL )
      save = tree->root->link[1];
    else {
      save = jsw_splay ( tree, tree->root->link[0], data );
      save->link[1] = tree->root->link[1];
    }

    tree->rel ( tree->root->data );
    free ( tree->root );
    tree->root = save;
    --tree->size;
  }

  return 1;
}

size_t jsw_splaysize ( jsw_splay_t *tree )
{
  return tree->size;
}

jsw_splaytrav_t *jsw_splaytnew ( void )
{
  return malloc ( sizeof ( jsw_splaytrav_t ) );
}

void jsw_splaytdelete ( jsw_splaytrav_t *trav )
{
  free ( trav );
}

/*
  First step in traversal,
  handles min and max
*/
static void *start ( jsw_splaytrav_t *trav, jsw_splay_t *tree, int dir )
{
  trav->tree = tree;
  trav->it = tree->root;
  trav->top = 0;

  /* Build a path to work with */
  if ( trav->it != NULL ) {
    while ( trav->it->link[dir] != NULL ) {
      trav->path[trav->top++] = trav->it;
      trav->it = trav->it->link[dir];
    }
  }

  return trav->it == NULL ? NULL : trav->it->data;
}

/*
  Subsequent traversal steps,
  handles ascending and descending
*/
static void *move ( jsw_splaytrav_t *trav, int dir )
{
  if ( trav->it->link[dir] != NULL ) {
    /* Continue down this branch */
    trav->path[trav->top++] = trav->it;
    trav->it = trav->it->link[dir];

    while ( trav->it->link[!dir] != NULL ) {
      trav->path[trav->top++] = trav->it;
      trav->it = trav->it->link[!dir];
    }
  }
  else {
    /* Move to the next branch */
    jsw_splaynode_t *last;

    do {
      if ( trav->top == 0 ) {
        trav->it = NULL;
        break;
      }

      last = trav->it;
      trav->it = trav->path[--trav->top];
    } while ( last == trav->it->link[dir] );
  }

  return trav->it == NULL ? NULL : trav->it->data;
}

void *jsw_splaytfirst ( jsw_splaytrav_t *trav, jsw_splay_t *tree )
{
  return start ( trav, tree, 0 ); /* Min value */
}

void *jsw_splaytlast ( jsw_splaytrav_t *trav, jsw_splay_t *tree )
{
  return start ( trav, tree, 1 ); /* Max value */
}

void *jsw_splaytnext ( jsw_splaytrav_t *trav )
{
  return move ( trav, 1 ); /* Toward larger items */
}

void *jsw_splaytprev ( jsw_splaytrav_t *trav )
{
  return move ( trav, 0 ); /* Toward smaller items */
}

#include <stdio.h>

static void jsw_splaydump_r ( jsw_splaynode_t *root, int level, FILE *out )
{
  int i;

  if ( root == NULL ) {
    for ( i = 0; i < level; i++ )
      fputc ( '\t', out );
    fputs ( "~\n", out );
  }
  else {
    jsw_splaydump_r ( root->link[1], level + 1, out );

    for ( i = 0; i < level; i++ )
      fputc ( '\t', out );
    fprintf ( out, "%d\n", *(int *)root->data );

    jsw_splaydump_r ( root->link[0], level + 1, out );
  }
}

void jsw_splaydump ( jsw_splay_t *tree, FILE *out )
{
  jsw_splaydump_r ( tree->root, 0, out );
}

int jsw_treeassert_r ( jsw_splay_t *tree, jsw_splaynode_t *root )
{
  if ( root != NULL ) {
    jsw_splaynode_t *ln = root->link[0];
    jsw_splaynode_t *rn = root->link[1];

    int lh = jsw_treeassert_r ( tree, ln );
    int rh = jsw_treeassert_r ( tree, rn );

    /* Invalid binary search tree */
    if ( ( ln != NULL && tree->cmp ( ln->data, root->data ) >= 0 )
      || ( rn != NULL && tree->cmp ( rn->data, root->data ) <= 0 ) )
    {
      puts ( "Binary tree violation" );
      return 0;
    }
  }

  return 1;
}

int jsw_treeassert ( jsw_splay_t *tree )
{
  return jsw_treeassert_r ( tree, tree->root );
}

int jsw_splayassert ( jsw_splay_t *tree, void *data )
{
  if ( tree->cmp ( tree->root->data, data ) != 0 ) {
    puts ( "Root violation" );
    return 0;
  }

  return 1;
}

None of this code has been thoroughly tested, so use it at your own risk.

[amromun]

Hi
can I ask what does jsw_busplay do ?

[Narue]

>can I ask what does jsw_busplay do ?
It recursively splays from the bottom up to the root. :icon_rolleyes: As for how it works, that's relatively easy to figure out if you do a paper run of the algorithm. Imagine a simple tree and do some inserts on it, with each step of the algorithm being illustrated on paper.

[amromun]

Ahhhh , Trees give me headaches currently am working on a project on Trees : BST,AVL,B-tree,Splay,red black its too much

thx Narue for answering