数据结构：关于二叉查找树(BinarySearchTree)的删除算法的疑问？

Question

Mark Allen Weiss的《数据结构与算法分析》第4章中讲到二叉查找树这种数据结构，关于删除的代码是这样的：

// 删除以t为根的BST中值为x的节点
void remove(int x, BinaryNode*& t)
{
    if ( t == NULL)
    {
        return ;
    }
    if (x < t->data)
    {
        remove(x, t->left);
    }
    else if (x > t->data)
    {
        remove(x, t->right);
    }
    // 左右都有节点的情况
    else if (t->left != NULL && t->right != NULL)
    {
        t->data = findMin(t->right)->data; // 右子树最小的节点
        remove(t->data, t->right);
    }
    else
    {
        BinaryNode* oldNode = t;
        t = (t->left != NULL) ? t->left : t->right);
        delete oldNode;
    }
}

二叉树的基本性质是节点大于其左子树的所有节点，小于其右子树的所有节点，
在这个删除算法中，当删除的节点有2个儿子的情况的时候，为什么是从右子树找出最小的节点而不是从左子树找出最大的节点呢？

Answer 1

都可以，二叉搜索树删除拥有左右子树节点的时候，既可以用左子树的最右节点来替代，也可以用右子树的最左节点来替代。书中的例子应该是刚好用到了其中的一种情况。

Answer 2

其实当总是从寻找右子树的最左节点或者左子树的最右节点替代的时候，会引起二叉搜索树的退化，当退化成链表，二叉搜索树的查找优势就不存在了。可以尝试随机从左右子树的节点替代，也可以考虑更复杂但效果更好的treap，乃至非常复杂的红黑树、平衡树。