红黑树的插入操作和BST也差不多，同样在插入以后需要像AVL树那样向上调整，但是红黑树因为每个节点都存在parent指针，所以向上调整可以通过迭代来实现，而不需要像AVL树那样要用递归回溯。红黑树向上调整的过程实际上就是不断将新插入的红节点向上移动，直至它的父节点为黑为止，这样就存在三种情况（之所以不存在其他情况，完全是由于红黑树的性质决定的）。并且红黑树的根节点和根节点的父节点的Color一定是Black，所以这个向上调整的过程就一定会停止，也就是最终一定能跳出循环，在跳出循环之后需要将根节点的Color赋值为Black。
以下三种情况均针对待调整节点在其祖父节点的左子树中时进行分析，若在右子树中时，做对称操作即可。
Case One这种情况中,待调整节点是C节点，C节点的父节点B和父节点B的Sibling节点E的Color均为Red（需要注意的是这里C、D、E的左右子树可能为空，可能不为空，且A节点也可能不是根节点）。遇到这种情况时，将C节点的父节点B和父节点B的Sibling节点E的Color赋值为Black，并将C节点的祖父节点A赋值为Red，同时将待调整节点变为节点A。因为起初父节点的Color为Red，所以根据性质，C的祖父节点A的Color一定为Black，这样同时调整B和E为Black，可以使沿B和E至叶节点的路径上的Black节点数相同，且消除了B、C均为Red的情况，但是这样一来沿A至叶节点的路径上的Black节点数就增加了一个，因此将A赋值为Red，使得沿A至叶节点的路径上的Black节点数保持和调整前的数量一致，然而我们无法排除A的父节点的Color也是Red的情况，所以将待调整节点变为节点A，在下一次循环中继续调整。
这种情况中，待调整节点是D节点，D节点的父节点B的Color是Red，但是父节点B的Sibling节点E的Color是Black，且D节点是其父节点B的右子节点。此时仅需要以B节点为Pivot做左旋即可，并将待调整节点变为B。在具体实现时还需要注意将记录父节点的变量FNode变为D节点，并进入Case Three。之所以要这样操作，是因为这里的操作仅仅针对两个Red节点，而对于Black节点的操作（例如C节点），起初沿B的左子节点、D的左（C节点）右子节点至叶节点的路径的Black节点数都是相同的，所以旋转操作中移动以C为根节点的子树后，沿B的子节点和D的子节点至叶节点的路径的Black节点数依然是相同的且保持不变。
这种情况中，待调整节点是C节点，C节点的父节点B的Color是Red，但是父节点B的Sibling节点E的Color是Black，且C节点是其父节点B的左子节点。此时仅需要以C节点的祖父节点A作为Pivot做右旋即可，并将原先的父节点B的Color调整为Black，将原先的祖父节点A的Color调整为Red。之所以要这样操作，是因为起初沿C节点的左右子节点、沿D节点和E节点至叶节点的路径的Black节点数是相同的，所以在调整过后沿它们至叶节点的路径上的Black节点数依然是相同的且保持不变，而这样操作却可以通过交换颜色将一个Red节点移动到祖先节点的右子树中，消除了两个Red节点相连的情况，当然旋转后新的子树的根节点B要赋值为Black，以保持从子树的根节点（原先是A，现在是B）的路径的Black节点数保持和原来一样。这里要是Pivot是整棵红黑树的根节点，则需更新Root节点的值。
PtrRBT RBInsert(PtrRBT T, ElementType Val){ PtrRBTNode TempNode = T->Root; PtrRBTNode NewNode = RBCreateNode(T, Val); if(NULL == TempNode){ T->Root = NewNode; NewNode->Parent = T->NullNode; } else{ while(T->NullNode != TempNode){ if(Val < TempNode->Key){ if(T->NullNode == TempNode->Left){ TempNode->Left = NewNode; NewNode->Parent = TempNode; break; } else{ TempNode = TempNode->Left; } } else{ if(T->NullNode == TempNode->Right){ TempNode->Right = NewNode; NewNode->Parent = TempNode; break; } else{ TempNode = TempNode->Right; } } } } T = RBInsertFixUp(T, NewNode); return T; } PtrRBT RBInsertFixUp(PtrRBT T, PtrRBTNode CurrentNode){ PtrRBTNode FNode, GNode, UNode; while(Red == CurrentNode->Parent->Color){ FNode = CurrentNode->Parent; GNode = FNode->Parent; if(GNode->Left == FNode){ UNode = GNode->Right; if(Red == FNode->Color&&Red == UNode->Color){ FNode->Color = UNode->Color = Black; GNode->Color = Red; CurrentNode = GNode; } else{ if(CurrentNode == FNode->Right){ T = RBLeftRotate(T, FNode); CurrentNode = FNode; FNode = CurrentNode->Parent; } FNode->Color = Black; GNode->Color = Red; T = RBRightRotate(T, GNode); } } else{ UNode = GNode->Left; if(Red == FNode->Color&&Red == UNode->Color){ FNode->Color = UNode->Color = Black; GNode->Color = Red; CurrentNode = GNode; } else{ if(CurrentNode == FNode->Left){ T = RBRightRotate(T, FNode); CurrentNode = FNode; FNode = CurrentNode->Parent; } FNode->Color = Black; GNode->Color = Red; T = RBLeftRotate(T, GNode); } } } T->Root->Color = Black; return T; }
Delete