最近觉得C++生疏了，拿出侯捷的《STL源码剖析》翻了翻，看到C++ set，map底层实现机制，其中采用的就是红黑树数据结构，另外Linux内核对内存管理和进程调度都用到了红黑树，看来它不能让人小视。自己从网上和书上重新看了下红黑树，把个人的理解放到博客上，跟大家讨论，也作为自己的重新梳理的方式。
红黑树(Red-Black Tree)
它是在1972 年由Rudolf Bayer 发明的，他称之为"对称二叉B 树"，它现代的名字是在Leo J. Guibas 和Robert Sedgewick 于1978 年写的一篇论文中获得的。它是复杂的，但它的操作有着良好的最坏情况运行时间，并且在实践中是高效的: 它可以在O(log n)时间内做查找，插入和删除，这里的n 是树中元素的数目。
红黑树本身是二叉搜索树，同时它应该始终满足五个性质：
红黑树每个节点颜色非红即黑；
根节点颜色必须为黑色；
每个叶节点(指的NULL指针节点)颜色均为黑；
不可以出现相邻的两个红色节点；
对于每个节点，其左右子树中的黑色节点个数必须相等；
一棵正常的红黑树如下图(引自wiki)：
红黑树的难点在于插入和删除操作涉及到的红黑树重新调整问题，关于原理性问题，有篇文章《红黑树原理详解》，作者：余强. 讲的比较清楚，也可以参照《CLRS》第13章红黑树的描述，以下主要结合C语言实现代码加注释的方式进行分析，编完代码后进行了一定的测试，如果还存在问题，可回帖反馈，我会进行更改，谢谢。
插入操作：
新插入一个节点时，其颜色未定，可以选择黑色也可以选择红色，但是仔细看下上述红黑树5个性质，会发现，插入黑色节点必然会导致性质5被破坏(空树除外)，而如果插入红色节点，则可能破坏性质4，这其中有一定的几率无需调整红黑树(父节点为黑色)，因此插入的新节点颜色设置为红色，以下插入操作均不考虑是空树和父节点是黑色的情况，因为这两种情况无需进行调整。
而如果发生上面说的破坏性质4，即新插入节点与父节点均是红色的情况，则我们需要将这两个相邻红色节点分开，以使性质4重新被满足，而涉及到的调整则需要看新插入节点的父节点、叔父节点以及祖父节点颜色而定，可以分情况讨论之；
首先考虑叔父节点的颜色，这里以叔父节点的颜色来划分接下来的调整操作是因为插入的新节点与其父节点均为红色，目的为了将这两个红色节点分开，可以通过性质推理知祖父节点必然为黑色，因为插入新节点前，树是满足性质的，而父节点颜色为红色，因此祖父节点必然为黑色。调整颜色过程中，如果需要改变父节点颜色，则必然需要考虑叔父节点，因此叔父节点是插入操作分情况讨论的关键点。
在介绍插入后红黑树重新调整前，首先引入左旋操作和右旋操作，在红黑树所有调整中，均采用左右旋操作解决节点移动问题，左右旋操作并不破坏二叉搜索树的性质，因此不会引入额外的重新对红黑树进行排序的负担，具体左右旋操作可参考其他红黑树相关文章或下文中对于左右旋操作的代码分析加注释；
重回正题，首先对插入操作所需要的调整进行分情况讨论，再次强调父节点为黑色的情况不分析，因为无需作过多调整，所以下面操作中父节点颜色均为红色：
叔父节点颜色为黑色：
以上两种情况为插入节点的父节点在祖父节点的左子树情况，当位于右子树时，情况类似。
以上两种情况，即新插入节点分别为外侧插入和内侧插入时，需要将父节点和新节点的相邻红色分开，该两种情况下叔父节点应该为NULL节点(如果有不正确，请大家指正
)
因此调整操作是以祖父节点为基点，父节点和祖父节点的连接为轴进行右旋转（内侧插入即第二种情况必须先以父节点为基点进行左旋调整），然后改变父节点和祖父节点的颜色。
新节点外侧插入情况：以祖父节点为基点，右单选，改变父节点和祖父节点颜色；
