红黑树C实现

Share 
红黑树是一门玄学，想活着就千万不要想我一样去碰他（吐出一口老血）

这个轮子是我到目前写的最复杂的一个数据结构的轮子，没有之一。

具体关于红黑树的文章我会在过几天整理出来。

先看代码吧，里面有注释。

redBalckTreeNode.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
43
44
45
46
47
48
49
50
//
//  redBalckTreeNode.h
//  redBlackTree
//
//  Created by SaberDa on 2016/11/15.
//  Copyright © 2016年 SaberDa. All rights reserved.
//

#ifndef redBalckTreeNode_h
#define redBalckTreeNode_h

#include <stdio.h>
#include "redBlackTree.h"

bool NodeisRed(const Node *x);
Node *NodeMinbyKey(Node *x);
Value *NodeGet(Node *x, Key key);
int NodeSize(const Node *x);
Node *NodeMaxbyKey(Node *x);

Node *NodeRotateRight(Node *h);
Node *NodeRotateLeft(Node *h);

void NodeFlipColors(Node *h);

Node *ModeMoveRedLeft(Node *h);
Node *NodeMoveRedRight(Node *h);

Node *NodeBalance(Node *h);

Node *NodeDeleteMax(Node *h);
Node *NodeDeleteMin(Node *h);

Node *NodeRemove(Node *h, Key key);
Node *NodePut(Node *h, Key key, Value val);

int NodeHeight(Node *x);
Node *NodeFloor(Node *x, Key key);
Node *NodeCeiling(Node *x, Key key);
Node *NodeSelect(Node *x, int k);

int NodeRank(Node *x, Key key);
void NodeKeys(Node *x, keyList **queue, const Key low, const Key high);

bool NodeTestisBST(const Node *x, const Key *min, const Key *max);
bool NodeTestisSizeConsistant(const Node *x);
bool NodeTestis23(const Node *x, const Node *root);
bool NodeTestisBalanced(const Node *x, int black);

#endif /* redBalckTreeNode_h */

redBalckTreeNode.c

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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
//
//  redBalckTreeNode.c
//  redBlackTree
//
//  Created by SaberDa on 2016/11/15.
//  Copyright © 2016年 SaberDa. All rights reserved.
//

#include "redBalckTreeNode.h"
#include <string.h>
#include <stdlib.h>

#define MAX(a,b) (a > b) ? a : b

#ifdef ASSERTS
#include <assert.h>
#else
#define assert(X) {/* Asserts are unused unless defined */}
#endif // ASSERTS

#pragma region Private NODE_* functions

//释放该结点内存
void NodeFree(Node **x) {
    free((*x) -> value);
    (*x) -> value = NULL;
    free((*x));
    (*x) = NULL;
}

bool NodeisRed(const Node *x) {
    if (x == NULL) {
        return false;
    }
    return x -> color == RED;
}

//求最小键值
Node *NodeMinbyKey(Node *x) {
    assert(x != NULL);
    if (x -> lChild == NULL) {
        return x;
    }
    return NodeMinbyKey(x -> lChild);
}

//求最大键值
Node *NodeMaxbyKey(Node *x) {
    assert(x != NULL);
    if (x -> rChild == NULL) {
        return x;
    }
    return NodeMaxbyKey(x -> rChild);
}

//获取该结点键值，没有返回NULL
Value *NodeGet(Node *x, Key key) {
    while (x != NULL) {
        if (key < x -> key) {
            x = x ->lChild;
        } else if (key > x ->key) {
            x = x -> rChild;
        } else
            return &(x -> value);
    }
    return NULL;
}

//求以x为根结点的结点数量；如果x为NULL，则返回0
int NodeSize(const Node *x) {
    if (x == NULL) {
        return 0;
    }
    return x -> size;
}

//右旋转
Node *NodeRotateRight(Node *h) {
    assert((h != NULL) && NodeisRed(h -> lChild));
    Node *x = h -> lChild;
    h -> lChild = x -> rChild;
    x -> rChild = h;
    x -> color = x -> rChild -> color;
    x -> rChild -> color = RED;
    x -> size = h -> size;
    h -> size = NodeSize(h -> lChild) + NodeSize(h -> rChild) + 1;
    return x;
}

//左旋转
Node *NodeRotateLeft(Node *h) {
    assert((h != NULL) && NodeisRed(h -> rChild));
    Node *x = h -> rChild;
    x -> lChild = h;
    x -> color = x -> lChild -> color;
    x -> lChild -> color = RED;
    x -> size = h -> size;
    h -> size = NodeSize(h -> lChild) + NodeSize(h -> rChild) + 1;
    return x;
}

//将根结点与其孩子结点的颜色转换
void NodeFlipColors(Node *h) {
    //根结点h必须与其孩子结点颜色不同
    assert((h != NULL) && (h -> lChild != NULL) && (h -> rChild != NULL));
    assert((NodeisRed(h) && !NodeisRed(h -> lChild) && NodeisRed(h -> rChild)) || (!NodeisRed(h) && NodeisRed(h -> lChild) && NodeisRed(h -> rChild)));
    h -> color = !(h -> color);
    h -> lChild -> color = !(h -> lChild -> color);
    h -> rChild -> color = !(h -> rChild -> color);
}

//假定h为红的，h.lChild 和 h.lChild.lChild 都是黑的，将其中一个变成红的
Node *ModeMoveRedLeft(Node *h) {
    assert(h != NULL);
    assert(NodeisRed(h) && !NodeisRed(h -> lChild) && !NodeisRed(h -> lChild -> lChild));
    NodeFlipColors(h);
    if (NodeisRed(h -> rChild -> lChild)) {
        h -> rChild = NodeRotateRight(h -> rChild);
        h = NodeRotateLeft(h);
        NodeFlipColors(h);
    }
    return h;
}

//假定h为红的，h.rChild 和 h.rChild.rChild 都是黑的，将其中一个变成红的
Node *NodeMoveRedRight(Node *h) {
    assert(h != NULL);
    assert(NodeisRed(h) && !NodeisRed(h -> rChild) && !NodeisRed(h -> rChild -> lChild));
    NodeFlipColors(h);
    if (NodeisRed(h -> lChild -> lChild)) {
        h = NodeRotateRight(h);
        NodeFlipColors(h);
    }
    return h;
}

//确保红黑树性质不变
Node *NodeBalance(Node *h) {
    assert(h != NULL);
    if (NodeisRed(h -> rChild)) {
        h = NodeRotateLeft(h);
    }
    if (NodeisRed(h -> lChild) && NodeisRed(h -> lChild -> lChild)) {
        h = NodeRotateRight(h);
    }
    if (NodeisRed(h -> lChild) && NodeisRed(h -> rChild)) {
        NodeFlipColors(h);
    }
    h -> size = NodeSize(h -> lChild) + NodeSize(h -> rChild) + 1;
    return h;
}

//删除以h为根结点的树中最大的键值
Node *NodeDeleteMax(Node *h) {
    if (NodeisRed(h -> lChild)) {
        h = NodeMoveRedRight(h);
    }
    if (h -> rChild == NULL) {
        NodeFree(&h);
        return NULL;
    }
    if (!NodeisRed(h -> rChild) && !NodeisRed(h -> rChild -> lChild)) {
        h = NodeMoveRedRight(h);
    }
    h -> rChild = NodeDeleteMax(h -> rChild);
    return NodeBalance(h);
}

//删除以h为根结点的树中最小的键值
Node *NodeDeleteMin(Node *h) {
    if (h -> lChild == NULL) {
        NodeFree(&h);
        return h;
    }
    if (!NodeisRed(h -> lChild) && !NodeisRed(h -> lChild -> lChild)) {
        h = NodeRotateLeft(h);
    }
    h -> lChild = NodeDeleteMin(h -> lChild);
    return NodeBalance(h);
}

//删除给定键值的结点
Node *NodeRemove(Node *h, Key key) {
    assert(NodeGet(h, key) != NULL);
    if (key < h -> key) {
        if (!NodeisRed(h -> lChild) && !NodeisRed(h -> lChild -> lChild)) {
            h = NodeRotateLeft(h);
        }
        h -> lChild = NodeRemove(h -> lChild, key);
    } else {
        if (NodeisRed(h -> lChild)) {
            h = NodeRotateRight(h);
        }
        if ((key == h -> key) && (h -> rChild == NULL)) {
            NodeFree(&h);
            return NULL;
        }
        if (!NodeisRed(h -> rChild) && !NodeisRed(h -> rChild -> lChild)) {
            h = NodeMoveRedRight(h);
        }
        if (key == h ->key) {
            Node *x = NodeMinbyKey(h -> rChild);
            h -> key = x -> key;
            //x在外部操作要释放：确保其数据域被释放
            Value temp = h -> value;
            h -> value = x -> value;
            x -> value = temp;
            h -> rChild = NodeDeleteMin(h -> rChild);
        } else {
            h -> rChild = NodeRemove(h -> rChild, key);
        }
    }
    return NodeBalance(h);
}

//插入
Node *NodePut(Node *h, Key key, Value val) {
    if (h == NULL) {
        return createNode(key, val, RED, 1);
    }
    if (key < h -> key) {
        h -> lChild = NodePut(h -> lChild, key, val);
    } else if (key > h -> key) {
        h -> rChild = NodePut(h -> rChild, key, val);
    } else {
        //以一个新的数据替代
        memcmp(h -> value, val, sizeof(Value));
    }
    //修正树
    if (NodeisRed(h -> rChild) && !NodeisRed(h -> lChild)) {
        h = NodeRotateLeft(h);
    }
    if (NodeisRed(h -> lChild) && NodeisRed(h -> lChild -> lChild)) {
        h = NodeRotateRight(h);
    }
    if (NodeisRed(h -> lChild) && NodeisRed(h -> rChild)) {
        NodeFlipColors(h);
    }
    h -> size = NodeSize(h -> lChild) + NodeSize(h -> rChild) + 1;
    return h;
}

int NodeHeight(Node *x) {
    if (x == NULL) {
        return  -1;
    }
    return (1 + (MAX(NodeSize(x -> lChild), NodeSize(x -> rChild))));
}

//根的子树中x小于或等于给定键的最大关键值
Node *NodeFloor(Node *x, Key key) {
    if (x == NULL) {
        return NULL;
    }
    if (key == x -> key) {
        return x;
    }
    if (key < x -> key) {
        return NodeFloor(x -> lChild, key);
    }
    Node *t = NodeFloor(x -> rChild, key);
    if (t != NULL) {
        return t;
    } else {
        return x;
    }
}

//根的子树中x小于或等于给定键的最小关键值
Node *NodeCeiling(Node *x, Key key) {
    if (x == NULL) {
        return NULL;
    }
    if (key == x -> key) {
        return x;
    }
    if (key > x -> key) {
        return NodeCeiling(x -> rChild, key);
    }
    Node *t = NodeCeiling(x -> lChild, key);
    if (t != NULL) {
        return t;
    } else {
        return x;
    }
}

//the key of rank k in the subtree rooted at x
Node *NodeSelect(Node *x, int k) {
    assert(x != NULL);
    assert(k >= 0 && k < NodeSize(x));
    int t = NodeSize(x -> lChild);
    if (t > k) {
        return NodeSelect(x -> lChild, k);
    }
    if (t < k) {
        return NodeSelect(x -> rChild, k);
    }
    return x;
}

//求秩
int NodeRank(Node *x, Key key) {
    if (x == NULL) {
        return 0;
    }
    if (key < x -> key) {
        return NodeRank(x -> lChild, key);
    } else if (key > x -> key) {
        return (1 + NodeSize(x -> rChild) + NodeRank(x -> lChild, key));
    } else {
        return NodeSize(x -> lChild);
    }
}

//将low与high之间的结点入队
void NodeKeys(Node *x, keyList **queue, const Key low, const Key high) {
    if (x == NULL || queue == NULL) {
        return;
    }
    if (low < x -> key) {
        NodeKeys(x -> lChild, queue, low, high);
    }
    if (low <= x -> key && high >= x -> key) {
        keyList *next = (keyList *)calloc(1, sizeof(keyList));
        (*queue) -> node = x;
        (*queue) -> next = next;
        (*queue) = next;
    }
    if (high > x -> key) {
        NodeKeys(x -> rChild, queue, low, high);
    }
}

#pragma region Node Tests

bool NodeTestisBST(const Node *x, const Key *min, const Key *max) {
    if (x == NULL) {
        return true;
    }
    if ((min != NULL) && (x -> key <= *min)) {
        return false;
    }
    if ((max != NULL) && (x -> key >= *max)) {
        return false;
    }
    return NodeTestisBST(x -> lChild, min, &(x -> key)) && NodeTestisBST(x -> rChild, &(x -> key), max);
}

bool NodeTestisSizeConsistant(const Node *x) {
    if (x == NULL) {
        return true;
    }
    if (x -> size != (NodeSize(x -> lChild) + NodeSize(x -> rChild) + 1)) {
        return false;
    }
    return NodeTestisSizeConsistant(x -> lChild) && NodeTestisSizeConsistant(x -> rChild);
}

bool NodeTestis23(const Node *x, const Node *root) {
    if (x == NULL) {
        return true;
    }
    if (NodeisRed(x -> rChild)) {
        return false;
    }
    if (x != root && NodeisRed(x) && NodeisRed(x -> rChild)) {
        return false;
    }
    return NodeTestis23(x -> lChild, root) && NodeTestis23(x -> rChild, root);
}

bool NodeTestisBalanced(const Node *x, int black) {
    if (x == NULL) {
        return black = 0;
    }
    if (!NodeisRed(x)) {
        black--;
    }
    return NodeTestisBalanced(x -> lChild, black) && NodeTestisBalanced(x -> rChild, black);
}

redBlackTree.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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
//
//  redBlackTree.h
//  redBlackTree
//
//  Created by SaberDa on 2016/11/15.
//  Copyright © 2016年 SaberDa. All rights reserved.
//

#ifndef redBlackTree_h
#define redBlackTree_h

#include <stdio.h>
#include <stdbool.h>

typedef char* Value;
typedef int Key;

const static bool RED = 1;
const static bool BLACK = 0;

typedef struct _Node {
    
    Value value;
    struct _Node *lChild, *rChild;
    bool color;
    Key key;
    int size;
    
} Node;

typedef struct _keyList {
    
    Node *node;
    struct _keyList *next;
    
} keyList;

#define INIT_KeyList(X) KeyList X = { .node = NULL,	.next = NULL }

typedef struct _redBlackBST {
    
    Node *root;
    
} redBlackBST;

void applyKeyValue(Node *node, Key key, Value val);
void KL_forEach(redBlackBST *self, keyList *list, void(* func)(redBlackBST *, Node *));
Node *createNode(Key _key, Value _value, bool _color, int _size);

void RBTDeleteMax(redBlackBST *self);
void RBTRemove(redBlackBST *self, Key key);
void RBTPut(redBlackBST *self, Key key, Value val);

Value *RBTGet(const redBlackBST *self, Key key);
int RBTSize(const redBlackBST *self);
bool RBTisEmpty(const redBlackBST *self);
bool RBTContains(const redBlackBST *self, Key key);

const Node *RBTMinbyKey(const redBlackBST *self);
const Node *RBTMaxbyKey(const redBlackBST *self);

int RBTHeight(const redBlackBST *self);
Node *RBTFloor(const redBlackBST *self, Key key);
Node *RBTCeiling(const redBlackBST *self, Key key);
Key RBTSelect(const redBlackBST *self, int k);

int RBTRank(const redBlackBST *self, Key key);

keyList *RBTKeys(const redBlackBST *self);
keyList *RBTKeyRange(const redBlackBST *self, const Key low, const Key high);
int RBTRangeSize(const redBlackBST *self, Key low, Key high);

//bool RBTSelfCheck(const redBlackBST *self);
bool RBTFree(redBlackBST *self);

#endif /* redBlackTree_h */

redBlackTree.c

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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
//
//  redBlackTree.c
//  redBlackTree
//
//  Created by SaberDa on 2016/11/15.
//  Copyright © 2016年 SaberDa. All rights reserved.
//

#include "redBlackTree.h"
#include "redBalckTreeNode.h"
#include <string.h>
#include <stdio.h>
#include <stdlib.h>

#define MAX(a,b) (a > b) ? a : b

#ifdef ASSERTS
#include <assert.h>
#else
#define assert(X) {/* Asserts are unused unless defined */}
#endif // ASSERTS

void applyKeyValue(Node *node, Key key, Value val) {
    node -> key = key;
    char *nodeBuffer = (char*)calloc(1, strlen(val));
    node -> value = nodeBuffer;
    sprintf(node -> value, "%s", val);
}

void KL_forEach(redBlackBST *self, keyList *list, void(*func)(redBlackBST*, Node*)) {
    Node *node;
    while (list && list -> node) {
        node = list -> node;
        func(self, node);
        keyList *toRelease = list;
        list = list -> next;
        free(toRelease);
    }
    free(list);
}

Node *createNode(Key _key, Value _value, bool _color, int _size) {
    Node *node = calloc(1, sizeof(Node));
    memset(node, 0, sizeof(Node));
    Node structNode = {
        .key = _key,
        .value = _value,
        .color = _color,
        .size = _size,
        .lChild = NULL,
        .rChild = NULL
    };
    applyKeyValue(&structNode, _key, _value);
    memcpy(node, &structNode, sizeof(Node));
    return (Node *)node;
}

/**
    基本二叉树函数
 */

Value *RBTGet(const redBlackBST *self, Key key) {
    if (key == NULL) {
        printf("argument to get() is NULL\n");
        exit(EXIT_FAILURE);
    }
    return NodeGet(self -> root, key);
}

int RBTSize(const redBlackBST *self) {
    return NodeSize(self -> root);
}

bool RBTisEmpty(const redBlackBST *self) {
    return self -> root == NULL;
}

bool RBTContains(const redBlackBST *self, Key key) {
    return RBTGet(self, key) != NULL;
}

const Node *RBTMinbyKey(const redBlackBST *self) {
    if (RBTisEmpty(self)) {
        printf("called max() with empty symbol table");
        exit(EXIT_FAILURE);
    }
    return NodeMinbyKey(self -> root);
}
const Node *RBTMaxbyKey(const redBlackBST *self) {
    if (RBTisEmpty(self)) {
        printf("called max() with empty symbol table");
        exit(EXIT_FAILURE);
    }
    return NodeMaxbyKey(self -> root);
}

/**
    红黑树删除
 */

//移去最大值
void RBTDeleteMax(redBlackBST *self) {
    if (RBTisEmpty(self)) {
        printf("BST underflow");
        exit(EXIT_FAILURE);
    }
    //如果两个孩子都是黑的，将父结点设为红
    if (!NodeisRed(self -> root -> lChild) && !NodeisRed(self -> root -> rChild)) {
        self -> root -> color = RED;
    }
    self -> root = NodeDeleteMax(self -> root);
    if (!RBTisEmpty(self)) {
        self -> root -> color = BLACK;
    }
    assert(RBTSelfCheck(self));
}

//移去特定值
void RBTRemove(redBlackBST *self, Key key) {
    if (key == NULL) {
        printf("argument to remove() is NULL");
        exit(EXIT_FAILURE);
    }
    //如果两个孩子都是黑的，将父结点设为红
    if (!NodeisRed(self -> root -> lChild) && !NodeisRed(self -> root -> rChild)) {
        self -> root -> color = RED;
    }
    self -> root = NodeRemove(self -> root, key);
    if (!RBTisEmpty(self)) {
        self -> root -> color = BLACK;
    }
    assert(RBTSelfCheck(self));
}

//红黑树插入
void RBTPut(redBlackBST *self, Key key, Value val) {
    if (key == NULL) {
        printf("argument to remove() is NULL");
        exit(EXIT_FAILURE);
    }
    if (val == NULL) {
        RBTRemove(self, key);
        return ;
    }
    self -> root = NodePut(self -> root, key, val);
    self -> root -> color = BLACK;
    assert(RBTSelfCheck(self));
}

//求数的深度
int RBTHeight(const redBlackBST *self) {
    return NodeHeight(self -> root);
}

//下面函数功能看redBalckTreeNode.c

Node *RBTFloor(const redBlackBST *self, Key key) {
    if (key == NULL) {
        printf("argument to remove() is NULL");
        exit(EXIT_FAILURE);
    }
    if (RBTisEmpty(self)) {
        printf("called RBTFloor() with empty symbol table");
        exit(EXIT_FAILURE);
    }
    Node *x = NodeFloor(self -> root, key);
    if (x == NULL) {
        return NULL;
    } else {
        return x;
    }
}

Node *RBTCeiling(const redBlackBST *self, Key key) {
    if (key == NULL) {
        printf("argument to remove() is NULL");
        exit(EXIT_FAILURE);
    }
    if (RBTisEmpty(self)) {
        printf("called RBTCeiling() with empty symbol table");
        exit(EXIT_FAILURE);
    }
    Node *x = NodeCeiling(self -> root, key);
    if (x == NULL) {
        return NULL;
    } else {
        return x;
    }
}

Key RBTSelect(const redBlackBST *self, int k) {
    if (k < 0 || k > RBTSize(self)) {
        printf("Illegal arguement");
        exit(EXIT_FAILURE);
    }
    Node *x = NodeSelect(self -> root, k);
    return x -> key;
}

int RBTRank(const redBlackBST *self, Key key) {
    if (key == NULL) {
        printf("argument to rank() is NULL");
        exit(EXIT_FAILURE);
    }
    return NodeRank(self -> root, key);
}

keyList *RBTKeys(const redBlackBST *self) {
    if (RBTisEmpty(self)) {
        return NULL;
    }
    return RBTKeyRange(self, RBTMinbyKey(self) -> key, RBTMaxbyKey(self) -> key);
}
keyList *RBTKeyRange(const redBlackBST *self, const Key low, const Key high) {
    if (low == NULL) {
        printf("first argument to keys() is NULL");
        exit(EXIT_FAILURE);
    }
    if (high == NULL) {
        printf("second argument to keys() is NULL");
        exit(EXIT_FAILURE);
    }
    keyList *list = (keyList *)calloc(1, sizeof(keyList));
    keyList *end = list;
    NodeKeys(self -> root, &end, low, high);
    return list;
}

int RBTRangeSize(const redBlackBST *self, Key low, Key high) {
    if (low == NULL) {
        printf("first argument to keys() is NULL");
        exit(EXIT_FAILURE);
    }
    if (high == NULL) {
        printf("second argument to keys() is NULL");
        exit(EXIT_FAILURE);
    }
    if (low < high) {
        return 0;
    }
    if (RBTContains(self, high)) {
        return RBTRank(self, high) - RBTRank(self, low) + 1;
    }
    return RBTRank(self, high) - RBTRank(self, low);
}

bool RBTFree(redBlackBST *self) {
    keyList *list = RBTKeys(self);
    while (list && list->node) {
        keyList* release = list;
        list = list -> next;
        free(release -> node -> value);
        release -> node -> value = NULL;
        free(release -> node);
        release -> node -> lChild = NULL;
        release -> node -> rChild = NULL;
        release -> node = NULL;
        free(release);
        release = NULL;
    }
    self -> root = NULL;
    free(list);
    return true;
}

bool RBTTestisBST(const redBlackBST *self) {
    return NodeTestisBST(self -> root, NULL, NULL);
}

bool RBTTestisSizeConsistent(const redBlackBST *self) {
    return NodeTestisSizeConsistant(self -> root);
}

bool RBTTestisRankConsistent(const redBlackBST *self) {
    int i = 0;
    for (; i < RBTSize(self); i++) {
        if (i != RBTRank(self, RBTSelect(self, i))) {
            return false;
        }
    }
    keyList *list = RBTKeys(self);
    Node *n;
    while (list && list -> node) {
        n = list -> node;
        if (n -> key != RBTSelect(self, RBTRank(self, n -> key))) {
            while (list -> next) {
                keyList *releasse = list;
                list = list -> next;
                free(releasse);
            }
            free(list);
            return false;
        }
        keyList *release = list;
        list = list -> next;
        free(release);
    }
    free(list);
    return true;
}

bool RBTTestis23(const redBlackBST *self) {
    return NodeTestis23(self -> root, self -> root);
}

bool RBTTestisBalanced(const redBlackBST *self) {
    int black = 0;
    Node *x = self -> root;
    while (x != NULL) {
        if (!NodeisRed(x)) {
            black++;
        }
    }
    return NodeTestisBalanced(self -> root, black);
}

main.c

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
//
//  main.c
//  redBlackTree
//
//  Created by SaberDa on 2016/11/15.
//  Copyright © 2016年 SaberDa. All rights reserved.
//

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include "redBlackTree.h"

void printNode(redBlackBST *self, Node *node) {
    printf("%d %s at %p => (%p)\n", node -> key, *RBTGet(self, node -> key), node, node -> value);
}


int main(int argc, const char * argv[]) {
    redBlackBST st = {
        .root = NULL
    };
    //输入
    //...
    RBTFree(&st);
    return 0;
}