Turbak所写。因为时间关系，插入算法只是实现了非CLR算法。删除算法我也不知道叫什么名字(文献里没有讲)。但是删除结果依旧符合红黑树。

1. /*
2. * create RBNode class for construction RBTree
3. * create by chico chen
4. * date: 2008/09/04
5. * 如需转载注明出处
6. */
1. template< class T>
7. #define RED 0
8. #define BLACK 1
9. class RBNode
10. {
11. public :
1. T data;
12. RBNode* left;
13. RBNode* right;
14. RBNode* parent;
15. int color;
1. RBNode(T& data)
16. {
17. this ->data = data;
18. left = NULL;
19. right = NULL;
20. parent = NULL;
21. color = RED;
22. }
23. RBNode(T& data, RBNode* left, RBNode* right, RBNode* parent)
24. {
25. this ->data = data;
26. this ->left = left;
27. this ->right = right;
28. this ->parent = parent;
29. color = RED;
30. }
1. ~RBNode()
31. {
32. this ->left = this ->right = this ->parent = NULL;
33. color = RED;
34. }
35. };

1. /*
2. * this is red-black-tree code
3. * this code is not efficent in inserting
4. * create by chico chen
5. * date: 2008/09/04
6. * 如需转载注明出处
7. */
1. #include “RBNode.h”
1. template< class T>
8. class RBTree
9. {
1. private :
10. RBNode* root;
11. public :
12. RBTree()
13. {
14. this ->root = NULL;
15. }
16. ~RBTree()
17. {
18. clearTree( this ->root);
19. }
1. void print()
20. {
21. print( this ->root,0);
22. }
1. void insert(T& data)
23. {
1. RBNode* node = new RBNode(data);
24. insertNode(node);
25. }
1. void deleteKey(T& data)
26. {
27. deleteNode(data);
28. }
1. bool RBTreeTest()
29. {
30. try
31. {
32. getBlackNum( this ->root);
1. }
33. catch (…)
34. {
35. return false ;
36. }
37. return true ;
38. }
1. private :
1. void print(RBNode* subRoot, int num)
39. {
40. if (subRoot != NULL)
41. {
42. print(subRoot->right,num+3);
43. for ( int i = 0; i < num; i++)
44. {
45. cout << " " ;
46. }
47. cout << subRoot->data<< “(” <color<< “)” <<endl;
48. print(subRoot->left,num+3);
49. }
50. }
1. void clearTree(RBNode* subRoot)
51. {
52. if (subRoot == NULL)
53. return ;
54. clearTree(subRoot->left);
55. clearTree(subRoot->right);
56. delete subRoot;
57. }
1. RBNode* deleteMin(RBNode* subRoot,RBNode** parent)
58. {
1. while (subRoot != NULL)
59. {
60. parent = &subRoot;
61. if (subRoot->right != NULL)
62. {
63. subRoot = subRoot->right;
64. }
65. else
66. {
67. break ;
68. }
69. }
70. return subRoot;
71. }
1. void deleteNode(T& data)
72. {
73. if (root == NULL)
74. {
75. throw “Empty tree” ;
76. }
77. RBNode* subRoot = root;
78. while (subRoot != NULL)
79. {
80. if (subRoot->data > data)
81. {
82. subRoot = subRoot->left;
83. }
84. else if (subRoot->data < data)
85. {
86. subRoot = subRoot->right;
87. }
88. else
89. {
90. // find the data
91. // use the midOrder last one which is before the data node to replace
92. RBNode* inParent = subRoot;
93. RBNode* deleteNode = deleteMin(subRoot->left,&inParent);
94. RBNode* realDelete = NULL;
95. if (deleteNode != NULL)
96. {
97. subRoot->data = deleteNode->data; // copy
98. realDelete = deleteNode;
99. //real delete
100. }
101. else
102. {
103. realDelete = subRoot;
104. //real delete
105. }
106. if (realDelete->parent == NULL)
107. {
108. // delete root
109. delete realDelete;
110. }
111. else
112. {
113. // nothing at realDelete->right
114. RBNode* parent = realDelete->parent;
115. RBNode* subATree = NULL;
116. if (parent->left == realDelete)
117. {
118. parent->left = realDelete->left;
119. }
120. else
121. {
122. parent->right = realDelete->left;
123. }
124. subATree = realDelete->left;
125. if (realDelete->left != NULL)
126. {
127. realDelete->left->parent = parent;
128. }
129. int color = realDelete->color;
130. delete realDelete;
131. if (color == BLACK &&
132. (subATree == NULL || subATree->color == BLACK))
133. {
1. deleteRebuild(subATree,parent);
134. }
135. else if (color == BLACK && subATree->color == RED)
136. {
137. subATree->color = BLACK;
138. }
139. else
140. {
141. // do nothing
142. }
143. break ;
144. }
1. }
145. }
146. }
1. /* delete them if you want
147. //     x®                c®
148. //     /  /                /  /
149. //   a(b) b(b) -->     x(b)   b(b)
150. //         /            /
151. //        c®         a(b)
152. // LRL means L-> double black is at left, and rotate is RL
153. RBNode* LRLCaseA(RBNode* x)
154. {
155. RLRotate(x,x->right,x->right->left);
156. x->color = BLACK;
157. return x->parent;
1. }
1. //     x®                 b®
158. //     /  /                 /  /
159. //   a(b) b(b)   -->    x(b)   c(b)
160. //          /             /
161. //           c®       a(b)
162. RBNode* LLLCaseA(RBNode* x)
163. {
164. RRRotate(x,x->right);
165. x->color = BLACK;
166. x->parent->color = RED;
167. x->parent->right->color = BLACK;
168. return x->parent;
169. }
1. //     x®                b®
170. //     /  /                /  /
171. //   b(b) a(b)–>       c(b) x(b)
172. //    /                         /
173. //  c®                        a(b)
174. RBNode* RLLCaseA(RBNode* x)
175. {
176. LLRotate(x,x->left);
177. x->color = BLACK;
178. x->parent->color = RED;
179. x->parent->left->color = BLACK;
180. return x->parent;
181. }
1. //     x®                c®
182. //     /  /                /  /
183. //   b(b) a(b)–>       b(b) x(b)
184. //    /                         /
185. //    c®                        a(b)
186. RBNode* RLRCaseA(RBNode* x)
187. {
188. LRRotate(x,x->left,x->left->right);
189. x->color = BLACK;
1. return x->parent;
190. }
1. //     x®                     x(b)
191. //     /  /                     /  /
192. //   a(b) c(b)        ->     a(b) c®
193. //         /   /                  /   /
194. //        d(b)  e(b)            d(b)  e(b)
195. RBNode* LCaseB(RBNode* x)
196. {
197. x->color = BLACK;
198. x->right->color = RED;
199. }
1. //     x®                     x(b)
200. //     /  /                     /  /
201. //    c(b) a(b)       ->     c® a(b)
202. //   /   /                   /   /
203. // d(b)  e(b)              d(b)  e(b)
204. RBNode* RCaseB(RBNode* x)
205. {
206. x->color = BLACK;
207. x->left->color = RED;
208. }
1. //     x(b)                    c(b)
209. //     /  /                    /  /
210. //  a(b)  c®      ->     x®  e(b)
211. //        /   /             /  /
212. //       d(b)  e(b)      a(b)  d(b)
213. RBNode* LCaseC(RBNode* x)
214. {
215. RRRotate(x,x->right);
216. x->color = RED;
217. x->parent->color = BLACK;
218. return  x->parent;
219. }
1. //     x(b)                    c(b)
220. //     /  /                    /  /
221. //   c® a(b)     ->       d(b) x®
222. //   /   /                        /  /
223. //  d(b)  e(b)                  e(b) a(b)
224. RBNode* RCaseC(RBNode* x)
225. {
226. LLRotate(x,x->left);
227. x->color = RED;
228. x->parent->color = BLACK;
229. return  x->parent;
230. }
231. */
1. bool isBlack(RBNode* node)
232. {
1. if (node == NULL || node->color == BLACK)
233. return true ;
234. return false ;
235. }
1. void rebuild(RBNode* node)
236. {
237. if (node->parent->data > node->data)
238. {
239. node->parent->left = node;
240. }
241. else
242. {
243. node->parent->right = node;
244. }
245. }
1. /*
246. * There are 9 cases we will meet. The cases of the double black node at the right is ignored.
247. * (b) means black node, (db) means double black node, ® means red node
248. * 1.    (b)              2   (b)           3 (b)
249. *      /   /                 /  /            /  /
250. *    (db)  (b)             (db)  (b)       (db)  (b)
251. *          /  /                  / /             / /
252. *         (b)  (b)             ®  (b)        (b)  ®
253. * 4.    (b)              5   (b)           6 ®
254. *      /   /                 /  /            /  /
255. *    (db)  (b)             (db)  ®       (db)  (b)
256. *          /  /                  / /             / /
257. *         ®  ®             (b)  (b)        (b)  (b)
258. * 7.    ®              8   ®           9 ®
259. *      /   /                 /  /            /  /
260. *    (db)  (b)             (db)  (b)       (db)  (b)
261. *          /  /                  / /             / /
262. *         ®  (b)             (b)  ®        ®  ®
263. * case 1,6: up the black, if the parent is black then call the function again until the
264. * double black node is root, else blacken the parent.
265. * case 2,4,7,9: call the RLRotate, if the parent of the double
266. * node is black, up the black and call the function again, else
267. * blacken the parent.
268. * case 3,8: call the LLRotate, the same as case 2.
269. * case 5: call LLRotate, change as    (b)   then end.
270. *                                    /   /
271. *                                  (b)    (b)
272. *                                  / /
273. *                                (b)  ®
274. */
275. void deleteRebuild(RBNode* node,RBNode* parent)
276. {
277. if (parent == NULL)
278. {
279. // root, delete the black
280. return ;
281. }
282. if (parent->left == node)
283. {
284. RBNode* brother = parent->right;
285. RBNode* nephewA = brother->left;
286. RBNode* nephewB = brother->right;
1. if (isBlack(nephewA) && isBlack(nephewB) && isBlack(brother))
287. {
288. // case 1,6
289. brother->color = RED;
290. if (parent->color == BLACK)
291. {
292. deleteRebuild(parent,parent->parent);
293. }
294. else
295. {
296. parent->color = BLACK;
297. return ;
298. }
1. }
1. else if (!isBlack(nephewA))
299. {
300. // case 2,4,7,9
301. RBNode* tempRoot = RLRotate(parent,brother,nephewA);
302. // rebuild
303. rebuild(tempRoot);
1. }
304. else if (!isBlack(nephewB))
305. {
306. // case 3,8
307. RBNode* tempRoot = RRRotate(parent,brother);
308. rebuild(tempRoot);
309. nephewB->color = BLACK;
310. brother->color = RED;
311. }
312. else if (!isBlack(brother))
313. {
314. // case 5
315. RBNode* tempRoot = RRRotate(parent,brother);
316. rebuild(tempRoot);
317. brother->color = BLACK;
318. nephewA->color = RED;
319. return ;
320. }
321. else
322. {
323. // unknown
324. throw “none excption, about there is no red or black” ;
325. }
1. if (parent->color == BLACK)
326. {
327. // case 2,3,4
328. deleteRebuild(parent,parent->parent);
329. }
330. else
331. {
332. // case 7,8,9
333. parent->color = BLACK;
334. }
1. }
335. else
336. {
337. RBNode* brother = parent->left;
338. RBNode* nephewA = brother->right;
339. RBNode* nephewB = brother->left;
1. if (isBlack(nephewA) && isBlack(nephewB) && isBlack(brother))
340. {
341. brother->color = RED;
342. if (parent->color == BLACK)
343. {
344. deleteRebuild(parent,parent->parent);
345. }
346. else
347. {
348. parent->color = BLACK;
349. return ;
350. }
351. }
352. else if (!isBlack(nephewA))
353. {
354. RBNode* tempRoot = LRRotate(parent,brother,nephewA);
355. // rebuild
356. rebuild(tempRoot);
1. }
357. else if (!isBlack(nephewB))
358. {
359. RBNode* tempRoot = LLRotate(parent,brother);
360. rebuild(tempRoot);
361. nephewB->color = BLACK;
362. brother->color = RED;
363. }
364. else if (!isBlack(brother))
365. {
366. RBNode* tempRoot = LLRotate(parent,brother);
367. rebuild(tempRoot);
368. nephewA->color = RED;
369. brother->color = BLACK;
370. return ;
371. }
372. else
373. {
374. throw “none excption, about there is no red or black” ;
375. }
1. if (parent->color == BLACK)
376. {
377. deleteRebuild(parent,parent->parent);
378. }
379. else
380. {
381. parent->color = BLACK;
382. }
1. }
1. }
1. void insertNode(RBNode* node)
383. {
1. if (root == NULL)
384. {
385. root = node;
386. node->color = BLACK;
387. return ;
388. }
389. RBNode* subRoot = root;
390. RBNode* insertPoint = NULL;
391. while (subRoot!=NULL)
392. {
393. insertPoint = subRoot;
394. if (subRoot->data > node->data)
395. {
396. // insert left
397. subRoot = subRoot->left;
1. }
398. else if (subRoot->data < node->data)
399. {
400. subRoot = subRoot->right;
401. }
402. else
403. {
404. throw “same key” ;
405. }
406. }
1. if (insertPoint->data > node->data)
407. {
408. insertPoint->left = node;
409. }
410. else
411. {
412. insertPoint->right = node;
413. }
414. node->parent = insertPoint;
1. insertRebuild(node);
1. }
1. // return the subRoot
415. //        a                   b
416. //       /                  /   /
417. //      b        ->        c     a
418. //     /
419. //    c
420. RBNode* LLRotate(RBNode* a, RBNode* b)
421. {
422. if (b->right != NULL)
423. {
424. b->right->parent = a;
1. }
425. a->left = b->right;
426. b->right = a;
427. b->parent = a->parent;
428. a->parent = b;
429. return b;
430. }
1. // return the subRoot
431. //        a                      b
432. //          /                  /   /
433. //            b        ->     a     c
434. //              /
435. //                c
436. RBNode* RRRotate(RBNode* a, RBNode* b)
437. {
438. if (b->left != NULL)
439. {
440. b->left->parent = a;
1. }
441. a->right = b->left;
442. b->left = a;
443. b->parent = a->parent;
444. a->parent = b;
1. return b;
445. }
1. // return the subRoot
446. //        a                      c
447. //          /                  /   /
448. //            b        ->     a     b
449. //           /                 /
450. //          c                   d
451. //         /
452. //        d
453. RBNode* RLRotate(RBNode* a, RBNode* b, RBNode* c)
454. {
1. if (c->right != NULL)
455. {
456. c->right->parent = b;
1. }
457. b->left = c->right;
458. c->right = b;
459. b->parent = c;
460. if (c->left != NULL)
461. {
462. c->left->parent = a;
1. }
463. a->right = c->left;
464. c->left = a;
465. c->parent = a->parent;
466. a->parent = c;
1. return c;
467. }
1. // return the subRoot
468. //        a                      c
469. //       /                     /   /
470. //      b              ->     b     a
471. //       /                         /
472. //        c                       d
473. //         /
474. //          d
475. RBNode* LRRotate(RBNode* a, RBNode* b, RBNode* c)
476. {
477. if (c->left != NULL)
478. {
479. c->left->parent = b;
1. }
480. b->right = c->left;
481. c->left = b;
482. b->parent = c;
483. if (c->right!= NULL)
484. {
485. c->right->parent = a;
1. }
486. a->left = c->right;
487. c->right = a;
488. c->parent = a->parent;
489. a->parent = c;
1. return c;
490. }
1. // node is not the root
491. void insertRebuild(RBNode* node)
492. {
493. RBNode* parent = NULL;
494. RBNode* grandParent = NULL;
495. while (node->parent != NULL)
496. {
497. parent = node->parent;
1. if (parent->color == RED) // here means there must be a grandparent
498. {
499. grandParent = parent->parent;
500. grandParent->color = BLACK;
1. if (grandParent->left == parent)
501. {
502. if (parent->left == node)
503. {
504. //LLRotate
505. node->color = BLACK;
506. node = LLRotate(grandParent,parent);
1. }
507. else
508. {
509. //LRRotate
510. parent->color = BLACK;
511. node = LRRotate(grandParent,parent,node);
1. }
1. }
512. else
513. {
1. if (parent->left == node)
514. {
515. //RLRotate
516. parent->color = BLACK;
517. node = RLRotate(grandParent,parent,node);
518. }
519. else
520. {
521. //RRRotate
522. node->color = BLACK;
523. node = RRRotate(grandParent,parent);
524. }
525. }
526. }
527. else
528. {
529. break ;
530. }
531. }
1. if (node->parent == NULL)
532. {
533. node->color = BLACK;
534. this ->root = node;
535. }
536. else
537. {
538. rebuild(node);
539. /*if(node->parent->data > node->data)
540. {
541. node->parent->left = node;
542. }
543. else
544. {
545. node->parent->right = node;
546. }*/
547. }
548. }
1. int getBlackNum(RBNode* subRoot)
549. {
550. if (subRoot == NULL)
551. {
552. return 1;
553. }
554. int left = getBlackNum(subRoot->left);
555. int right = getBlackNum(subRoot->right);
556. if (left != right)
557. {
558. throw “wrong” ;
559. }
560. if (subRoot->color == BLACK)
561. {
1. return 1+left;
562. }
563. else
564. {
565. return left;
566. }
1. }
567. };