红黑树实现_#define rb_parent(r) ((struct rb_node *)((r)->rb_p

红黑树概述

红黑树是一种自平衡二叉查找树，典型的用途是实现关联数组。它是复杂的，但它的操作有着良好的最坏情况运行时间，并且在实践中是高效的: 它可以在O(logn)时间内做查找，插入和删除，这里的n是树中元素的数目。红黑树是 2-3-4树的一种等同。换句话说，对于每个 2-3-4 树，都存在至少一个数据元素是同样次序的红黑树。详细的红黑树介绍参考我转载的一篇博文http://blog.csdn.net/pngynghay/article/details/8185351。本博文仅仅实现了rbtree以及如何使用rbtree。

红黑树实现

本博文红黑树的实现取自Linux内核对红黑树的实现，只是，我去掉了内核实现中对内核的依赖，使得我们可以在用户态应用程序中依然可以使用。

rbtree.h

#ifndef RBTREE_H_
#define RBTREE_H_
 
#include <stdlib.h>
#include <stddef.h>
#include <stdio.h>
#include <string.h>
 
/*通过父结构体type中的成员member的已知地址ptr，来寻找当前ptr地址所属的父结构体type的地址*/
#define container_of(ptr, type, member) ({ \
const typeof( ((type *)0)->member ) *__mptr = (ptr); \
(type *)( (char *)__mptr - offsetof(type,member) );})
 
struct rb_node {
	unsigned long rb_parent_color;
#define	RB_RED		0
#define	RB_BLACK	1
	struct rb_node *rb_right;
	struct rb_node *rb_left;
}__attribute__((aligned(sizeof(long))));
/* The alignment might seem pointless, but allegedly CRIS needs it */
 
struct rb_root {
	struct rb_node *rb_node;
};
 
#define rb_parent(r)   ((struct rb_node *)((r)->rb_parent_color & ~3))
#define rb_color(r)   ((r)->rb_parent_color & 1)
#define rb_is_red(r)   (!rb_color(r))
#define rb_is_black(r) rb_color(r)
#define rb_set_red(r)  do { (r)->rb_parent_color &= ~1; } while (0)
#define rb_set_black(r)  do { (r)->rb_parent_color |= 1; } while (0)
 
static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p) {
	rb->rb_parent_color = (rb->rb_parent_color & 3) | (unsigned long) p;
}
static inline void rb_set_color(struct rb_node *rb, int color) {
	rb->rb_parent_color = (rb->rb_parent_color & ~1) | color;
}
 
#define RB_ROOT	(struct rb_root) { NULL, }
#define	rb_entry(ptr, type, member) container_of(ptr, type, member)
 
#define RB_EMPTY_ROOT(root)	((root)->rb_node == NULL)
#define RB_EMPTY_NODE(node)	(rb_parent(node) == node)
#define RB_CLEAR_NODE(node)	(rb_set_parent(node, node))
 
extern void rb_insert_color(struct rb_node *, struct rb_root *);
extern void rb_erase(struct rb_node *, struct rb_root *);
 
/* Find logical next and previous nodes in a tree */
extern struct rb_node *rb_next(const struct rb_node *);
extern struct rb_node *rb_prev(const struct rb_node *);
extern struct rb_node *rb_first(const struct rb_root *);
extern struct rb_node *rb_last(const struct rb_root *);
 
/* Fast replacement of a single node without remove/rebalance/add/rebalance */
extern void rb_replace_node(struct rb_node *victim, struct rb_node *new,
		struct rb_root *root);
 
static inline void rb_link_node(struct rb_node * node, struct rb_node * parent,
		struct rb_node ** rb_link) {
	node->rb_parent_color = (unsigned long) parent;
	node->rb_left = node->rb_right = NULL;
 
	*rb_link = node;
}
 
#endif /* RBTREE_H_ */

rbtree.c

static void __rb_rotate_left(struct rb_node *node, struct rb_root *root) {
	struct rb_node *right = node->rb_right;
	struct rb_node *parent = rb_parent(node);
 
	if ((node->rb_right = right->rb_left))
		rb_set_parent(right->rb_left, node);
	right->rb_left = node;
 
	rb_set_parent(right, parent);
 
	if (parent) {
		if (node == parent->rb_left)
			parent->rb_left = right;
		else
			parent->rb_right = right;
	} else
		root->rb_node = right;
	rb_set_parent(node, right);
}
 
static void __rb_rotate_right(struct rb_node *node, struct rb_root *root) {
	struct rb_node *left = node->rb_left;
	struct rb_node *parent = rb_parent(node);
 
	if ((node->rb_left = left->rb_right))
		rb_set_parent(left->rb_right, node);
	left->rb_right = node;
 
	rb_set_parent(left, parent);
 
	if (parent) {
		if (node == parent->rb_right)
			parent->rb_right = left;
		else
			parent->rb_left = left;
	} else
		root->rb_node = left;
	rb_set_parent(node, left);
}
 
void rb_insert_color(struct rb_node *node, struct rb_root *root) {
	struct rb_node *parent, *gparent;
 
	while ((parent = rb_parent(node)) && rb_is_red(parent)) {
		gparent = rb_parent(parent);
 
		if (parent == gparent->rb_left) {
			{
				register struct rb_node *uncle = gparent->rb_right;
				if (uncle && rb_is_red(uncle))
				{
					rb_set_black(uncle);
					rb_set_black(parent);
					rb_set_red(gparent);
					node = gparent;
					continue;
				}
			}
 
			if (parent->rb_right == node) {
				register struct rb_node *tmp;
				__rb_rotate_left(parent, root);
				tmp = parent;
				parent = node;
				node = tmp;
			}
 
			rb_set_black(parent);
			rb_set_red(gparent);
			__rb_rotate_right(gparent, root);
		} else {
			{
				register struct rb_node *uncle = gparent->rb_left;
				if (uncle && rb_is_red(uncle))
				{
					rb_set_black(uncle);
					rb_set_black(parent);
					rb_set_red(gparent);
					node = gparent;
					continue;
				}
			}
 
			if (parent->rb_left == node) {
				register struct rb_node *tmp;
				__rb_rotate_right(parent, root);
				tmp = parent;
				parent = node;
				node = tmp;
			}
 
			rb_set_black(parent);
			rb_set_red(gparent);
			__rb_rotate_left(gparent, root);
		}
	}
 
	rb_set_black(root->rb_node);
}
 
static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
		struct rb_root *root) {
	struct rb_node *other;
 
	while ((!node || rb_is_black(node)) && node != root->rb_node) {
		if (parent->rb_left == node) {
			other = parent->rb_right;
			if (rb_is_red(other)) {
				rb_set_black(other);
				rb_set_red(parent);
				__rb_rotate_left(parent, root);
				other = parent->rb_right;
			}
			if ((!other->rb_left || rb_is_black(other->rb_left))
					&& (!other->rb_right || rb_is_black(other->rb_right))) {
				rb_set_red(other);
				node = parent;
				parent = rb_parent(node);
			} else {
				if (!other->rb_right || rb_is_black(other->rb_right))
				{
					rb_set_black(other->rb_left);
					rb_set_red(other);
					__rb_rotate_right(other, root);
					other = parent->rb_right;
				}
				rb_set_color(other, rb_color(parent));
				rb_set_black(parent);
				rb_set_black(other->rb_right);
				__rb_rotate_left(parent, root);
				node = root->rb_node;
				break;
			}
		} else {
			other = parent->rb_left;
			if (rb_is_red(other)) {
				rb_set_black(other);
				rb_set_red(parent);
				__rb_rotate_right(parent, root);
				other = parent->rb_left;
			}
			if ((!other->rb_left || rb_is_black(other->rb_left))
					&& (!other->rb_right || rb_is_black(other->rb_right))) {
				rb_set_red(other);
				node = parent;
				parent = rb_parent(node);
			} else {
				if (!other->rb_left || rb_is_black(other->rb_left))
				{
					rb_set_black(other->rb_right);
					rb_set_red(other);
					__rb_rotate_left(other, root);
					other = parent->rb_left;
				}
				rb_set_color(other, rb_color(parent));
				rb_set_black(parent);
				rb_set_black(other->rb_left);
				__rb_rotate_right(parent, root);
				node = root->rb_node;
				break;
			}
		}
	}
	if (node)
		rb_set_black(node);
}
 
void rb_erase(struct rb_node *node, struct rb_root *root) {
	struct rb_node *child, *parent;
	int color;
 
	if (!node->rb_left)
		child = node->rb_right;
	else if (!node->rb_right)
		child = node->rb_left;
	else {
		struct rb_node *old = node, *left;
 
		node = node->rb_right;
		while ((left = node->rb_left) != NULL)
			node = left;
 
		if (rb_parent(old)) {
			if (rb_parent(old)->rb_left == old)
				rb_parent(old)->rb_left = node;
			else
				rb_parent(old)->rb_right = node;
		} else
			root->rb_node = node;
 
		child = node->rb_right;
		parent = rb_parent(node);
		color = rb_color(node);
 
		if (parent == old) {
			parent = node;
		} else {
			if (child)
				rb_set_parent(child, parent);
			parent->rb_left = child;
 
			node->rb_right = old->rb_right;
			rb_set_parent(old->rb_right, node);
		}
 
		node->rb_parent_color = old->rb_parent_color;
		node->rb_left = old->rb_left;
		rb_set_parent(old->rb_left, node);
 
		goto color;
	}
 
	parent = rb_parent(node);
	color = rb_color(node);
 
	if (child)
		rb_set_parent(child, parent);
	if (parent) {
		if (parent->rb_left == node)
			parent->rb_left = child;
		else
			parent->rb_right = child;
	} else
		root->rb_node = child;
 
	color: if (color == RB_BLACK
		)
		__rb_erase_color(child, parent, root);
}
/*
 * This function returns the first node (in sort order) of the tree.
 */
struct rb_node *rb_first(const struct rb_root *root) {
	struct rb_node *n;
 
	n = root->rb_node;
	if (!n)
		return NULL;
	while (n->rb_left)
		n = n->rb_left;
	return n;
}
 
struct rb_node *rb_last(const struct rb_root *root) {
	struct rb_node *n;
 
	n = root->rb_node;
	if (!n)
		return NULL;
	while (n->rb_right)
		n = n->rb_right;
	return n;
}
 
struct rb_node *rb_next(const struct rb_node *node) {
	struct rb_node *parent;
 
	if (rb_parent(node) == node)
		return NULL;
 
	/* If we have a right-hand child, go down and then left as far
	 as we can. */
	if (node->rb_right) {
		node = node->rb_right;
		while (node->rb_left)
			node = node->rb_left;
		return (struct rb_node *) node;
	}
 
	/* No right-hand children.  Everything down and left is
	 smaller than us, so any 'next' node must be in the general
	 direction of our parent. Go up the tree; any time the
	 ancestor is a right-hand child of its parent, keep going
	 up. First time it's a left-hand child of its parent, said
	 parent is our 'next' node. */
	while ((parent = rb_parent(node)) && node == parent->rb_right)
		node = parent;
 
	return parent;
}
 
struct rb_node *rb_prev(const struct rb_node *node) {
	struct rb_node *parent;
 
	if (rb_parent(node) == node)
		return NULL;
 
	/* If we have a left-hand child, go down and then right as far
	 as we can. */
	if (node->rb_left) {
		node = node->rb_left;
		while (node->rb_right)
			node = node->rb_right;
		return (struct rb_node *) node;
	}
 
	/* No left-hand children. Go up till we find an ancestor which
	 is a right-hand child of its parent */
	while ((parent = rb_parent(node)) && node == parent->rb_left)
		node = parent;
 
	return parent;
}
 
void rb_replace_node(struct rb_node *victim, struct rb_node *new,
		struct rb_root *root) {
	struct rb_node *parent = rb_parent(victim);
 
	/* Set the surrounding nodes to point to the replacement */
	if (parent) {
		if (victim == parent->rb_left)
			parent->rb_left = new;
		else
			parent->rb_right = new;
	} else {
		root->rb_node = new;
	}
	if (victim->rb_left)
		rb_set_parent(victim->rb_left, new);
	if (victim->rb_right)
		rb_set_parent(victim->rb_right, new);
 
	/* Copy the pointers/colour from the victim to the replacement */
	*new = *victim;
}

rbtree实例

若要使用上面的rbtree，需要根据需要实现自己的rbtree插入和查询函数。本博文实现如下：

//关联到红黑树的数据结构
struct int_rbtree {
	struct rb_node rbnode;
	int i;
};
 
//红黑树最大节点数目
#define MAX_NUM 20
 
struct int_rbtree * int_search(struct rb_root *root, int key) {
	struct rb_node *node = root->rb_node;
	while (node) {
		struct int_rbtree *data = container_of(node, struct int_rbtree, rbnode);
		if (key < data->i)
			node = node->rb_left;
		else if (key > data->i)
			node = node->rb_right;
		else
			return data;
	}
	return NULL;
}
 
int int_insert(struct rb_root *root, struct int_rbtree *data) {
	struct rb_node **newnode = &(root->rb_node), *parent = NULL;
	/* Figure out where to put new node */
	while (*newnode) {
		struct int_rbtree *thisnode =
				container_of(*newnode, struct int_rbtree, rbnode);
		parent = *newnode;
		if (data->i < thisnode->i)
			newnode = &((*newnode)->rb_left);
		else if (data->i > thisnode->i)
			newnode = &((*newnode)->rb_right);
		else
			return 0;
	}
	/* Add new node and rebalance tree. */
	rb_link_node(&data->rbnode, parent, newnode);
	rb_insert_color(&data->rbnode, root);
	return 1;
}

 测试主程序

void testrbtree() {
	struct rb_node *node; // rb node
	struct rb_root root = RB_ROOT; //root node
	int i = 0;
 
	//insert
	for (i = 0; i < MAX_NUM; i = i + 2) {
		//分配节点，删除时需释放节点
		struct int_rbtree *inttree = malloc(sizeof(struct int_rbtree));
		memset(inttree, 0, sizeof(struct int_rbtree));
		inttree->i = i;
 
		int res = int_insert(&root, inttree);
		if (res) {
			printf("insert %d succeed\n", i);
		} else {
			printf("insert %d failed\n", i);
		}
	}
 
	for (i = 1; i < MAX_NUM; i = i + 2) {
		struct int_rbtree *inttree = malloc(sizeof(struct int_rbtree));
		memset(inttree, 0, sizeof(struct int_rbtree));
		inttree->i = i;
		int res = int_insert(&root, inttree);
		if (res) {
			printf("insert %d succeed\n", i);
		} else {
			printf("insert %d failed\n", i);
		}
	}
 
	//travel
	printf("begin to travel tree\n");
	for (node = rb_first(&root); node; node = rb_next(node)) {
		printf("key %d \n", rb_entry(node, struct int_rbtree, rbnode)->i);
	}
	printf("end to travel tree\n");
 
	//delete
	srand(time(NULL));
	int key = rand() % MAX_NUM;
	struct int_rbtree *data = int_search(&root, key);
	if (NULL != data) {
		rb_erase(&data->rbnode, &root);
		//删除时需释放节点
		free(data);
		data = NULL;
		printf("is going to delete key %d \n", key);
	} else {
		printf("key %d is not in the tree\n", key);
		return;
	}
	data = int_search(&root, key);
	if (NULL != data) {
		printf("delete key %d failed\n", key);
	} else {
		printf("delete key  %d succeed\n", key);
	}
 
	return;
}

只要在main函数中调用这个测试函数即可。

同时，有需要的朋友可以从http://download.csdn.net/detail/it_pcode/6632917下载本博文代码。