前言
面试微软互联网工程院的过程中，有两面都问到了二叉搜索树的基本操作——删除节点。第一次问到时我跟面试官说自己看过相关内容但是需要时间重新推导，于是他便没有继续追问；但第二次面试官坚持要求我写代码实现，于是在全程高能的情况下几乎重新将其推导了一遍。虽然最后写完还是有小的瑕疵，但可以看出其实面试官也并没能看懂我的实现，后来只是问了问如果我是测试的话，会如何测自己的代码，我大概说了说主要应该考虑二叉树基本形态的边界测试、人工根据代码逻辑构造的分支条件测试和随机构建二叉树的大数据测试。
但是这个细节令我十分疑惑，似乎在面试官们看来，这是个非常基础的操作，不需要太多的思考就应该能够写出代码实现；而在我的印象中，刷算导的时候这个操作明明被分为几种复杂的情况并进行了严格而细致的探讨，可以说实现起来十分繁琐，没有刻意背过的话恐怕很难临场写对，为什么面试官却这么喜欢问呢？
面试结束后跟清华的一位硕士私下交流，才发现问题出在了哪里：原来面试官印象中的BST节点删除算法，应该都是来源于《算法导论》第一、二版的那个简单算法，但算导第三版对这个算法进行了更为严谨细致的修订。我学习的时候，看的就是这个严谨修正过后的版本，因此觉得很复杂很难记，但是对于面试官而言，他们印象中的这个知识点还是来源于旧版书，自然而然就觉得这不算是个复杂的操作。由于AA面撞上了老外面试官，基本这次面试算是已经挂掉了，不过总归是学到了些有用的东西，在此总结分析一下，希望能够有幸为他人解惑。
简单版本
这个简单版的节点删除算法其实我在面试过程中完全自主想出来过，但当时以为是自己纯YY出来的，所以没敢写代码实现。后来才发现，我那个YY的思路其实就是正解，只不过是一个广为人知但却不那么严谨的正解。我们首先分析一下这个做法。
给定一棵二叉查找树和一个关键字，要将包含该关键字的节点删除，我们首先需要找到指向该关键字所在节点的指针z，然后具体要删除的节点可以分为下面三种情况：
z没有子女，则要删除z；z有一个子女，也是删除z；z有两个子女，则是删除z的后继y。
对于前两种情况，不管z具体是其父亲节点的左孩子还是右孩子，我们只需要干净利落地改变z的父亲节点的指针，将其指向NULL或者指向z的子女，则显然可以证明，这个操作一定不会破坏BST的性质。
而在上述的第三种情况中，显然我们知道z的后继y一定存在于z的右子树中，因为前提条件已经保证了z有子女。并且，我们也能够保证，后继y一定属于上述前两种情况，不可能同时具有左右孩子，不然它不符合后继的定义。这样，我们只需要将z与y的关键字数据互换，然后再像前两种操作那样删掉y指向的节点即可。同样容易证明，这样的操作一定不会破坏BST的性质。
严谨版本
考虑STL里面红黑树的实现，它包含一个erase方法，可以将待删除关键字作为参数，也可以输入一个指向待删除节点的指针。再仔细分析上述算法，我们就会很容易发现问题了：如果待删除节点同时包含左右孩子的话，那么我们其实并没有将输入指针所指向的节点删除掉，而是删除掉了BST中另外一个节点！这样的话，如果我们在程序的其他地方需要维持一些指向树中节点的指针，那么当我们实际用到这些指针的时候，它们很可能已经莫名其妙地失效了！访问已经被释放掉的内存位置，在C++中显然是极为禁忌的操作，程序很容易就崩溃掉了，这会是极为严重的BUG。
为此，算导在第三版中重新修订了这个算法，为严谨性而增加了更为复杂的细节讨论。在此我不再赘述算导中是如何描述这个删除操作的，因为书上写得已经足够详细并且严谨。我只想进一步谈谈自己的理解。
首先，对于“简单版本”算法中的前两种情况，显然无需进行任何修改，处理方式还是一模一样；关键在于对第三种情况的处理：如何在一定删除掉指针所指向节点的前提下，调整BST使其维持性质不变。
其实核心思路还是类似的：我们需要寻找待删除节点z的后继。关键在于，找到这个后继之后该怎么做呢？这里就是难点了，需要再分为两种情况讨论。
情况1：z的后继就是其右子树根节点
此时，由于后继的性质，z的后继y一定没有左儿子。这样的话我们把z的左子树连接到y的左儿子，再用y直接替换掉z，则显然一定满足性质：y的左子树中所有节点均小于y，也就意味着没有破坏二叉树的性质。y的右子树没有经过任何修改，同样满足BST的性质，并且经过这个操作之后，我们仅仅删除掉了z本身但保留了其他所有节点，没有丢失任何信息。
情况2：z的后继并非其右子树根节点
这种情况就要稍微复杂一些了，显然我们还是需要用z的后继y来替换掉z，但在此之前需要做额外调整，以维持BST的性质并且不丢失节点。
首先，我们使用y的右孩子替换y，这个操作是相对于y的父亲节点而言的，也就相当于从BST中删除了节点y。由后继的性质，y一定没有左子树，则此时可以认为y节点的左右指针都是NULL。接下来，既然y节点已经“干净”了，我们就可以直接用y节点把z替换掉即可。
上述操作完成后，我们实际上还是保留了z的后继节点y，而删除的是z本身。同时，分析整个操作过程，一共也就仅仅替换了两次节点。可以证明，这两次替换过程中，都保持了BST的性质，第一次替换的正确性是显然的，这里我们只分析第二次替换：考虑y是z的后继，因此显然原本z的左子树中所有关键字小于y；并且由于y被从z的右子树中移除，因此更新后z的右子树中所有元素一定大于y。
综上所述，经过这些分类讨论的操作后，算法删除了指针指向的节点，并且一定保持了BST的性质，故算法正确，且复杂度显然为O(h)。
总结
虽然在最后一面中可以看出，面试官自己也并未深刻理解二叉搜索树的删除操作，包括他在内的很多人一直把一个不严谨的算法当作正解；不过归根结底，闹出这种类似“乌龙”的情况，还是要归咎于自己对算法的理解还不够深刻。以后在刷书的过程中，更是要注意多动手实践，多思考，举一反三，方能有透彻领悟。
无论面试结果如何，必当奋力前行。谨以此文自勉。
2015年1月23日 深夜