红黑树作为同样提供O(log n)查询的树结构（其实准确点说不是log n，红黑树虽然是平衡树，但是没有AVL树那么平衡），通常用于关联数组的使用中，相对于AVL树，在插入和删除操作中能够以更少的调节操作来位置平衡，AVL树的平衡唯一参考标准就是其高度，在插入和删除节点时需要检查调整在搜索路径上造成的“影响”，可能需要多个调整步骤来维持树的平衡。
红黑树的节点具有一个颜色属性，平衡是根据其定义的五个特性来维持的：
1.节点颜色为红或者为黑
2.根节点为黑
3.叶子节点为黑（叶子作为结束标志，可以以空表示或者自定义实体节点作为结束标志，后面树中没有画出来）
4.红色节点必须有两个黑色子节点（子节点可以为结束标志）
5.任一节点出发到叶节点路径上包含相同数量的黑色节点
提前预告：最重要的就是特性4,5，因为后续的插入节点操作主要依靠特性4来调整平衡，删除节点操作主要依靠特性5来调整平衡。整个后面的操作都是依赖这5条要求，所以一定要记熟了（下面会反复提，帮助记忆）。
由这5个特性要求可以看出，红黑树的平衡调节操作有两种类型：
1.节点变色
2.子树旋转
相对于AVL树，调节操作较少，能够提供良好的统计性能（插入最多旋转两次，删除最多旋转三次，节点变色不提）。因为保证的是更大范围上的平衡（颜色+高度），AVL树的平衡（高度），所以需要考虑的情况就相对比较多，不只是AVL树中的左旋，右旋。
(1) 关于颜色要求，之前特性4说过，红不能与红相邻，意思就是红色节点父节点只能为黑，子节点只能为黑。也就是说红黑树中存在节点为红时，则父节点必存在且为黑，子节点若存在则必为黑，不存在也可，因为叶子节点也是黑色。
(2) 关于高度要求，能够保证一条路径上的高度不能超过另一条路径高度的两倍。两倍的情况：一个为纯黑路线，一个为黑红交替路线，有图有真相：
左边属于纯黑路线，两个节点，右边属于黑红交替路线，四个节点，叶子节点不计算在内。
节点插入操作相对于删除操作来讲，考虑的情况比较少，所以操作比较简单
在正式插入节点之前，先预演一下经常使用的变换，口说无凭，有图有真相
从左往右是黑色上提，从右往左是黑色下方
在树的局部子树中存在节点颜色不一致情况，如上图所示时，根据特性5，黑色和红色的向上变换或者向下变换，该子树对外呈现的结果都是满足特性5的。
至于因为颜色变换导致特性4的冲突，在当前步骤不关心。
在节点的插入时，将待插入的节点创建为红色节点，目的当然是避免在每一次插入都导致特性5不符，需要进行平衡调节。
插入节点会遇到的情形
情形1：当前判断的节点为根节点，节点直接将当前节点变色为黑即可。
当前节点如果为新插入的节点，即树为空，此时直接变色为黑即可；如果是迭代调整后的当前节点为根节点，即已经“上诉”，将调整情况反馈到根节点，则此时只需要直接将节点颜色变为黑即可满足平衡。
情形2：树不为空，待插入节点的父节点为黑，则直接插入，特性4不会不符，无需调整。
情形3：树不为空，带插入节点的父节点为红，特性4不符：
情形3.1：父节点为红，叔节点为红。因为父节点为红，则祖父节点为黑，此时情形如下图所示：
f：父节点，u：叔节点，g：祖父节点，n：新插入节点
此时的情形如上面提到的情景演示中的颜色变换场景，所以此时的调节操作为：
将父节点和叔节点的颜色变为黑，祖父节点颜色变为红，将祖父节点作为新节点n，进行迭代平衡调节，则在新一轮的判断中，n节点属于根节点，直接颜色变为黑即可。
所以在该情形中不需要考虑新插入节点n是左节点还是右节点。
代码演示：
叔节点为红色：
/* check_case1解决问题，父节点红色，则祖父节点为黑色，叔节点为红色的情况 */ void check_case1(node t){//叔节点为红 node uncle=uncle(t); t.parent.color=false;//父节点变黑 uncle.color=false;//叔节点变黑 uncle.parent.color=true;//祖父节点变红 insert_check(uncle.parent);//以祖父节点作为新的检查点 }
情形3.2：父节点为红，叔节点为叶子节点或者叔节点为黑色节点。如图所示：
叔节点为叶子节点或者黑色节点的时候，为了保持平衡，解决特性4的冲突问题，由AVL树得来的经验可知，此时需要旋转了，因为节点包含颜色属性，所以在旋转时需要更改颜色。
在旋转之前，先讲明该情形的由来。如果n为新插入节点，则由特性5知，叔节点u为叶子节点；如果n为由情形3.1中的祖父节点g更换而来的节点，则此时的叔节点u为黑色节点。
不过既然叔节点u不为红色节点，则不需要考虑u到底是哪种情形，无关紧要。相比较与AVL树的节点结构，此时的节点包含了指向父节点的parent属性，而且红黑树的旋转操作属于局部操作，所以插入或者删除函数不必以递归的方式进行（不需要如此大的消耗运算）。
代码演示：
旋转操作：
node left_rotate(node t){//以t为根节点，左旋 node par=t.parent; node t_rig=t.right; boolean l=false; if(par!=null){ l=check_for_side(t); } t.right=t_rig.left; if(t_rig.left!=null){ t_rig.left.parent=t; } t_rig.left=t; t.parent=t_rig; t_rig.parent=par; if(par!=null){ if(l){ par.left=t_rig; }else{ par.right=t_rig; } } if(t_rig.parent==null){ root=t_rig; } return t_rig; } node right_rotate(node t){//以t为根节点，右旋 node par=t.parent; node t_lef=t.left; boolean l=false; if(par!=null){ l=check_for_side(t); } t.left=t_lef.right; if(t_lef.right!=null){ t_lef.right.parent=t; } t_lef.right=t; t.parent=t_lef; t_lef.parent=par; if(par!=null){ if(l){ par.left=t_lef; }else{ par.right=t_lef; } } if(t_lef.parent==null){ root=t_lef; } return t_lef; } 情形3.2.1：n节点为f节点左孩子，f为g节点左孩子，或者n为f节点右孩子，f为g节点右孩子，即红色节点都在一根绳上，以左边为例，旋转操作如下：
更改父节点f和祖父节点g的颜色，以g节点为根右旋，旋转操作在AVL树中已经说过，此时父节点f的右孩子没有画出来。
情形3.2.2：n节点为f节点的左孩子，f节点为g节点的右孩子，或者n为f节点的右孩子，f为g节点的左孩子，即红色节点存在“拐弯”情景，以“右拐弯”为例，此时的旋转操作如下：
该选择操作之后，以f节点为新的n节点，进行迭代平衡调节，则进入情形3.2.1所描述的场景。
代码演示：
叔节点不为红色：
/* check_case2解决问题，父节点红色，则祖父节点为黑色，叔节点不为红色的情况 直接插入新节点不会出现这种情况，因为祖父节点到叔节点和到父节点情况，违背红黑树特性5 所以这种情况是由check_case1变化颜色导致的 */ void check_case2(node t){//叔节点为黑 if(t==t.parent.right&&t.parent==grandparent(t).left){//左右拐弯 t=left_rotate(t.parent);//以父节点为根左旋，将新的父节点返回 t.color=false; t.parent.color=true; t=right_rotate(t.parent);//以父节点为根右旋，将新的父节点返回 }else if(t==t.parent.left&&t.parent==grandparent(t).right){//右左拐弯 t=right_rotate(t.parent);//以父节点为根右旋，将新的父节点返回 t.color=false; t.parent.color=true; t=left_rotate(t.parent);//以父节点为根左旋，将新的父节点返回 }else if(t==t.parent.left&&t.parent==grandparent(t).left){//左边一条道 t.parent.color=false; t.parent.parent.color=true; t=right_rotate(grandparent(t));//以祖父节点为根右旋 }else if(t==t.parent.right&&t.parent==grandparent(t).right){ t.parent.color=false; t.parent.parent.color=true; t=left_rotate(grandparent(t));//以祖父节点为根左旋 } }
这里其实正规来讲应该根据f，n先进行一次旋转，然后以f作为新的n节点，再进行一次平衡调节（这种写法才规范），不过这里顺便就直接两次旋转结束了。
由以上插入过程可以看出来，插入节点最多进行两次旋转操作即可达成平衡状态，变色操作不计入。主要的操作都是通过对叔节点的判断来进行选择执行的。
代码演示：
插入节点：
void insert_check(node t){//插入检查 if(t.parent==null){//如果问题已经上升到根节点，则就是check的最后一步 t.color=false;//下层都已经整理好，直接改根节点为黑色 root=t; }else{ if(t.parent.color){//父节点存在，且为红 if(uncle(t)!=null&&uncle(t).color){//如果叔节点存在且为红 check_case1(t);//叔节点为红 }else{ check_case2(t);//叔节点为黑 } } } }删除节点操作放在下一篇。
