-
Notifications
You must be signed in to change notification settings - Fork 0
/
stree.h
executable file
·44 lines (31 loc) · 1.02 KB
/
stree.h
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
/*
* Splay tree implementation
* Based on code in https://en.wikipedia.org/wiki/Splay_tree
*
* Students are welcome to borrow and adapt this code for any
* assignment in 15-213/18-213/15-513
*/
typedef long tkey_t;
typedef void (*free_fun_t)(void *r);
typedef struct node {
struct node *left, *right;
struct node *parent;
tkey_t key;
void *record; // Points to user data */
} node_t;
typedef struct {
node_t *root;
size_t node_count;
size_t comparison_count;
} tree_t;
tree_t *tree_new();
/* Delete all nodes in tree, applying free_fun to each record */
void tree_free(tree_t *tree, free_fun_t free_fun);
/* Insertion function returns false if already have key in tree */
bool tree_insert(tree_t *tree, tkey_t key, void *record);
void *tree_find(tree_t *tree, tkey_t key);
/* Find element with largest key <= given key */
void *tree_find_nearest(tree_t *tree, tkey_t key);
void *tree_remove(tree_t *tree, tkey_t key);
/* Print keys in tree */
void tree_show(tree_t *tree, bool tree_mode);