2  * rbtree.c -- generic red black tree
47 /** Node colour black */
48 #define	BLACK	0  macro
58 	BLACK			/* Color.  */
72  * Creates a new red black tree, initializes and returns a pointer to it.
170 				/* Paint the parent and the uncle black... */  in rbtree_insert_fixup()
171 				node->parent->color = BLACK;  in rbtree_insert_fixup()
172 				uncle->color = BLACK;  in rbtree_insert_fixup()
179 			} else {				/* Our uncle is black... */  in rbtree_insert_fixup()
186 				node->parent->color = BLACK;  in rbtree_insert_fixup()
195 				/* Paint the parent and the uncle black... */  in rbtree_insert_fixup()
196 				node->parent->color = BLACK;  in rbtree_insert_fixup()
197 				uncle->color = BLACK;  in rbtree_insert_fixup()
204 			} else {				/* Our uncle is black... */  in rbtree_insert_fixup()
211 				node->parent->color = BLACK;  in rbtree_insert_fixup()
217 	rbtree->root->color = BLACK;  in rbtree_insert_fixup()
222  * Inserts a node into a red black tree.
270 	/* Fix up the red-black properties... */  in rbtree_insert()
277  * Searches the red black tree, returns the data if key is found or NULL otherwise.
389 		/* if node is red then the child (black) can be swapped in */  in rbtree_delete()
393 		/* change child to BLACK, removing a RED node is no problem */  in rbtree_delete()
394 		if(child!=RBTREE_NULL) child->color = BLACK;  in rbtree_delete()
402 	to_delete->color = BLACK;  in rbtree_delete()
412 	/* determine sibling to the node that is one-black short */  in rbtree_delete_fixup()
420 			/* removed parent==black from root, every path, so ok */  in rbtree_delete_fixup()
425 		{	/* rotate to get a black sibling */  in rbtree_delete_fixup()
427 			sibling->color = BLACK;  in rbtree_delete_fixup()
436 		if(child_parent->color == BLACK   in rbtree_delete_fixup()
437 			&& sibling->color == BLACK  in rbtree_delete_fixup()
438 			&& sibling->left->color == BLACK  in rbtree_delete_fixup()
439 			&& sibling->right->color == BLACK)  in rbtree_delete_fixup()
454 		&& sibling->color == BLACK  in rbtree_delete_fixup()
455 		&& sibling->left->color == BLACK  in rbtree_delete_fixup()
456 		&& sibling->right->color == BLACK)   in rbtree_delete_fixup()
461 		child_parent->color = BLACK;  in rbtree_delete_fixup()
469 		&& sibling->color == BLACK  in rbtree_delete_fixup()
471 		&& sibling->left->color == BLACK)  in rbtree_delete_fixup()
474 		sibling->right->color = BLACK;  in rbtree_delete_fixup()
481 		&& sibling->color == BLACK  in rbtree_delete_fixup()
483 		&& sibling->right->color == BLACK)  in rbtree_delete_fixup()
486 		sibling->left->color = BLACK;  in rbtree_delete_fixup()
493 	/* now we have a black sibling with a red child. rotate and exchange colors. */  in rbtree_delete_fixup()
495 	child_parent->color = BLACK;  in rbtree_delete_fixup()
499 		sibling->left->color = BLACK;  in rbtree_delete_fixup()
505 		sibling->right->color = BLACK;  in rbtree_delete_fixup()
545  * Finds the first element in the red black tree