之所以称为红黑树的原因就在于它的每个节点都被着色为红色或黑色。这些节点颜色被用来检测树的平衡性。但需要注意的是，红黑树并不是严格意义上的平衡二叉树，恰恰相反，红黑树放松了平衡二叉树的某些要求，由于一定限度的不平衡，红黑树的性能得到了提升。

从根节点到叶节点的黑色节点数被称为树的黑色高度（black-height）。前面关于红黑树的性质保证了从根节点到叶节点的路径长度不会超过任何其他路径的两倍。因此，对于给定的黑色高度为n的红黑树，从根到叶节点的简单路径的最短长度为n−1，最大长度为2×(n−1)。

红黑树在插入和删除操作中，节点可能需要被旋转以保持树的平衡。红黑树的平均和最差搜索时间都是O(log2N)。在实际应用中，红黑树的统计性能要好于严格平衡二叉树（如AVL树），但极端性能略差。

红黑树的定义

红黑树是指满足下列条件的二叉搜索树。 }性质1：每个节点要么是红色，要么是黑色（后面将说明）。 }性质2：所有的叶节点都是空节点，并且是黑色的。 }性质3：如果一个节点是红色的，那么它的两个子节点都是黑色的。 }性质4：节点到其子孙节点的每条简单路径都包含相同数目的黑色节点。 }性质5：根节点永远是黑色的。

红黑树节点的插入过程 }插入节点的过程如下。在树中搜索插入点。

新节点将替代某个已经存在的空节点，并且将拥有两个作为子节点的空节点。

新节点标记为红色，其父节点的颜色根据红黑树的定义确定，如果需要，对树作调整。

存在两种情况 ：

（1）情形1：红色父节点的兄弟节点也是红色的 ？

（2）情形2：红色父节点的兄弟节点是黑色的？

3）红黑树节点的结束插入过程 }插入结点时，可能会需要重新着色，或者旋转，来保持红黑树的性质。如果旋转完成，那么算法就结束了。对于重新着色来说，读者需要在子树的根节点留下一个红色节点，于是需要继续向上对树进行修整，以保持红黑树的性质。最坏情况下，用户将不得不对到树根的所有路径进行处理。

ARM Linux中红黑树使用实例

首先，以下是红黑树的定义，其位于

中。

struct rb_node

{

struct rb_node *rb_parent;

int rb_color;

#define RB_RED 0

#define RB_BLACK 1

struct rb_node *rb_right;

struct rb_node *rb_left;

};

红黑树的旋转代码

static void __rb_rotate_left(struct rb_node *node, struct rb_root *root)

{

/*设置right*/ } struct rb_node *right = node->rb_right; } /*把right的左子树赋给node的右子树*/ }

if ((node->rb_right = right->rb_left))

right->rb_left->rb_parent = node;

right->rb_left = node;

/*把node的父节点赋给right的父节点，并且判断是否为0/

if ((right->rb_parent = node->rb_parent))

{

if (node == node->rb_parent->rb_left)

node->rb_parent->rb_left = right;

else

node->rb_parent->rb_right = right;

}

else

root->rb_node = right;

node->rb_parent = right;

}

数据结构在嵌入式中的应用实例之一，so cool！