--- /dev/null
+
+/*
+ * CS5600 University of Utah
+ * Charles McGarvey
+ * mcgarvey@eng.utah.edu
+ */
+
+#ifndef _RBTREE_H_
+#define _RBTREE_H_
+
+#include "common.h"
+
+
+#define RBTREE_BLACK (0)
+#define RBTREE_RED (1)
+
+
+/*
+ * A single node of the red-black tree.
+ */
+struct rbtree_node
+{
+ struct rbtree_node* parent;
+ struct rbtree_node* left;
+ struct rbtree_node* right;
+ char color;
+};
+typedef struct rbtree_node rbtree_node_t;
+
+/*
+ * Get a pointer to the data stored in a node.
+ */
+#define RBTREE_NODE_DATA(N) ((void*)((char*)N + sizeof(rbtree_node_t)))
+
+/*
+ * A pointer to the global sentinel node.
+ */
+extern rbtree_node_t* rbtree_sentinel;
+
+
+/*
+ * In order to search the tree, you need a function matching this protocol.
+ */
+typedef int (*rbtree_search_fn_t)(rbtree_node_t** np, void* data);
+
+
+/*
+ * The famous and well-loved red and black tree structure.
+ */
+struct rbtree
+{
+ rbtree_node_t* root;
+ size_t size;
+ rbtree_search_fn_t search;
+};
+typedef struct rbtree rbtree_t;
+
+/*
+ * Allocate a new red-black tree. It takes the size of the data to be stored
+ * in each node and a search function.
+ */
+rbtree_t* rbtree_alloc(size_t size, rbtree_search_fn_t search);
+
+/*
+ * Destroy a red-black tree, returning its memory to the allocator.
+ */
+void rbtree_destroy(rbtree_t* t);
+
+
+/*
+ * The common actions which can be invoked on a tree.
+ * These are O(logn) operations.
+ */
+rbtree_node_t* rbtree_delete(rbtree_t* t, void* data);
+rbtree_node_t* rbtree_insert(rbtree_t* t, void* data);
+rbtree_node_t* rbtree_search(rbtree_t* t, void* data);
+
+/*
+ * If you already have a pointer to a node, you can delete it directly.
+ * This is a O(1) operation.
+ */
+rbtree_node_t* rbtree_delete_node(rbtree_t* t, rbtree_node_t* n);
+
+
+/*
+ * Determine whether or not the tree is empty.
+ */
+INLINE_MAYBE
+bool rbtree_empty(rbtree_t* t)
+{
+ return (t->root == rbtree_sentinel);
+}
+
+/*
+ * Clear the tree of all of it's nodes.
+ */
+void rbtree_clear(rbtree_t* t);
+
+
+/*
+ * Get the node with the minimum data in the tree.
+ * This is a O(logn) operation.
+ */
+INLINE_MAYBE
+rbtree_node_t* rbtree_node_min(rbtree_node_t* n)
+{
+ while (n->left != rbtree_sentinel) {
+ n = n->left;
+ }
+ return n;
+}
+
+/*
+ * Get the node with the maximum data in the tree.
+ * This is a O(logn) operation.
+ */
+INLINE_MAYBE
+rbtree_node_t* rbtree_node_max(rbtree_node_t* n)
+{
+ while (n->right != rbtree_sentinel) {
+ n = n->right;
+ }
+ return n;
+}
+
+
+/*
+ * A function that can be used as a callback for handling tree data.
+ */
+typedef void (*rbtree_call_fn_t)(void* e);
+
+/*
+ * Call a function for each node in the tree, from smallest to greatest.
+ */
+void rbtree_call(const rbtree_t* t, rbtree_call_fn_t fn);
+
+
+#endif // _RBTREE_H_
+