1.红黑树的定义
红黑树是指满足下列条件的二叉搜索树:
(1)每个节点要么是红色，要么是黑色
(2)所有的叶节点都是空节点，并且是黑色
(3)如果一个节点是红色，那么它的两个子节点都是黑色
(4)节点到其孙子节点的每条简单路径都包含相同数目的黑色节点
(5)根节点永远是黑色的
从根节点到叶节点的黑色节点数被称为树的黑色高度(black-height)。
从根节点到叶节点的路径长度不会超过任何其他路径的两倍。
对于给定的黑色高度为n的红黑树，从根到叶节点的简单路径的最短长度为n-1，最大长度为2*(n-1)。
红黑树在插入和删除操作中，节点可能需要被旋转以保持树的平衡。红黑树的平均和最差搜索时间是O(log2N)
2.红黑树节点的插入过程
插入节点的过程如下:
在树中搜索插入点
新节点将替代某个已经存在的空节点，并且将拥有两个作为子节点的空节点
新节点标记为红色，其父节点的颜色根据红黑树的定义确定，如果需要，对树作调整
给一个红色节点加入两个空的子节点符合性质4，同时，也必须确保红色节点的两个子节点都是黑色的(根据性质3)。尽管如此，当新节点的父节点为红色时，插入红色的子节点将是违反定义的。这时存在两种情况:
(1)情形1:红色父节点的兄弟节点也是红色的
这时可以简单地对上级节点重新着色来解决冲突。当节点B被重新着色之后，应该重新检验更大范围内树节点的颜色，以确保整棵树符合定义的要求。结束时根节点应该是黑色的，如果它原先是红色的，则红黑树的黑色高度将递增1。
(2)情形2:红色父节点的兄弟节点是黑色的
为了解决问题，需要旋转并对树节点进行重新着色。这时算法将正常结束，因为子树的根节点(A)被着色为黑色，同时，不会引入新的红-红冲突。
3.红黑树节点的结束插入过程
插入节点时，可能会需要重新着色，或者旋转，来保持红黑树的性质。如果旋转完成，那么算法就结束了。那么对于重新着色来说，需要在子树的根节点留下一个红色节点，于是需要继续向上对树进行修整，以保持红黑树的性质。最坏情况下，用户将不得不对树根的所有路径进行处理。
以下是红黑树的定义，其位于<include/linux/rbtree.h>中