二叉搜索树删除算法

未讲课时，自己结合网上相关教程做出来的版本

运用递归原理实现二叉搜索树有序删除。首先判断传入地址是否为空；

之后判断pos内的val值，若大于参数val，则删除目标只可能在左子树中，对左子树节点进行重新赋值（若大于则对右子树重新赋值）。若左（右）子树节点数据为参数val，则返回删除后的新节点，反之返回原节点。

接下来对数据val等于参数val的节点pos的情况进行分类讨论：

1. 若pos为叶节点，则与第2（或3）种情况并为一类讨论。

2. 若pos仅有右子树，则将pos赋值为pos右子树（对情况1而言，即为nullptr，亦符合要求），删除原pos变量。

3. 若pos仅有左子树，则将pos赋值为pos左子树，删除原pos变量。

4. 若pos既有左子树又有右子树，此时应当将pos的左子树移动到pos右子树中的最左边的左子树（即中序遍历的下一个位置）之左，随后将pos赋值为pos的右子树节点。最后删除原pos。

分类讨论完成操作后，返回pos值作为双亲节点的子节点。

核心代码

template<typename Type>
BinNode<Type>* BST<Type>::DeleteNode(Type val, BinNode<Type>*& pos) 
{
 if (!pos) return nullptr;

 if (pos->val > val)
   pos->left = DeleteNode(val, pos->left);
 else if (pos->val < val)
   pos->right = DeleteNode(val, pos->right);
 else
 {
   if (!pos->left) //leaf node or only have right child
   {
    auto temp = pos;
    pos = pos->right;
    delete temp;
   }

   else if (!pos->right) // only have left child
   {
    auto temp = pos;
    pos = pos->left;
    delete temp;
   }

   else // both
   {
    auto cursor = pos->right;
    while (cursor->left!=nullptr)
       cursor = cursor->left; //完成后，cursor即为中序遍历情况下的下一个位置

    cursor->left = pos->left;
    auto temp = pos;
    pos = pos->right;
    delete temp;
   }
 }

 return pos;
}

课本上的版本

后来阅读课本时，发现课本上的另外一种更为精妙的方法。

对于前三种情况，课本上的处理方式也没有多大的差别，即：

1. 若pos为叶节点，则与第2（或3）种情况并为一类讨论。
2. 若pos仅有右子树，则将pos赋值为pos右子树（对情况1而言，即为nullptr，亦符合要求），删除原pos变量。
3. 若pos仅有左子树，则将pos赋值为pos左子树，删除原pos变量。

不同的是第4种情况。课本上是怎么做的呢？一句话来说，就是先找到该位置A在中序遍历下的下一个节点B，并将两者数据内容互换。接下来，将目标转换为，在右子树里查找并删除A。假设二叉排序树升序排序，则B必定为右子树之下最小的元素，而A在中序遍历中位于B之前，必然比B更小，故交换位置后，右子树的二叉排序树性质依然未变。

接下来继续查找删除，直到删除A的情况满足1~3中任意一个即可。

贴出伪代码：

def del(val,startPos):
    pos = find(val)
    // ..other conditions
    if pos->left != null and pos->right != null:
        nextPos = nextInorderPos(pos)
        swap(pos.data, nextpos.data)
        del(val,pos->right)

总结

相比之下，个人认为第二种方法更为精妙。第一种方法可能更好理解一些，但是在处理情况4时，会在无形之中增加树的高度，导致其分布不均匀，这样子会导致查找的性能降低。而后者则维护了树的整体结构，很好地避免了这一情况。