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

Either way, when a binary search tree deletes a node with left and right subtrees, it can be replaced with the rightmost node of the left subtree or the leftmost node of the right subtree. The examples in the book should happen to be used in one of these situations.

Answer 2

In fact, when always searching for the leftmost node of the right subtree or the rightmost node of the left subtree, it will cause the degradation of the binary search tree. When it degenerates into a linked list, the search advantage of the binary search tree is No longer exists. You can try to randomly replace the nodes of the left and right subtrees, or you can consider the more complex but better treap, or even the very complex red-black tree, balanced tree.