1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
|
/**********************************************************
* See the LICENSE file for copyright infomation. *
**********************************************************/
#pragma once
#ifdef __cplusplus
extern "C" {
#endif
/* CONVENTIONS: All data structures for red-black trees have the prefix */
/* "rb_" to prevent name conflicts. */
/* */
/* Function names: Each word in a function name begins with */
/* a capital letter. An example funcntion name is */
/* CreateRedTree(a,b,c). Furthermore, each function name */
/* should begin with a capital letter to easily distinguish */
/* them from variables. */
/* */
/* Variable names: Each word in a variable name begins with */
/* a capital letter EXCEPT the first letter of the variable */
/* name. For example, int newLongInt. Global variables have */
/* names beginning with "g". An example of a global */
/* variable name is gNewtonsConstant. */
typedef struct rb_red_blk_node {
void* key;
int red; /* if red=0 then the node is black */
struct rb_red_blk_node* left;
struct rb_red_blk_node* right;
struct rb_red_blk_node* parent;
} rb_red_blk_node;
/* Compare(a,b) should return 1 if *a > *b, -1 if *a < *b, and 0 otherwise */
/* Destroy(a) takes a pointer to whatever key might be and frees it accordingly */
typedef struct rb_red_blk_tree {
int (*Compare)(const void* a, const void* b);
void (*DestroyKey)(void* a);
/* A sentinel is used for root and for nil. These sentinels are */
/* created when RBTreeCreate is caled. root->left should always */
/* point to the node which is the root of the tree. nil points to a */
/* node which should always be black but has aribtrary children and */
/* parent and no key. The point of using these sentinels is so */
/* that the root and nil nodes do not require special cases in the code */
rb_red_blk_node* root;
rb_red_blk_node* nil;
} rb_red_blk_tree;
rb_red_blk_tree* RBTreeCreate(int (*CompFunc)(const void*, const void*),
void (*DestFunc)(void *));
rb_red_blk_node *RBTreeInsert(rb_red_blk_tree *, void *key);
void RBDelete(rb_red_blk_tree* , rb_red_blk_node* );
void RBTreeDestroy(rb_red_blk_tree*);
rb_red_blk_node* TreePredecessor(rb_red_blk_tree*,rb_red_blk_node*);
rb_red_blk_node* TreeSuccessor(rb_red_blk_tree*,rb_red_blk_node*);
rb_red_blk_node* RBExactQuery(rb_red_blk_tree*, void*);
#ifdef __cplusplus
}
#endif
|
