文章原文：
rbtree.txt

什么是红黑树，它们有什么作用？

红黑树是一种自平衡的二叉搜索树，用来存储可排序的数据键值对。这不同于基树(radix tree)(用于有效存储稀疏数组，使用长整数索引来插入/访问/删除节点)和哈希表(不能保持有序—用来方便地按序遍历，并且必须针对特定大小和哈希函数进行调整，而rbtrees 可以优雅地存储任意键)。
红黑树类似于 AVL 树，但在最坏场景下为插入和删除提供更快的实时有界性能，最多分别旋转两次和三次，来平衡树），速度稍慢（但仍然是 O(log n)) 查找时间。
引用 Linux Weekly News：
在内核中有大量正在使用的红黑树。deadline和 CFQ I/O 调度器使用 rbtrees 来跟踪请求； 数据包 CD/DVD 驱动程序也是如此。高分辨率计时器代码使用一颗rbtree来组织未完成的计时请求。ext3文件系统在一个红黑树中跟踪目录entry。虚拟内存区域 (VMA) 使用红黑树进行跟踪，epoll 文件描述符、加密密钥和网络也是如此。
此文档包含了linux rbtree实现的使用。有关红黑树的性质和实施的更多信息，请参阅：
Linux Weekly News 关于红黑树的文章
http://lwn.net/Articles/184495/

*关于红黑树的条目：
http://en.wikipedia.org/wiki/Red-black_tree

linux红黑树的实现

linux红黑树的实现在文件"lib/rbtree.c"中。要使用它，请加上"#include <linux/rbtree.h>".
linux红黑树的实现是针对速度的优化，因此比传统树的实现少了一层间接（和更好的缓存位置）。不使用指针来分隔 rb_node 和数据结构，而是将 struct rb_node 的每个实例嵌入到它组织的数据结构中。 不使用比较回调函数的指针，用户应该编写自己的树搜索和插入函数，这些函数调用提供的 rbtree 函数。 锁定也由 rbtree 代码的用户决定。

创建一颗新的红黑树

Data nodes in an rbtree tree are structures containing a struct rb_node member::
一个红黑树中的数据节点是一个包含struct rb_node成员的结构：

struct mytype {
  	struct rb_node node;
  	char *keystring;
  };

当处理一个指向内嵌的struct rb_node的指针时，数据结构必须通过标准宏container_of()来访问，可以通过rb_entry(node, type, member)直接访问单个成员
每个红黑树的根节点是一个rb_root结构，可以通过这样初始化为空:

  struct rb_root mytree = RB_ROOT;

在红黑树中查找一个值

为您的树编写搜索函数相当简单:在root开始，比较每个值，必要时走向左右分支。
例如:

struct mytype *my_search(struct rb_root *root, char *string)
  {
  	struct rb_node *node = root->rb_node;

  	while (node) {
  		struct mytype *data = container_of(node, struct mytype, node);
		int result;

		result = strcmp(string, data->keystring);

		if (result < 0)
  			node = node->rb_left;
		else if (result > 0)
  			node = node->rb_right;
		else
  			return data;
	}
	return NULL;
  }

在红黑树中插入数据

在树中插入数据需要首先搜索插入新节点的位置，然后插入节点并重新平衡（“重新着色”）树。
插入的搜索与之前的搜索不同，它查找要嫁接新节点的指针的位置。 为了重新平衡，新节点还需要一个到其父节点的链接。
例如：

 int my_insert(struct rb_root *root, struct mytype *data)
  {
  	struct rb_node **new = &(root->rb_node), *parent = NULL;

  	/* Figure out where to put new node */
  	while (*new) {
  		struct mytype *this = container_of(*new, struct mytype, node);
  		int result = strcmp(data->keystring, this->keystring);

		parent = *new;
  		if (result < 0)
  			new = &((*new)->rb_left);
  		else if (result > 0)
  			new = &((*new)->rb_right);
  		else
  			return FALSE;
  	}

  	/* Add new node and rebalance tree. */
  	rb_link_node(&data->node, parent, new);
  	rb_insert_color(&data->node, root);

	return TRUE;
  }

删除或替换红黑树中的数据

为删除树中一个已存在的节点，这样调用：

  void rb_erase(struct rb_node *victim, struct rb_root *tree);

例如：

  struct mytype *data = mysearch(&mytree, "walrus");

  if (data) {
  	rb_erase(&data->node, &mytree);
  	myfree(data);
  }

要将树中的现有节点替换为具有相同键的新节点，请调用：

void rb_replace_node(struct rb_node *old, struct rb_node *new,
  			struct rb_root *tree);

这种方式替换一个节点不需要对树重新排序:如果一个新节点没有与旧节点相同的键，那红黑树很可能会崩溃。

遍历树中存储的元素(按序遍历)

提供了四个函数来按序遍历红黑树中的内容。这些适用于任意树，不需要修改或包装（除了锁定目的）::

  struct rb_node *rb_first(struct rb_root *tree);
  struct rb_node *rb_last(struct rb_root *tree);
  struct rb_node *rb_next(struct rb_node *node);
  struct rb_node *rb_prev(struct rb_node *node);

要开始遍历，用一个指向根节点的指针来调用rb_first()或者rb_last()，会返回一个树中包含的第一个或者最后一个元素的节点结构。要继续的话，调用rb_next()或者rb_prev()来获取下一个或者上一个节点。当没有节点时会返回NULL指针。
迭代器函数返回一个指向嵌入结构 rb_node 的指针，可以使用 container_of() 宏从中访问包含的数据结构，并且可以通过 rb_entry(node, type, member) 直接访问各个成员。
例如：

  struct rb_node *node;
  for (node = rb_first(&mytree); node; node = rb_next(node))
	printk("key=%s\n", rb_entry(node, struct mytype, node)->keystring);

缓存红黑树

计算最左边（最小）节点对于二叉搜索树来说是一项非常常见的任务，例如对于遍历或用户依赖于他们自己的逻辑的特定顺序。 为此，用户可以使用 struct rb_root_cached 将 O(logN) 的rb_first() 调用优化为简单的指针获取，从而避免潜在的昂贵的迭代。这是在维护的运行时开销可以忽略不计的情况下完成的；但是内存占用更大。

和rb_root结构相似，缓存红黑树可以这样初始化为空：

struct rb_root_cached mytree = RB_ROOT_CACHED;

缓存红黑树只是一个普通的 rb_root，带有一个额外的指针来缓存最左边的节点。这允许rb_root_cached 存在于 rb_root 所在的任何地方，这允许支持增强树以及仅几个额外的接口：

  struct rb_node *rb_first_cached(struct rb_root_cached *tree);
  void rb_insert_color_cached(struct rb_node *, struct rb_root_cached *, bool);
  void rb_erase_cached(struct rb_node *node, struct rb_root_cached *);

插入和删除都可以分别调用他们在增强树中对应的部分：

  void rb_insert_augmented_cached(struct rb_node *node, struct rb_root_cached *,
				  bool, struct rb_augment_callbacks *);
  void rb_erase_augmented_cached(struct rb_node *, struct rb_root_cached *,
				 struct rb_augment_callbacks *);

对增强红黑树的支持

增强rbtree 是一种每个节点中存储了“一些”附加数据的rbtree，其中节点 N 的附加数据必须是以 N 为根的子树中所有节点内容的函数。此数据可用于为 rbtree 增加一些新功能。增强的 rbtree 是一个构建在基本 rbtree 基础设施之上的可选功能。需要此功能的 rbtree 用户必须在插入和删除节点时使用用户提供的增强回调来调用增强函数。
实现增强红黑树操作的c文件必须包含<linux/rbtree_augmented.h>而不是<linux/rbtree.h>.注意linux/rbtree_augmented.h.请注意， linux/rbtree_augmented.h 公开了一些您不希望依赖的rbtree 实现细节；请坚持使用文档中的 API，并且不要在头文件中包含 <linux/rbtree_augmented.h> 以尽量减少您的用户意外依赖此类实现细节的机会。
插入的时候，用户必须根据被插入节点的路径更新附加信息，然后正常调用rb_link_node和rb_augment_inserted()而不是调用rb_insert_color()。如果rb_augment_inserted()重平衡红黑树，它将回调一个用户提供的函数来更新受影响的子树中的附加信息。
当删除一个节点时，用户必须调用rb_earse_augmented()而不是rb_earse()。rb_erase_augmented会回调用户提供的函数来更新受影响的子树中的附加信息。

在这两种情况下(插入和删除)，回调都是通过 struct rb_augment_callbacks 提供的。
必须定义 3 个回调：

• 一个传播回调，它更新给定节点及其祖先的附加值，直到给定的停止点（或 NULL 以一直更新到根）

• 一个复制回调，将给定子树的附加值复制到新分配的子树根。

• 一个树旋转的回调，将给定子树的附加值复制到新分配的子树根，并重新计算前子树根的附加信息。

rb_erase_augmented() 编译后的代码可能会内联传播和复制回调，这会导致函数很大，因此每个增强的 rbtree 用户都应该有单个 rb_erase_augmented() 调用点，以限制编译代码的大小。

示例用法
^^^^^^^^^^^^
区间树(Interval tree)是增强红黑树的一个例子。参考 - Cormen、Leiserson、Rivest 和 Stein 的“Introduction to Algorithms”。
有关区间树的更多详细信息：
经典rbtree有单个键而且它不能直接用来存储像[lo:hi]这样的区间范围，也不能快速查找与新 lo:hi 的任何重叠，或者查找是否与新 lo:hi 完全匹配。
但是，可以扩充 rbtree 以结构化的方式存储此类区间范围，从而可以进行有效的查找和精确匹配。
每个节点中存储的“额外信息”是其后代节点中的最大 hi (max_hi) 值。 只需查看节点及其直接子节点即可在每个节点上维护此信息。 这将用于在O(log n) 内查找最低匹配（所有可能匹配中的最低起始地址），例如：

  struct interval_tree_node *
  interval_tree_first_match(struct rb_root *root,
			    unsigned long start, unsigned long last)
  {
	struct interval_tree_node *node;

	if (!root->rb_node)
		return NULL;
	node = rb_entry(root->rb_node, struct interval_tree_node, rb);

	while (true) {
		if (node->rb.rb_left) {
			struct interval_tree_node *left =
				rb_entry(node->rb.rb_left,
					 struct interval_tree_node, rb);
			if (left->__subtree_last >= start) {
				/*
				 * Some nodes in left subtree satisfy Cond2.
				 * Iterate to find the leftmost such node N.
				 * If it also satisfies Cond1, that's the match
				 * we are looking for. Otherwise, there is no
				 * matching interval as nodes to the right of N
				 * can't satisfy Cond1 either.
				 */
				node = left;
				continue;
			}
		}
		if (node->start <= last) {		/* Cond1 */
			if (node->last >= start)	/* Cond2 */
				return node;	/* node is leftmost match */
			if (node->rb.rb_right) {
				node = rb_entry(node->rb.rb_right,
					struct interval_tree_node, rb);
				if (node->__subtree_last >= start)
					continue;
			}
		}
		return NULL;	/* No match */
	}
  }

插入和删除是使用的下面的增强回调来定义的：

  static inline unsigned long
  compute_subtree_last(struct interval_tree_node *node)
  {
	unsigned long max = node->last, subtree_last;
	if (node->rb.rb_left) {
		subtree_last = rb_entry(node->rb.rb_left,
			struct interval_tree_node, rb)->__subtree_last;
		if (max < subtree_last)
			max = subtree_last;
	}
	if (node->rb.rb_right) {
		subtree_last = rb_entry(node->rb.rb_right,
			struct interval_tree_node, rb)->__subtree_last;
		if (max < subtree_last)
			max = subtree_last;
	}
	return max;
  }

  static void augment_propagate(struct rb_node *rb, struct rb_node *stop)
  {
	while (rb != stop) {
		struct interval_tree_node *node =
			rb_entry(rb, struct interval_tree_node, rb);
		unsigned long subtree_last = compute_subtree_last(node);
		if (node->__subtree_last == subtree_last)
			break;
		node->__subtree_last = subtree_last;
		rb = rb_parent(&node->rb);
	}
  }

  static void augment_copy(struct rb_node *rb_old, struct rb_node *rb_new)
  {
	struct interval_tree_node *old =
		rb_entry(rb_old, struct interval_tree_node, rb);
	struct interval_tree_node *new =
		rb_entry(rb_new, struct interval_tree_node, rb);

	new->__subtree_last = old->__subtree_last;
  }

  static void augment_rotate(struct rb_node *rb_old, struct rb_node *rb_new)
  {
	struct interval_tree_node *old =
		rb_entry(rb_old, struct interval_tree_node, rb);
	struct interval_tree_node *new =
		rb_entry(rb_new, struct interval_tree_node, rb);

	new->__subtree_last = old->__subtree_last;
	old->__subtree_last = compute_subtree_last(old);
  }

  static const struct rb_augment_callbacks augment_callbacks = {
	augment_propagate, augment_copy, augment_rotate
  };

  void interval_tree_insert(struct interval_tree_node *node,
			    struct rb_root *root)
  {
	struct rb_node **link = &root->rb_node, *rb_parent = NULL;
	unsigned long start = node->start, last = node->last;
	struct interval_tree_node *parent;

	while (*link) {
		rb_parent = *link;
		parent = rb_entry(rb_parent, struct interval_tree_node, rb);
		if (parent->__subtree_last < last)
			parent->__subtree_last = last;
		if (start < parent->start)
			link = &parent->rb.rb_left;
		else
			link = &parent->rb.rb_right;
	}

	node->__subtree_last = last;
	rb_link_node(&node->rb, rb_parent, link);
	rb_insert_augmented(&node->rb, root, &augment_callbacks);
  }

  void interval_tree_remove(struct interval_tree_node *node,
			    struct rb_root *root)
  {
	rb_erase_augmented(&node->rb, root, &augment_callbacks);
  }