最后我们来探究红黑树的删除算法，相比插入操作，它的情况更复杂一些。因此直接考虑很容易撞到南墙，我们更需要利用转化与化归的思想（还记得高中数学四大思想方法吧，这里一样适用），通过提升变化，把红黑树映射成一颗B-树，并站在后者的角度，反过来理解前者的原理。但我们更需要关心重构操作，也就是一系列的旋转和修复过程，并在此过程中留意他的重构次数都是$O\left( 1 \right)$级别的。
这个删除操作还挺复杂的。。。可以说繁琐到了让人恶心的地步，各位做好心理准备。可以在旁边准备个塑料袋或者盆什么的，省的没地方。。。
先给出一些辅助函数，方便后续使用
Position SearchIn(Position v,int e,Position& parent){//返回指向父节点指针的引用，因为后续要做左值 if (!v || (e == v->value)) return v; //递归基，如果直接命中或不存在则返回 parent=v; //一般情况则是先记下当前节点,然后深入一层。 return SearchIn((e < v->value ? v->left : v->right), e, parent); }//返回值指向命中节点，parent为其父。 Position Search(int target,RedBlackTree T){ return SearchIn(T, target, p); } Position GetParentOf(int e){ Search(e, fir); return p; } //由于我写的结构体里没有parent指针，所以通过这个函数等效获取。 Position GetParentOf(Position T){ //得到T的父节点 Search(T->value, fir); return p; } int IsLChild(Position p){ //判断p点是否为某个节点的左孩子 if (GetParentOf(p) != fir && GetParentOf(p)->left == p) return 1; else return 0; } Position& FromParentTo(Position p){ //返回某个节点来自父亲的指针 if(GetParentOf(p) == fir) return p; //处理P是根的情况 if (GetParentOf(p) ->left ==p) // p is leftChild return GetParentOf(p)->left; else return GetParentOf(p)->right; }