bst red black that does not work
what is wrong with this?



// rbt.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"

#ifndef rbth
#define rbth

typedef enum {
    RBT_STATUS_OK,
    RBT_STATUS_MEM_EXHAUSTED,
    RBT_STATUS_DUPLICATE_KEY,
    RBT_STATUS_KEY_NOT_FOUND
} RbtStatus;

typedef void *RbtIterator;
typedef void *RbtHandle;

RbtHandle rbtNew(int(*compare)(void *a, void *b));
// create red-black tree
// parameters:
//     compare  pointer to function that compares keys
//              return 0   if a == b
//              return < 0 if a < b
//              return > 0 if a > b
// returns:
//     handle   use handle in calls to rbt functions


void rbtDelete(RbtHandle h);
// destroy red-black tree

RbtStatus rbtInsert(RbtHandle h, void *key, void *value);
// insert key/value pair

RbtStatus rbtErase(RbtHandle h, RbtIterator i);
// delete node in tree associated with iterator
// this function does not free the key/value pointers

RbtIterator rbtNext(RbtHandle h, RbtIterator i);
// return ++i

RbtIterator rbtBegin(RbtHandle h);
// return pointer to first node

RbtIterator rbtEnd(RbtHandle h);
// return pointer to one past last node

void rbtKeyValue(RbtHandle h, RbtIterator i, void **key, void **value);
// returns key/value pair associated with iterator

RbtIterator rbtFind(RbtHandle h, void *key);
// returns iterator associated with key

#endif 

// reentrant red-black tree

#include <stdlib.h>
#include <rbtr.h>

typedef enum { BLACK, RED } NodeColor;

typedef struct NodeTag {
    struct NodeTag *left;       // left child
    struct NodeTag *right;      // right child
    struct NodeTag *parent;     // parent
    NodeColor color;            // node color (BLACK, RED)
    void *key;                  // key used for searching
    void *val;                // user data
} NodeType;

typedef struct RbtTag {
    NodeType *root;   // root of red-black tree
    NodeType sentinel;
    int (*compare)(void *a, void *b);    // compare keys
} RbtType;

// all leafs are sentinels
#define SENTINEL &rbt->sentinel

RbtHandle rbtNew(int(*rbtCompare)(void *a, void *b)) {
    RbtType *rbt;
    
    if ((rbt = (RbtType *)malloc(sizeof(RbtType))) == NULL) {
        return NULL;
    }

    rbt->compare = rbtCompare;
    rbt->root = SENTINEL;
    rbt->sentinel.left = SENTINEL;
    rbt->sentinel.right = SENTINEL;
    rbt->sentinel.parent = NULL;
    rbt->sentinel.color = BLACK;
    rbt->sentinel.key = NULL;
    rbt->sentinel.val = NULL;

    return rbt;
}

static void deleteTree(RbtHandle h, NodeType *p) {
    RbtType *rbt = h;

    // erase nodes depth-first
    if (p == SENTINEL) return;
    deleteTree(h, p->left);
    deleteTree(h, p->right);
    free(p);
}

void rbtDelete(RbtHandle h) {
    RbtType *rbt = h;

    deleteTree(h, rbt->root);
    free(rbt);
}

static void rotateLeft(RbtType *rbt, NodeType *x) {

    // rotate node x to left

    NodeType *y = x->right;

    // establish x->right link
    x->right = y->left;
    if (y->left != SENTINEL) y->left->parent = x;

    // establish y->parent link
    if (y != SENTINEL) y->parent = x->parent;
    if (x->parent) {
        if (x == x->parent->left)
            x->parent->left = y;
        else
            x->parent->right = y;
    } else {
        rbt->root = y;
    }

    // link x and y
    y->left = x;
    if (x != SENTINEL) x->parent = y;
}

static void rotateRight(RbtType *rbt, NodeType *x) {

    // rotate node x to right

    NodeType *y = x->left;

    // establish x->left link
    x->left = y->right;
    if (y->right != SENTINEL) y->right->parent = x;

    // establish y->parent link
    if (y != SENTINEL) y->parent = x->parent;
    if (x->parent) {
        if (x == x->parent->right)
            x->parent->right = y;
        else
            x->parent->left = y;
    } else {
        rbt->root = y;
    }

    // link x and y
    y->right = x;
    if (x != SENTINEL) x->parent = y;
}

static void insertFixup(RbtType *rbt, NodeType *x) {

    // maintain red-black tree balance after inserting node x

    // check red-black properties
    while (x != rbt->root && x->parent->color == RED) {
        // we have a violation
        if (x->parent == x->parent->parent->left) {
            NodeType *y = x->parent->parent->right;
            if (y->color == RED) {

                // uncle is RED
                x->parent->color = BLACK;
                y->color = BLACK;
                x->parent->parent->color = RED;
                x = x->parent->parent;
            } else {

                // uncle is BLACK
                if (x == x->parent->right) {
                    // make x a left child
                    x = x->parent;
                    rotateLeft(rbt, x);
                }

                // recolor and rotate
                x->parent->color = BLACK;
                x->parent->parent->color = RED;
                rotateRight(rbt, x->parent->parent);
            }
        } else {

            // mirror image of above code
            NodeType *y = x->parent->parent->left;
            if (y->color == RED) {

                // uncle is RED
                x->parent->color = BLACK;
                y->color = BLACK;
                x->parent->parent->color = RED;
                x = x->parent->parent;
            } else {

                // uncle is BLACK
                if (x == x->parent->left) {
                    x = x->parent;
                    rotateRight(rbt, x);
                }
                x->parent->color = BLACK;
                x->parent->parent->color = RED;
                rotateLeft(rbt, x->parent->parent);
            }
        }
    }
    rbt->root->color = BLACK;
}

RbtStatus rbtInsert(RbtHandle h, void *key, void *val) {
    NodeType *current, *parent, *x;
    RbtType *rbt = h;

    // allocate node for data and insert in tree

    // find future parent
    current = rbt->root;
    parent = 0;
    while (current != SENTINEL) {
        int rc = rbt->compare(key, current->key);
        if (rc == 0)
            return RBT_STATUS_DUPLICATE_KEY;
        parent = current;
        current = (rc < 0) ? current->left : current->right;
    }

    // setup new node
    if ((x = malloc (sizeof(*x))) == 0)
        return RBT_STATUS_MEM_EXHAUSTED;
    x->parent = parent;
    x->left = SENTINEL;
    x->right = SENTINEL;
    x->color = RED;
    x->key = key;
    x->val = val;

    // insert node in tree
    if(parent) {
        if(rbt->compare(key, parent->key) < 0)
            parent->left = x;
        else
            parent->right = x;
    } else {
        rbt->root = x;
    }

    insertFixup(rbt, x);

    return RBT_STATUS_OK;
}

void deleteFixup(RbtType *rbt, NodeType *x) {

    // maintain red-black tree balance after deleting node x

    while (x != rbt->root && x->color == BLACK) {
        if (x == x->parent->left) {
            NodeType *w = x->parent->right;
            if (w->color == RED) {
                w->color = BLACK;
                x->parent->color = RED;
                rotateLeft (rbt, x->parent);
                w = x->parent->right;
            }
            if (w->left->color == BLACK && w->right->color == BLACK) {
                w->color = RED;
                x = x->parent;
            } else {
                if (w->right->color == BLACK) {
                    w->left->color = BLACK;
                    w->color = RED;
                    rotateRight (rbt, w);
                    w = x->parent->right;
                }
                w->color = x->parent->color;
                x->parent->color = BLACK;
                w->right->color = BLACK;
                rotateLeft (rbt, x->parent);
                x = rbt->root;
            }
        } else {
            NodeType *w = x->parent->left;
            if (w->color == RED) {
                w->color = BLACK;
                x->parent->color = RED;
                rotateRight (rbt, x->parent);
                w = x->parent->left;
            }
            if (w->right->color == BLACK && w->left->color == BLACK) {
                w->color = RED;
                x = x->parent;
            } else {
                if (w->left->color == BLACK) {
                    w->right->color = BLACK;
                    w->color = RED;
                    rotateLeft (rbt, w);
                    w = x->parent->left;
                }
                w->color = x->parent->color;
                x->parent->color = BLACK;
                w->left->color = BLACK;
                rotateRight (rbt, x->parent);
                x = rbt->root;
            }
        }
    }
    x->color = BLACK;
}

RbtStatus rbtErase(RbtHandle h, RbtIterator i) {
    NodeType *x, *y;
    RbtType *rbt = h;
    NodeType *z = i;

    if (z->left == SENTINEL || z->right == SENTINEL) {
        // y has a SENTINEL node as a child
        y = z;
    } else {
        // find tree successor with a SENTINEL node as a child
        y = z->right;
        while (y->left != SENTINEL) y = y->left;
    }

    // x is y's only child
    if (y->left != SENTINEL)
        x = y->left;
    else
        x = y->right;

    // remove y from the parent chain
    x->parent = y->parent;
    if (y->parent)
        if (y == y->parent->left)
            y->parent->left = x;
        else
            y->parent->right = x;
    else
        rbt->root = x;

    if (y != z) {
        z->key = y->key;
        z->val = y->val;
    }


    if (y->color == BLACK)
        deleteFixup (rbt, x);

    free (y);

    return RBT_STATUS_OK;
}

RbtIterator rbtNext(RbtHandle h, RbtIterator it) {
    RbtType *rbt = h;
    NodeType *i = it;

    if (i->right != SENTINEL) {
        // go right 1, then left to the end
        for (i = i->right; i->left != SENTINEL; i = i->left);
    } else {
        // while you're the right child, chain up parent link
        NodeType *p = i->parent;
        while (p && i == p->right) {
            i = p;
            p = p->parent;
        }

        // return the "inorder" node
        i = p;
    }
    return i != SENTINEL ? i : NULL;
}

RbtIterator rbtBegin(RbtHandle h) {
    RbtType *rbt = h;

    // return pointer to first value
    NodeType *i;
    for (i = rbt->root; i->left != SENTINEL; i = i->left);
    return i != SENTINEL ? i : NULL;
}

RbtIterator rbtEnd(RbtHandle h) {
   // return pointer to one past last value
   return NULL;
}

void rbtKeyValue(RbtHandle h, RbtIterator it, void **key, void **val) {
    NodeType *i = it;

    *key = i->key;
    *val = i->val;
}


void *rbtFind(RbtHandle h, void *key) {
    RbtType *rbt = h;

    NodeType *current;
    current = rbt->root;
    while(current != SENTINEL) {
        int rc = rbt->compare(key, current->key);
        if (rc == 0) return current;
        current = (rc < 0) ? current->left : current->right;
    }
    return NULL;
 #include <stdio.h>
#include <stdlib.h>
#include "rbtr.h"

int compare(void *a, void *b) {
    return *(int *)a - *(int *)b;
}

int main(int argc, char **argv) {
    int maxnum, ct;

    // command-line:
    //
    //   rbtmain 2000
    //       process 2000 records

    RbtIterator i;
    RbtHandle h;
    RbtStatus status;

    maxnum = atoi(argv[1]);

    // obtain handle to red-black tree
    h = rbtNew(compare);

    printf("maxnum = %d\n", maxnum);
    for (ct = maxnum; ct; ct--) {
        int key = rand() % 90 + 1;

        if ((i = rbtFind(h, &key)) != rbtEnd(h)) {
            // found an existing node
            void *keyp, *valuep;

            // get key-value pointers
            rbtKeyValue(h, i, &keyp, &valuep);

            // check to see they contain correct data
            if (*(int *)keyp != key) printf("fail keyp\n");
            if (*(int *)valuep != 10*key) printf("fail valuep\n");

            // erase node in red-black tree
            status = rbtErase(h, i);
            if (status) printf("fail: status = %d\n", status);

            // free the pointers allocated by main
            free(keyp); free(valuep);

        } else {
            // create a new node
            int *keyp, *valuep;

            // allocate key/value data
            keyp = (int *)malloc(sizeof(int));
            valuep = (int *)malloc(sizeof(int));

            // initialize with values
            *keyp = key;
            *valuep = 10*key;

            // insert in red-black tree
            status = rbtInsert(h, keyp, valuep);
            if (status) printf("fail: status = %d\n", status);
        }
    }

    // output nodes in order
    for (i = rbtBegin(h); i != rbtEnd(h); i = rbtNext(h, i)) {
        void *keyp, *valuep;
        rbtKeyValue(h, i, &keyp, &valuep);
        printf("%d %d\n", *(int *)keyp, *(int *)valuep);
    }

    // delete my allocated memory
    for (i = rbtBegin(h); i != rbtEnd(h); i = rbtNext(h, i)) {
        void *keyp, *valuep;
        rbtKeyValue(h, i, &keyp, &valuep);
        free(keyp); free(valuep);
    }

    // delete red-black tree
    rbtDelete(h);

    return 0;
}
}

bst red black that does not work
===

what is wrong with this?



// rbt.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"

#ifndef rbth
#define rbth

typedef enum {
    RBT_STATUS_OK,
    RBT_STATUS_MEM_EXHAUSTED,
    RBT_STATUS_DUPLICATE_KEY,
    RBT_STATUS_KEY_NOT_FOUND
} RbtStatus;

typedef void *RbtIterator;
typedef void *RbtHandle;

RbtHandle rbtNew(int(*compare)(void *a, void *b));
// create red-black tree
// parameters:
//     compare  pointer to function that compares keys
//              return 0   if a == b
//              return < 0 if a < b
//              return > 0 if a > b
// returns:
//     handle   use handle in calls to rbt functions


void rbtDelete(RbtHandle h);
// destroy red-black tree

RbtStatus rbtInsert(RbtHandle h, void *key, void *value);
// insert key/value pair

RbtStatus rbtErase(RbtHandle h, RbtIterator i);
// delete node in tree associated with iterator
// this function does not free the key/value pointers

RbtIterator rbtNext(RbtHandle h, RbtIterator i);
// return ++i

RbtIterator rbtBegin(RbtHandle h);
// return pointer to first node

RbtIterator rbtEnd(RbtHandle h);
// return pointer to one past last node

void rbtKeyValue(RbtHandle h, RbtIterator i, void **key, void **value);
// returns key/value pair associated with iterator

RbtIterator rbtFind(RbtHandle h, void *key);
// returns iterator associated with key

#endif 

// reentrant red-black tree

#include <stdlib.h>
#include <rbtr.h>

typedef enum { BLACK, RED } NodeColor;

typedef struct NodeTag {
    struct NodeTag *left;       // left child
    struct NodeTag *right;      // right child
    struct NodeTag *parent;     // parent
    NodeColor color;            // node color (BLACK, RED)
    void *key;                  // key used for searching
    void *val;                // user data
} NodeType;

typedef struct RbtTag {
    NodeType *root;   // root of red-black tree
    NodeType sentinel;
    int (*compare)(void *a, void *b);    // compare keys
} RbtType;

// all leafs are sentinels
#define SENTINEL &rbt->sentinel

RbtHandle rbtNew(int(*rbtCompare)(void *a, void *b)) {
    RbtType *rbt;
    
    if ((rbt = (RbtType *)malloc(sizeof(RbtType))) == NULL) {
        return NULL;
    }

    rbt->compare = rbtCompare;
    rbt->root = SENTINEL;
    rbt->sentinel.left = SENTINEL;
    rbt->sentinel.right = SENTINEL;
    rbt->sentinel.parent = NULL;
    rbt->sentinel.color = BLACK;
    rbt->sentinel.key = NULL;
    rbt->sentinel.val = NULL;

    return rbt;
}

static void deleteTree(RbtHandle h, NodeType *p) {
    RbtType *rbt = h;

    // erase nodes depth-first
    if (p == SENTINEL) return;
    deleteTree(h, p->left);
    deleteTree(h, p->right);
    free(p);
}

void rbtDelete(RbtHandle h) {
    RbtType *rbt = h;

    deleteTree(h, rbt->root);
    free(rbt);
}

static void rotateLeft(RbtType *rbt, NodeType *x) {

    // rotate node x to left

    NodeType *y = x->right;

    // establish x->right link
    x->right = y->left;
    if (y->left != SENTINEL) y->left->parent = x;

    // establish y->parent link
    if (y != SENTINEL) y->parent = x->parent;
    if (x->parent) {
        if (x == x->parent->left)
            x->parent->left = y;
        else
            x->parent->right = y;
    } else {
        rbt->root = y;
    }

    // link x and y
    y->left = x;
    if (x != SENTINEL) x->parent = y;
}

static void rotateRight(RbtType *rbt, NodeType *x) {

    // rotate node x to right

    NodeType *y = x->left;

    // establish x->left link
    x->left = y->right;
    if (y->right != SENTINEL) y->right->parent = x;

    // establish y->parent link
    if (y != SENTINEL) y->parent = x->parent;
    if (x->parent) {
        if (x == x->parent->right)
            x->parent->right = y;
        else
            x->parent->left = y;
    } else {
        rbt->root = y;
    }

    // link x and y
    y->right = x;
    if (x != SENTINEL) x->parent = y;
}

static void insertFixup(RbtType *rbt, NodeType *x) {

    // maintain red-black tree balance after inserting node x

    // check red-black properties
    while (x != rbt->root && x->parent->color == RED) {
        // we have a violation
        if (x->parent == x->parent->parent->left) {
            NodeType *y = x->parent->parent->right;
            if (y->color == RED) {

                // uncle is RED
                x->parent->color = BLACK;
                y->color = BLACK;
                x->parent->parent->color = RED;
                x = x->parent->parent;
            } else {

                // uncle is BLACK
                if (x == x->parent->right) {
                    // make x a left child
                    x = x->parent;
                    rotateLeft(rbt, x);
                }

                // recolor and rotate
                x->parent->color = BLACK;
                x->parent->parent->color = RED;
                rotateRight(rbt, x->parent->parent);
            }
        } else {

            // mirror image of above code
            NodeType *y = x->parent->parent->left;
            if (y->color == RED) {

                // uncle is RED
                x->parent->color = BLACK;
                y->color = BLACK;
                x->parent->parent->color = RED;
                x = x->parent->parent;
            } else {

                // uncle is BLACK
                if (x == x->parent->left) {
                    x = x->parent;
                    rotateRight(rbt, x);
                }
                x->parent->color = BLACK;
                x->parent->parent->color = RED;
                rotateLeft(rbt, x->parent->parent);
            }
        }
    }
    rbt->root->color = BLACK;
}

RbtStatus rbtInsert(RbtHandle h, void *key, void *val) {
    NodeType *current, *parent, *x;
    RbtType *rbt = h;

    // allocate node for data and insert in tree

    // find future parent
    current = rbt->root;
    parent = 0;
    while (current != SENTINEL) {
        int rc = rbt->compare(key, current->key);
        if (rc == 0)
            return RBT_STATUS_DUPLICATE_KEY;
        parent = current;
        current = (rc < 0) ? current->left : current->right;
    }

    // setup new node
    if ((x = malloc (sizeof(*x))) == 0)
        return RBT_STATUS_MEM_EXHAUSTED;
    x->parent = parent;
    x->left = SENTINEL;
    x->right = SENTINEL;
    x->color = RED;
    x->key = key;
    x->val = val;

    // insert node in tree
    if(parent) {
        if(rbt->compare(key, parent->key) < 0)
            parent->left = x;
        else
            parent->right = x;
    } else {
        rbt->root = x;
    }

    insertFixup(rbt, x);

    return RBT_STATUS_OK;
}

void deleteFixup(RbtType *rbt, NodeType *x) {

    // maintain red-black tree balance after deleting node x

    while (x != rbt->root && x->color == BLACK) {
        if (x == x->parent->left) {
            NodeType *w = x->parent->right;
            if (w->color == RED) {
                w->color = BLACK;
                x->parent->color = RED;
                rotateLeft (rbt, x->parent);
                w = x->parent->right;
            }
            if (w->left->color == BLACK && w->right->color == BLACK) {
                w->color = RED;
                x = x->parent;
            } else {
                if (w->right->color == BLACK) {
                    w->left->color = BLACK;
                    w->color = RED;
                    rotateRight (rbt, w);
                    w = x->parent->right;
                }
                w->color = x->parent->color;
                x->parent->color = BLACK;
                w->right->color = BLACK;
                rotateLeft (rbt, x->parent);
                x = rbt->root;
            }
        } else {
            NodeType *w = x->parent->left;
            if (w->color == RED) {
                w->color = BLACK;
                x->parent->color = RED;
                rotateRight (rbt, x->parent);
                w = x->parent->left;
            }
            if (w->right->color == BLACK && w->left->color == BLACK) {
                w->color = RED;
                x = x->parent;
            } else {
                if (w->left->color == BLACK) {
                    w->right->color = BLACK;
                    w->color = RED;
                    rotateLeft (rbt, w);
                    w = x->parent->left;
                }
                w->color = x->parent->color;
                x->parent->color = BLACK;
                w->left->color = BLACK;
                rotateRight (rbt, x->parent);
                x = rbt->root;
            }
        }
    }
    x->color = BLACK;
}

RbtStatus rbtErase(RbtHandle h, RbtIterator i) {
    NodeType *x, *y;
    RbtType *rbt = h;
    NodeType *z = i;

    if (z->left == SENTINEL || z->right == SENTINEL) {
        // y has a SENTINEL node as a child
        y = z;
    } else {
        // find tree successor with a SENTINEL node as a child
        y = z->right;
        while (y->left != SENTINEL) y = y->left;
    }

    // x is y's only child
    if (y->left != SENTINEL)
        x = y->left;
    else
        x = y->right;

    // remove y from the parent chain
    x->parent = y->parent;
    if (y->parent)
        if (y == y->parent->left)
            y->parent->left = x;
        else
            y->parent->right = x;
    else
        rbt->root = x;

    if (y != z) {
        z->key = y->key;
        z->val = y->val;
    }


    if (y->color == BLACK)
        deleteFixup (rbt, x);

    free (y);

    return RBT_STATUS_OK;
}

RbtIterator rbtNext(RbtHandle h, RbtIterator it) {
    RbtType *rbt = h;
    NodeType *i = it;

    if (i->right != SENTINEL) {
        // go right 1, then left to the end
        for (i = i->right; i->left != SENTINEL; i = i->left);
    } else {
        // while you're the right child, chain up parent link
        NodeType *p = i->parent;
        while (p && i == p->right) {
            i = p;
            p = p->parent;
        }

        // return the "inorder" node
        i = p;
    }
    return i != SENTINEL ? i : NULL;
}

RbtIterator rbtBegin(RbtHandle h) {
    RbtType *rbt = h;

    // return pointer to first value
    NodeType *i;
    for (i = rbt->root; i->left != SENTINEL; i = i->left);
    return i != SENTINEL ? i : NULL;
}

RbtIterator rbtEnd(RbtHandle h) {
   // return pointer to one past last value
   return NULL;
}

void rbtKeyValue(RbtHandle h, RbtIterator it, void **key, void **val) {
    NodeType *i = it;

    *key = i->key;
    *val = i->val;
}


void *rbtFind(RbtHandle h, void *key) {
    RbtType *rbt = h;

    NodeType *current;
    current = rbt->root;
    while(current != SENTINEL) {
        int rc = rbt->compare(key, current->key);
        if (rc == 0) return current;
        current = (rc < 0) ? current->left : current->right;
    }
    return NULL;
 #include <stdio.h>
#include <stdlib.h>
#include "rbtr.h"

int compare(void *a, void *b) {
    return *(int *)a - *(int *)b;
}

int main(int argc, char **argv) {
    int maxnum, ct;

    // command-line:
    //
    //   rbtmain 2000
    //       process 2000 records

    RbtIterator i;
    RbtHandle h;
    RbtStatus status;

    maxnum = atoi(argv[1]);

    // obtain handle to red-black tree
    h = rbtNew(compare);

    printf("maxnum = %d\n", maxnum);
    for (ct = maxnum; ct; ct--) {
        int key = rand() % 90 + 1;

        if ((i = rbtFind(h, &key)) != rbtEnd(h)) {
            // found an existing node
            void *keyp, *valuep;

            // get key-value pointers
            rbtKeyValue(h, i, &keyp, &valuep);

            // check to see they contain correct data
            if (*(int *)keyp != key) printf("fail keyp\n");
            if (*(int *)valuep != 10*key) printf("fail valuep\n");

            // erase node in red-black tree
            status = rbtErase(h, i);
            if (status) printf("fail: status = %d\n", status);

            // free the pointers allocated by main
            free(keyp); free(valuep);

        } else {
            // create a new node
            int *keyp, *valuep;

            // allocate key/value data
            keyp = (int *)malloc(sizeof(int));
            valuep = (int *)malloc(sizeof(int));

            // initialize with values
            *keyp = key;
            *valuep = 10*key;

            // insert in red-black tree
            status = rbtInsert(h, keyp, valuep);
            if (status) printf("fail: status = %d\n", status);
        }
    }

    // output nodes in order
    for (i = rbtBegin(h); i != rbtEnd(h); i = rbtNext(h, i)) {
        void *keyp, *valuep;
        rbtKeyValue(h, i, &keyp, &valuep);
        printf("%d %d\n", *(int *)keyp, *(int *)valuep);
    }

    // delete my allocated memory
    for (i = rbtBegin(h); i != rbtEnd(h); i = rbtNext(h, i)) {
        void *keyp, *valuep;
        rbtKeyValue(h, i, &keyp, &valuep);
        free(keyp); free(valuep);
    }

    // delete red-black tree
    rbtDelete(h);

    return 0;
}
}
