c++ - 数据结构：关于二叉查找树(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，甚至非常複雜的紅黑樹、平衡樹。