红黑树的实现源码(C语言版)

converse

不多说啥了,这里不讲理论, 需要的可以自己去看书(如算法导论等), 就给出一份实现代码, 供有需要的人参考之用, 前后写了好久, 参考的是linux内核中红黑树的实现代码:http://lxr.linux.no/linux/lib/rbtree.c

实现的操作有:插入, 查找, 删除.

1. 
   
2. /*-----------------------------------------------------------
   
3.     RB-Tree的插入和删除操作的实现算法
   
4.     参考资料:
   
5.     1) <<Introduction to algorithm>>
   
6.     2) [url]http://lxr.linux.no/linux/lib/rbtree.c[/url]
   
7. 
   
8.     作者：[url]http://www.cppblog.com/converse/[/url]
   
9.     您可以自由的传播，修改这份代码，转载处请注明原作者
   
10. 
    
11.     红黑树的几个性质:
    
12.     1) 每个结点只有红和黑两种颜色
    
13.     2) 根结点是黑色的
    
14.     3)空节点是黑色的（红黑树中，根节点的parent以及所有叶节点lchild、rchild都不指向NULL，而是指向一个定义好的空节点）。
    
15.     4) 如果一个结点是红色的,那么它的左右两个子结点的颜色是黑色的
    
16.     5) 对于每个结点而言,从这个结点到叶子结点的任何路径上的黑色结点
    
17.     的数目相同
    
18. -------------------------------------------------------------*/
    
19. 
    
20. #include <stdio.h>
    
21. #include <stdlib.h>
    
22. #include <string.h>
    
23. 
    
24. typedef int key_t;
    
25. typedef int data_t;
    
26. 
    
27. typedef enum color_t
    
28. {
    
29.     RED = 0,
    
30.     BLACK = 1
    
31. }color_t;
    
32. 
    
33. typedef struct rb_node_t
    
34. {
    
35.     struct rb_node_t *left, *right, *parent;
    
36.     key_t key;
    
37.     data_t data;
    
38.     color_t color;
    
39. }rb_node_t;
    
40. 
    
41. /* forward declaration */
    
42. rb_node_t* rb_insert(key_t key, data_t data, rb_node_t* root);
    
43. rb_node_t* rb_search(key_t key, rb_node_t* root);
    
44. rb_node_t* rb_erase(key_t key, rb_node_t* root);
    
45. 
    
46. int main()
    
47. {
    
48.     int i, count = 900000;
    
49.     key_t key;
    
50.     rb_node_t* root = NULL, *node = NULL;
    
51.    
    
52.     srand(time(NULL));
    
53.     for (i = 1; i < count; ++i)
    
54.     {
    
55.         key = rand() % count;
    
56.         if ((root = rb_insert(key, i, root)))
    
57.         {
    
58.             printf("[i = %d] insert key %d success!\n", i, key);
    
59.         }
    
60.         else
    
61.         {
    
62.             printf("[i = %d] insert key %d error!\n", i, key);
    
63.             exit(-1);
    
64.         }
    
65. 
    
66.         if ((node = rb_search(key, root)))
    
67.         {
    
68.             printf("[i = %d] search key %d success!\n", i, key);
    
69.         }
    
70.         else
    
71.         {
    
72.             printf("[i = %d] search key %d error!\n", i, key);
    
73.             exit(-1);
    
74.         }
    
75.         if (!(i % 10))
    
76.         {
    
77.             if ((root = rb_erase(key, root)))
    
78.             {
    
79.                 printf("[i = %d] erase key %d success\n", i, key);
    
80.             }
    
81.             else
    
82.             {
    
83.                 printf("[i = %d] erase key %d error\n", i, key);
    
84.             }
    
85.         }
    
86.     }
    
87. 
    
88.     return 0;
    
89. }
    
90. 
    
91. static rb_node_t* rb_new_node(key_t key, data_t data)
    
92. {
    
93.     rb_node_t *node = (rb_node_t*)malloc(sizeof(struct rb_node_t));
    
94. 
    
95.     if (!node)
    
96.     {
    
97.         printf("malloc error!\n");
    
98.         exit(-1);
    
99.     }
    
100.     node->key = key, node->data = data;
     
101. 
     
102.     return node;
     
103. }
     
104. 
     
105. /*-----------------------------------------------------------
     
106. |   node           right
     
107. |   / \    ==>     / \
     
108. |   a  right     node  y
     
109. |       / \           / \
     
110. |       b  y         a   b
     
111. -----------------------------------------------------------*/
     
112. static rb_node_t* rb_rotate_left(rb_node_t* node, rb_node_t* root)
     
113. {
     
114.     rb_node_t* right = node->right;
     
115. 
     
116.     if ((node->right = right->left))
     
117.     {
     
118.         right->left->parent = node;
     
119.     }
     
120.     right->left = node;
     
121. 
     
122.     if ((right->parent = node->parent))
     
123.     {
     
124.         if (node == node->parent->right)
     
125.         {
     
126.             node->parent->right = right;
     
127.         }
     
128.         else
     
129.         {
     
130.             node->parent->left = right;
     
131.         }
     
132.     }
     
133.     else
     
134.     {
     
135.         root = right;
     
136.     }
     
137.     node->parent = right;
     
138. 
     
139.     return root;
     
140. }
     
141. 
     
142. /*-----------------------------------------------------------
     
143. |       node           left
     
144. |       / \            / \
     
145. |    left  y   ==>    a   node
     
146. |   / \               / \
     
147. |  a   b             b   y
     
148. -----------------------------------------------------------*/
     
149. static rb_node_t* rb_rotate_right(rb_node_t* node, rb_node_t* root)
     
150. {
     
151.     rb_node_t* left = node->left;
     
152. 
     
153.     if ((node->left = left->right))
     
154.     {
     
155.         left->right->parent = node;
     
156.     }
     
157.     left->right = node;
     
158. 
     
159.     if ((left->parent = node->parent))
     
160.     {
     
161.         if (node == node->parent->right)
     
162.         {
     
163.             node->parent->right = left;
     
164.         }
     
165.         else
     
166.         {
     
167.             node->parent->left = left;
     
168.         }
     
169.     }
     
170.     else
     
171.     {
     
172.         root = left;
     
173.     }
     
174.     node->parent = left;
     
175. 
     
176.     return root;
     
177. }
     
178. 
     
179. static rb_node_t* rb_insert_rebalance(rb_node_t *node, rb_node_t *root)
     
180. {
     
181.     rb_node_t *parent, *gparent, *uncle, *tmp;
     
182. 
     
183.     while ((parent = node->parent) && parent->color == RED)
     
184.     {
     
185.         gparent = parent->parent;
     
186. 
     
187.         if (parent == gparent->left)
     
188.         {
     
189.             uncle = gparent->right;
     
190.             if (uncle && uncle->color == RED)
     
191.             {
     
192.                 uncle->color = BLACK;
     
193.                 parent->color = BLACK;
     
194.                 gparent->color = RED;
     
195.                 node = gparent;
     
196.             }
     
197.             else
     
198.             {
     
199.                 if (parent->right == node)
     
200.                 {
     
201.                     root = rb_rotate_left(parent, root);
     
202.                     tmp = parent;
     
203.                     parent = node;
     
204.                     node = tmp;
     
205.                 }
     
206. 
     
207.                 parent->color = BLACK;
     
208.                 gparent->color = RED;
     
209.                 root = rb_rotate_right(gparent, root);
     
210.             }
     
211.         }
     
212.         else
     
213.         {
     
214.             uncle = gparent->left;
     
215.             if (uncle && uncle->color == RED)
     
216.             {
     
217.                 uncle->color = BLACK;
     
218.                 parent->color = BLACK;
     
219.                 gparent->color = RED;
     
220.                 node = gparent;
     
221.             }
     
222.             else
     
223.             {
     
224.                 if (parent->left == node)
     
225.                 {
     
226.                     root = rb_rotate_right(parent, root);
     
227.                     tmp = parent;
     
228.                     parent = node;
     
229.                     node = tmp;
     
230.                 }
     
231. 
     
232.                 parent->color = BLACK;
     
233.                 gparent->color = RED;
     
234.                 root = rb_rotate_left(gparent, root);
     
235.             }
     
236.         }
     
237.     }
     
238. 
     
239.     root->color = BLACK;
     
240. 
     
241.     return root;
     
242. }
     
243. 
     
244. static rb_node_t* rb_erase_rebalance(rb_node_t *node, rb_node_t *parent, rb_node_t *root)
     
245. {
     
246.     rb_node_t *other, *o_left, *o_right;
     
247. 
     
248.     while ((!node || node->color == BLACK) && node != root)
     
249.     {
     
250.         if (parent->left == node)
     
251.         {
     
252.             other = parent->right;
     
253.             if (other->color == RED)
     
254.             {
     
255.                 other->color = BLACK;
     
256.                 parent->color = RED;
     
257.                 root = rb_rotate_left(parent, root);
     
258.                 other = parent->right;
     
259.             }
     
260.             if ((!other->left || other->left->color == BLACK) &&
     
261.                 (!other->right || other->right->color == BLACK))
     
262.             {
     
263.                 other->color = RED;
     
264.                 node = parent;
     
265.                 parent = node->parent;
     
266.             }
     
267.             else
     
268.             {
     
269.                 if (!other->right || other->right->color == BLACK)
     
270.                 {
     
271.                     if ((o_left = other->left))
     
272.                     {
     
273.                         o_left->color = BLACK;
     
274.                     }
     
275.                     other->color = RED;
     
276.                     root = rb_rotate_right(other, root);
     
277.                     other = parent->right;
     
278.                 }
     
279.                 other->color = parent->color;
     
280.                 parent->color = BLACK;
     
281.                 if (other->right)
     
282.                 {
     
283.                     other->right->color = BLACK;
     
284.                 }
     
285.                 root = rb_rotate_left(parent, root);
     
286.                 node = root;
     
287.                 break;
     
288.             }
     
289.         }
     
290.         else
     
291.         {
     
292.             other = parent->left;
     
293.             if (other->color == RED)
     
294.             {
     
295.                 other->color = BLACK;
     
296.                 parent->color = RED;
     
297.                 root = rb_rotate_right(parent, root);
     
298.                 other = parent->left;
     
299.             }
     
300.             if ((!other->left || other->left->color == BLACK) &&
     
301.                 (!other->right || other->right->color == BLACK))
     
302.             {
     
303.                 other->color = RED;
     
304.                 node = parent;
     
305.                 parent = node->parent;
     
306.             }
     
307.             else
     
308.             {
     
309.                 if (!other->left || other->left->color == BLACK)
     
310.                 {
     
311.                     if ((o_right = other->right))
     
312.                     {
     
313.                         o_right->color = BLACK;
     
314.                     }
     
315.                     other->color = RED;
     
316.                     root = rb_rotate_left(other, root);
     
317.                     other = parent->left;
     
318.                 }
     
319.                 other->color = parent->color;
     
320.                 parent->color = BLACK;
     
321.                 if (other->left)
     
322.                 {
     
323.                     other->left->color = BLACK;
     
324.                 }
     
325.                 root = rb_rotate_right(parent, root);
     
326.                 node = root;
     
327.                 break;
     
328.             }
     
329.         }
     
330.     }
     
331. 
     
332.     if (node)
     
333.     {
     
334.         node->color = BLACK;
     
335.     }
     
336. 
     
337.     return root;
     
338. }
     
339. 
     
340. static rb_node_t* rb_search_auxiliary(key_t key, rb_node_t* root, rb_node_t** save)
     
341. {
     
342.     rb_node_t *node = root, *parent = NULL;
     
343.     int ret;
     
344. 
     
345.     while (node)
     
346.     {
     
347.         parent = node;
     
348.         ret = node->key - key;
     
349.         if (0 < ret)
     
350.         {
     
351.             node = node->left;
     
352.         }
     
353.         else if (0 > ret)
     
354.         {
     
355.             node = node->right;
     
356.         }
     
357.         else
     
358.         {
     
359.             return node;
     
360.         }
     
361.     }
     
362. 
     
363.     if (save)
     
364.     {
     
365.         *save = parent;
     
366.     }
     
367. 
     
368.     return NULL;
     
369. }
     
370. 
     
371. rb_node_t* rb_insert(key_t key, data_t data, rb_node_t* root)
     
372. {
     
373.     rb_node_t *parent = NULL, *node;
     
374. 
     
375.     parent = NULL;
     
376.     if ((node = rb_search_auxiliary(key, root, &parent)))
     
377.     {
     
378.         return root;
     
379.     }
     
380. 
     
381.     node = rb_new_node(key, data);
     
382.     node->parent = parent;
     
383.     node->left = node->right = NULL;
     
384.     node->color = RED;
     
385. 
     
386.     if (parent)
     
387.     {
     
388.         if (parent->key > key)
     
389.         {
     
390.             parent->left = node;
     
391.         }
     
392.         else
     
393.         {
     
394.             parent->right = node;
     
395.         }
     
396.     }
     
397.     else
     
398.     {
     
399.         root = node;
     
400.     }
     
401. 
     
402.     return rb_insert_rebalance(node, root);
     
403. }
     
404. 
     
405. rb_node_t* rb_search(key_t key, rb_node_t* root)
     
406. {
     
407.     return rb_search_auxiliary(key, root, NULL);
     
408. }
     
409. 
     
410. rb_node_t* rb_erase(key_t key, rb_node_t *root)
     
411. {
     
412.     rb_node_t *child, *parent, *old, *left, *node;
     
413.     color_t color;
     
414. 
     
415.     if (!(node = rb_search_auxiliary(key, root, NULL)))
     
416.     {
     
417.         printf("key %d is not exist!\n");
     
418.         return root;
     
419.     }
     
420. 
     
421.     old = node;
     
422. 
     
423.     if (node->left && node->right)
     
424.     {
     
425.         node = node->right;
     
426.         while ((left = node->left) != NULL)
     
427.         {
     
428.             node = left;
     
429.         }
     
430.         child = node->right;
     
431.         parent = node->parent;
     
432.         color = node->color;
     
433. 
     
434.         if (child)
     
435.         {
     
436.             child->parent = parent;
     
437.         }
     
438.         if (parent)
     
439.         {
     
440.             if (parent->left == node)
     
441.             {
     
442.                 parent->left = child;
     
443.             }
     
444.             else
     
445.             {
     
446.                 parent->right = child;
     
447.             }
     
448.         }
     
449.         else
     
450.         {
     
451.             root = child;
     
452.         }
     
453. 
     
454.         if (node->parent == old)
     
455.         {
     
456.             parent = node;
     
457.         }
     
458. 
     
459.         node->parent = old->parent;
     
460.         node->color = old->color;
     
461.         node->right = old->right;
     
462.         node->left = old->left;
     
463. 
     
464.         if (old->parent)
     
465.         {
     
466.             if (old->parent->left == old)
     
467.             {
     
468.                 old->parent->left = node;
     
469.             }
     
470.             else
     
471.             {
     
472.                 old->parent->right = node;
     
473.             }
     
474.         }
     
475.         else
     
476.         {
     
477.             root = node;
     
478.         }
     
479. 
     
480.         old->left->parent = node;
     
481.         if (old->right)
     
482.         {
     
483.             old->right->parent = node;
     
484.         }
     
485.     }
     
486.     else
     
487.     {
     
488.         if (!node->left)
     
489.         {
     
490.             child = node->right;
     
491.         }
     
492.         else if (!node->right)
     
493.         {
     
494.             child = node->left;
     
495.         }
     
496.         parent = node->parent;
     
497.         color = node->color;
     
498. 
     
499.         if (child)
     
500.         {
     
501.             child->parent = parent;
     
502.         }
     
503.         if (parent)
     
504.         {
     
505.             if (parent->left == node)
     
506.             {
     
507.                 parent->left = child;
     
508.             }
     
509.             else
     
510.             {
     
511.                 parent->right = child;
     
512.             }
     
513.         }
     
514.         else
     
515.         {
     
516.             root = child;
     
517.         }
     
518.     }
     
519. 
     
520.     free(old);
     
521. 
     
522.     if (color == BLACK)
     
523.     {
     
524.         root = rb_erase_rebalance(child, parent, root);
     
525.     }
     
526. 
     
527.     return root;
     
528. }
     
529. 
     
530. 
     

复制代码

[ 本帖最后由 converse 于 2008-11-11 19:20 编辑 ]

UnixStudier

版权协议？

zengit

收藏

雨过白鹭洲

暂时看不懂，先顶一个先

nhuczp

红黑树在新的调度器（CFS）中被使用。这个东西很牛。

LZ能不能写得再细一点！！

cugb_cat

原帖由 nhuczp 于 2008-11-11 09:41 发表
红黑树在新的调度器（CFS）中被使用。这个东西很牛。

LZ能不能写得再细一点！！

你去看《算法导论》吧
内核中实现的红黑树是很中规中矩的，跟算法导论上讲的完全一样。

veking

有时间研究下，学习了。。。


LS的也在中关村吗？

[ 本帖最后由 veking 于 2008-11-11 13:40 编辑 ]

mz198424

原帖由 converse 于 2008-11-10 17:40 发表
不多说啥了,这里不讲理论, 需要的可以自己去看书(如算法导论等), 就给出一份实现代码, 供有需要的人参考之用, 前后写了好久, 参考的是linux内核中红黑树的实现代码:http://lxr.linux.no/linux/lib/rbtree.c

...

感谢，并且收藏了。

wxr9999

先收藏，谢谢

lbaby

http://www.freebsd.org/cgi/cvswe ... ib/rb.h?rev=1.4.2.1;content-type=text%2Fplain


/******************************************************************************
*
* Copyright (C) 2008 Jason Evans <jasone@FreeBSD.org>.
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
* 1. Redistributions of source code must retain the above copyright
*    notice(s), this list of conditions and the following disclaimer
*    unmodified other than the allowable addition of one or more
*    copyright notices.
* 2. Redistributions in binary form must reproduce the above copyright
*    notice(s), this list of conditions and the following disclaimer in
*    the documentation and/or other materials provided with the
*    distribution.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDER(S) ``AS IS'' AND ANY
* EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
* PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT HOLDER(S) BE
* LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
* CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
* SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
* BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
* WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE
* OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
* EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*
******************************************************************************
*
* cpp macro implementation of left-leaning red-black trees.
*
* Usage:
*
*   (Optional, see assert(3).)
*   #define NDEBUG
*
*   (Required.)
*   #include <assert.h>
*   #include <rb.h>
*   ...
*
* All operations are done non-recursively.  Parent pointers are not used, and
* color bits are stored in the least significant bit of right-child pointers,
* thus making node linkage as compact as is possible for red-black trees.
*
* Some macros use a comparison function pointer, which is expected to have the
* following prototype:
*
*   int (a_cmp *)(a_type *a_node, a_type *a_other);
*                         ^^^^^^
*                      or a_key
*
* Interpretation of comparision function return values:
*
*   -1 : a_node <  a_other
*    0 : a_node == a_other
*    1 : a_node >  a_other
*
* In all cases, the a_node or a_key macro argument is the first argument to the
* comparison function, which makes it possible to write comparison functions
* that treat the first argument specially.
*
******************************************************************************/

#ifndef RB_H_
#define        RB_H_

#include <sys/cdefs.h>
__FBSDID("$FreeBSD: src/lib/libc/stdlib/rb.h,v 1.4.2.1 2008/06/16 23:42:05 jasone Exp $");

/* Node structure. */
#define        rb_node(a_type)                                                        \
struct {                                                                \
    a_type *rbn_left;                                                        \
    a_type *rbn_right_red;                                                \
}

/* Root structure. */
#define        rb_tree(a_type)                                                        \
struct {                                                                \
    a_type *rbt_root;                                                        \
    a_type rbt_nil;                                                        \
}

/* Left accessors. */
#define        rbp_left_get(a_type, a_field, a_node)                                \
    ((a_node)->a_field.rbn_left)
#define        rbp_left_set(a_type, a_field, a_node, a_left) do {                \
    (a_node)->a_field.rbn_left = a_left;                                \
} while (0)

/* Right accessors. */
#define        rbp_right_get(a_type, a_field, a_node)                                \
    ((a_type *) (((intptr_t) (a_node)->a_field.rbn_right_red)                \
      & ((ssize_t)-2)))
#define        rbp_right_set(a_type, a_field, a_node, a_right) do {                \
    (a_node)->a_field.rbn_right_red = (a_type *) (((uintptr_t) a_right)        \
      | (((uintptr_t) (a_node)->a_field.rbn_right_red) & ((size_t)1)));        \
} while (0)

/* Color accessors. */
#define        rbp_red_get(a_type, a_field, a_node)                                \
    ((bool) (((uintptr_t) (a_node)->a_field.rbn_right_red)                \
      & ((size_t)1)))
#define        rbp_color_set(a_type, a_field, a_node, a_red) do {                \
    (a_node)->a_field.rbn_right_red = (a_type *) ((((intptr_t)                \
      (a_node)->a_field.rbn_right_red) & ((ssize_t)-2))                        \
      | ((ssize_t)a_red));                                                \
} while (0)
#define        rbp_red_set(a_type, a_field, a_node) do {                        \
    (a_node)->a_field.rbn_right_red = (a_type *) (((uintptr_t)                \
      (a_node)->a_field.rbn_right_red) | ((size_t)1));                        \
} while (0)
#define        rbp_black_set(a_type, a_field, a_node) do {                        \
    (a_node)->a_field.rbn_right_red = (a_type *) (((intptr_t)                \
      (a_node)->a_field.rbn_right_red) & ((ssize_t)-2));                \
} while (0)

/* Node initializer. */
#define        rbp_node_new(a_type, a_field, a_tree, a_node) do {                \
    rbp_left_set(a_type, a_field, (a_node), &(a_tree)->rbt_nil);        \
    rbp_right_set(a_type, a_field, (a_node), &(a_tree)->rbt_nil);        \
    rbp_red_set(a_type, a_field, (a_node));                                \
} while (0)

/* Tree initializer. */
#define        rb_new(a_type, a_field, a_tree) do {                                \
    (a_tree)->rbt_root = &(a_tree)->rbt_nil;                                \
    rbp_node_new(a_type, a_field, a_tree, &(a_tree)->rbt_nil);                \
    rbp_black_set(a_type, a_field, &(a_tree)->rbt_nil);                        \
} while (0)

/* Tree operations. */
#define        rbp_black_height(a_type, a_field, a_tree, r_height) do {        \
    a_type *rbp_bh_t;                                                        \
    for (rbp_bh_t = (a_tree)->rbt_root, (r_height) = 0;                        \
      rbp_bh_t != &(a_tree)->rbt_nil;                                        \
      rbp_bh_t = rbp_left_get(a_type, a_field, rbp_bh_t)) {                \
        if (rbp_red_get(a_type, a_field, rbp_bh_t) == false) {                \
            (r_height)++;                                                \
        }                                                                \
    }                                                                        \
} while (0)

#define        rbp_first(a_type, a_field, a_tree, a_root, r_node) do {                \
    for ((r_node) = (a_root);                                                \
      rbp_left_get(a_type, a_field, (r_node)) != &(a_tree)->rbt_nil;        \
      (r_node) = rbp_left_get(a_type, a_field, (r_node))) {                \
    }                                                                        \
} while (0)

#define        rbp_last(a_type, a_field, a_tree, a_root, r_node) do {                \
    for ((r_node) = (a_root);                                                \
      rbp_right_get(a_type, a_field, (r_node)) != &(a_tree)->rbt_nil;        \
      (r_node) = rbp_right_get(a_type, a_field, (r_node))) {                \
    }                                                                        \
} while (0)

#define        rbp_next(a_type, a_field, a_cmp, a_tree, a_node, r_node) do {        \
    if (rbp_right_get(a_type, a_field, (a_node))                        \
      != &(a_tree)->rbt_nil) {                                                \
        rbp_first(a_type, a_field, a_tree, rbp_right_get(a_type,        \
          a_field, (a_node)), (r_node));                                \
    } else {                                                                \
        a_type *rbp_n_t = (a_tree)->rbt_root;                                \
        assert(rbp_n_t != &(a_tree)->rbt_nil);                                \
        (r_node) = &(a_tree)->rbt_nil;                                        \
        while (true) {                                                        \
            int rbp_n_cmp = (a_cmp)((a_node), rbp_n_t);                        \
            if (rbp_n_cmp < 0) {                                        \
                (r_node) = rbp_n_t;                                        \
                rbp_n_t = rbp_left_get(a_type, a_field, rbp_n_t);        \
            } else if (rbp_n_cmp > 0) {                                        \
                rbp_n_t = rbp_right_get(a_type, a_field, rbp_n_t);        \
            } else {                                                        \
                break;                                                        \
            }                                                                \
            assert(rbp_n_t != &(a_tree)->rbt_nil);                        \
        }                                                                \
    }                                                                        \
} while (0)

#define        rbp_prev(a_type, a_field, a_cmp, a_tree, a_node, r_node) do {        \
    if (rbp_left_get(a_type, a_field, (a_node)) != &(a_tree)->rbt_nil) {\
        rbp_last(a_type, a_field, a_tree, rbp_left_get(a_type,                \
          a_field, (a_node)), (r_node));                                \
    } else {                                                                \
        a_type *rbp_p_t = (a_tree)->rbt_root;                                \
        assert(rbp_p_t != &(a_tree)->rbt_nil);                                \
        (r_node) = &(a_tree)->rbt_nil;                                        \
        while (true) {                                                        \
            int rbp_p_cmp = (a_cmp)((a_node), rbp_p_t);                        \
            if (rbp_p_cmp < 0) {                                        \
                rbp_p_t = rbp_left_get(a_type, a_field, rbp_p_t);        \
            } else if (rbp_p_cmp > 0) {                                        \
                (r_node) = rbp_p_t;                                        \
                rbp_p_t = rbp_right_get(a_type, a_field, rbp_p_t);        \
            } else {                                                        \
                break;                                                        \
            }                                                                \
            assert(rbp_p_t != &(a_tree)->rbt_nil);                        \
        }                                                                \
    }                                                                        \
} while (0)

#define        rb_first(a_type, a_field, a_tree, r_node) do {                        \
    rbp_first(a_type, a_field, a_tree, (a_tree)->rbt_root, (r_node));        \
    if ((r_node) == &(a_tree)->rbt_nil) {                                \
        (r_node) = NULL;                                                \
    }                                                                        \
} while (0)

#define        rb_last(a_type, a_field, a_tree, r_node) do {                        \
    rbp_last(a_type, a_field, a_tree, (a_tree)->rbt_root, r_node);        \
    if ((r_node) == &(a_tree)->rbt_nil) {                                \
        (r_node) = NULL;                                                \
    }                                                                        \
} while (0)

#define        rb_next(a_type, a_field, a_cmp, a_tree, a_node, r_node) do {        \
    rbp_next(a_type, a_field, a_cmp, a_tree, (a_node), (r_node));        \
    if ((r_node) == &(a_tree)->rbt_nil) {                                \
        (r_node) = NULL;                                                \
    }                                                                        \
} while (0)

#define        rb_prev(a_type, a_field, a_cmp, a_tree, a_node, r_node) do {        \
    rbp_prev(a_type, a_field, a_cmp, a_tree, (a_node), (r_node));        \
    if ((r_node) == &(a_tree)->rbt_nil) {                                \
        (r_node) = NULL;                                                \
    }                                                                        \
} while (0)

#define        rb_search(a_type, a_field, a_cmp, a_tree, a_key, r_node) do {        \
    int rbp_se_cmp;                                                        \
    (r_node) = (a_tree)->rbt_root;                                        \
    while ((r_node) != &(a_tree)->rbt_nil                                \
      && (rbp_se_cmp = (a_cmp)((a_key), (r_node))) != 0) {                \
        if (rbp_se_cmp < 0) {                                                \
            (r_node) = rbp_left_get(a_type, a_field, (r_node));                \
        } else {                                                        \
            (r_node) = rbp_right_get(a_type, a_field, (r_node));        \
        }                                                                \
    }                                                                        \
    if ((r_node) == &(a_tree)->rbt_nil) {                                \
        (r_node) = NULL;                                                \
    }                                                                        \
} while (0)

/*
* Find a match if it exists.  Otherwise, find the next greater node, if one
* exists.
*/
#define        rb_nsearch(a_type, a_field, a_cmp, a_tree, a_key, r_node) do {        \
    a_type *rbp_ns_t = (a_tree)->rbt_root;                                \
    (r_node) = NULL;                                                        \
    while (rbp_ns_t != &(a_tree)->rbt_nil) {                                \
        int rbp_ns_cmp = (a_cmp)((a_key), rbp_ns_t);                        \
        if (rbp_ns_cmp < 0) {                                                \
            (r_node) = rbp_ns_t;                                        \
            rbp_ns_t = rbp_left_get(a_type, a_field, rbp_ns_t);                \
        } else if (rbp_ns_cmp > 0) {                                        \
            rbp_ns_t = rbp_right_get(a_type, a_field, rbp_ns_t);        \
        } else {                                                        \
            (r_node) = rbp_ns_t;                                        \
            break;                                                        \
        }                                                                \
    }                                                                        \
} while (0)