首先说一下，关于红黑树有一篇很棒的论文《A dichromatic framework for balanced trees》，作者之一的Robert Sedgewick，想必大家不会陌生。如果有兴趣可以仔细研读一下，里面讲了更多细节的分析，而本文也借鉴了其中的一些思路和配图。
回顾一下之前的结构分析，经验指出：平均而言红黑树大约和AVL树一样深，如此保证了查找效率接近最优。另外他的优点有两个，插入所需要的开销比之前更低，再有就是实践中发生的旋转相对比较少。
而红黑树的具体实现是比较复杂的，这不仅因为可能会发生大量的旋转，还因为一些子树可能是空的（比如10这个节点的右子树），以及处理根的特殊情况（因为没有父节点）。因此我们要用两个标记节点：一个是根；一个是NullNode，类似在伸展树里指示NULL的指针。根标记用来储存$-\infty $和一个真正指向根的右指针。先给出类型声明，因为旋转操作还需要用到，所以继续沿用。
1 #ifndef RB_Tree_h 2 #define RB_Tree_h 3 4 typedef enum{ red,black} Color; 5 6 const int Infinity = 0x3f3f3f3f; 7 const int NegINF = -Infinity -1; 8 struct RedBlackNode; 9 typedef RedBlackNode* RedBlackTree; 10 typedef RedBlackNode* Position; 11 12 struct RedBlackNode { 13 int value,Height; 14 RedBlackTree left; 15 RedBlackTree right; 16 Color col; 17 }; 18 19 Position NullNode=NULL; //needs initialization 20 int max(int a,int b){ return a>b?a:b;} 21 RedBlackTree Insert(int Item,RedBlackTree T); 22 RedBlackTree Delete(int Item,RedBlackTree T); 23 #endif /* RB_Tree_h */ 24 25 static int 26 Height( Position P ) 27 { 28 return P==NULL?-1:P->Height; 29 } 30 31 static Position 32 SingleRotateWithLeft( Position p ) //左-左的情况 33 { 34 Position temp; 35 36 temp = p->left; 37 p->left = temp->right; 38 39 temp->right = p; 40 41 p->Height = max( Height( p->left ), Height( p->right ) ) + 1; 42 temp->Height = max( Height( temp->left ), p->Height ) + 1; 43 44 return temp; /* New root */ 45 } 46 47 static Position 48 SingleRotateWithRight( Position g ) //右-右的情况 49 { 50 Position temp; 51 52 temp = g->right; 53 g->right = temp->left; 54 55 temp->left = g; 56 57 g->Height = max( Height( g->left ), Height( g->right ) ) + 1; 58 temp->Height = max( Height( temp->right ), g->Height ) + 1; 59 60 return temp; /* New root */ 61 }