3 * CS5600 University of Utah
5 * mcgarvey@eng.utah.edu
14 #define RBTREE_BLACK (0)
15 #define RBTREE_RED (1)
19 * A single node of the red-black tree.
23 struct rbtree_node
* parent
;
24 struct rbtree_node
* left
;
25 struct rbtree_node
* right
;
28 typedef struct rbtree_node rbtree_node_t
;
31 * Get a pointer to the data stored in a node.
33 #define RBTREE_NODE_DATA(N) ((void*)((char*)N + sizeof(rbtree_node_t)))
36 * A pointer to the global sentinel node.
38 extern rbtree_node_t
* rbtree_sentinel
;
42 * In order to search the tree, you need a function matching this protocol.
44 typedef int (*rbtree_search_fn_t
)(rbtree_node_t
** np
, void* data
);
48 * The famous and well-loved red and black tree structure.
54 rbtree_search_fn_t search
;
56 typedef struct rbtree rbtree_t
;
59 * Allocate a new red-black tree. It takes the size of the data to be stored
60 * in each node and a search function.
62 rbtree_t
* rbtree_alloc(size_t size
, rbtree_search_fn_t search
);
65 * Destroy a red-black tree, returning its memory to the allocator.
67 void rbtree_destroy(rbtree_t
* t
);
71 * The common actions which can be invoked on a tree.
72 * These are O(logn) operations.
74 rbtree_node_t
* rbtree_delete(rbtree_t
* t
, void* data
);
75 rbtree_node_t
* rbtree_insert(rbtree_t
* t
, void* data
);
76 rbtree_node_t
* rbtree_search(rbtree_t
* t
, void* data
);
79 * If you already have a pointer to a node, you can delete it directly.
80 * This is a O(1) operation.
82 rbtree_node_t
* rbtree_delete_node(rbtree_t
* t
, rbtree_node_t
* n
);
86 * Determine whether or not the tree is empty.
89 bool rbtree_empty(rbtree_t
* t
)
91 return (t
->root
== rbtree_sentinel
);
95 * Clear the tree of all of its nodes.
97 void rbtree_clear(rbtree_t
* t
);
101 * Get the node with the minimum data in the tree.
102 * This is a O(logn) operation.
105 rbtree_node_t
* rbtree_node_min(rbtree_node_t
* n
)
107 while (n
->left
!= rbtree_sentinel
) {
114 * Get the node with the maximum data in the tree.
115 * This is a O(logn) operation.
118 rbtree_node_t
* rbtree_node_max(rbtree_node_t
* n
)
120 while (n
->right
!= rbtree_sentinel
) {
128 * A function that can be used as a callback for handling tree data.
130 typedef void (*rbtree_call_fn_t
)(void* e
);
133 * Call a function for each node in the tree, from smallest to greatest.
135 void rbtree_call(const rbtree_t
* t
, rbtree_call_fn_t fn
);