使用不同的方法删除具有2个节点的二叉搜索树中的节点？

我已经找遍了这一点，但只有一个方法：使用不同的方法删除具有2个节点的二叉搜索树中的节点？

找到节点的前任（或继承人）删除

取代前任（或继承人）节点

删除前身（或继承人）

，但我觉得我们也可以做到这样：

将要删除的节点的右（或左）元素拉下来，即只是用右（或左）元素替换要删除的元素，并继续这样做直到我们遇到叶，然后删除叶。简而言之，继续使用它的右（或左）元素替换要删除的元素，并继续这样做直到我们到达叶，然后删除叶。

那么这种方法是正确的吗？

来源

2017-03-31 coderAJ

如果我正确理解您的方法，听起来不像是可行的。你为什么不用一棵简单的树画出我们的照片（三个级别应该这样做），并向我们展示步骤？ –

不幸的是，CoderAj，Vikhram提供的解决方案是删除BST中节点的正确方法。你的方法听起来不错，但在第一次取代本身时失败。

让我们在树上研究你的方法。

      8 
        5    25 
      3   7  23  30 
        6   24 27 35

让我们删除根即8
第1步：

     25    //replaced 8 by 25 
       5    25 
     3   7  23  30 
       6   24 27 35

23和24是小于25，但他们还是在于它的右子树。

因此，你最终的树看起来像这样

     25 
       5    30 
     3   7  23  35 
       6   24 27

它看起来并不像一个二叉搜索树。

来源

2017-03-31 19:45:48 daBigBug

我不真正按照你的算法（他们俩）。但下面是如何从二叉树中删除一个节点（非平衡）。

找到要删除的节点。此节点只能由现有树中的2个节点中的一个节点替换。
1.右侧子节点的最左侧（即最小）元素或
2.左侧子节点的最右侧（即最大）元素。

替换它取可用的和你做

没有其他节点需要从
1. RightMostChildOfLeftChild（）< CurrentNode（）< LeftMostChildOfRightChild（）RightMostChildOfLeftChild之间存在
2.无节点移动（）和LeftMostChildOfRightChild（）除了CurrentNode（）

现在，如果您不介意移动一堆节点，那么还有很多其他方法可以删除节点。

希望能够为您澄清它。

来源

2017-03-31 17:38:51 Vikhram

这是我们到处得到的一般解决方案，但我觉得我们也可以这样做：继续用正确的元素替换要删除的元素，并继续这样做直到我们到达叶，然后删除叶。 – coderAJ

对于您的主题问题，答案是肯定的;另一种方法是可能的。

我在Sedgewick的书中发现了一种方法，在我看来，这种方法更简单一般。

首先，考虑两个BST的专有连接ts和tg'. Exclusive means that all the keys in ts are smaller than any key in tg`。因此，考虑以下情况：

现在，如果你选择ts或tg之间的任何根的独家根加入，你可以递归定义最终结果如下：

在这种情况下，连接的根是ts的根。

请注意，当您删除BST中的完整节点时，其子节点是前面定义的两个专用树。

Node * remove_from_bst(Node *& root, int key) noexcept 
{ 
    if (root == nullptr) 
    return nullptr; // In this case key was not found 

    // recursive searching of the key to be removed 
    if (key < root->key) 
    return remove_from_bst(root->left, key); 
    else if (root->key < key) 
    return remove_from_bst(root->right, key); 

    // here root contains a node with key 
    Node * ret_val = root; // backup of root that we will remove from tree 
    root = join_exclusive(root->left, root->right); // new subtree 

    return ret_val; // we return the removed node 
}

现在，整理，我们定义了join_exclusive()操作：所以，你可以如下定义删除

Node * join_exclusive(Node *& ts, Node *& tg) noexcept 
{ 
    if (ts == nullptr) 
    return tg; 

    if (tg == nullptr) 
    return ts; 

    tg->left = join_exclusive(ts->right, tg->left); 

    ts->right = tg; 
    Node * ret_val = ts; 
    ts = tg = nullptr; // empty the trees 

    return ret_val; 
}

这种方法对我来说更容易，因为它管理的三种情况：叶子，不完整的节点和完整的节点。另外，密钥永远不会在节点之间移动。

由于独占连接的根是任意选择的，所以这种方法以及您的方法引入了一种倾向于使随机树不平衡的偏差（根选择不是随机完成的）。然而，正如Roura为他们的随机树所建议的那样，您可以将每个子树的基数存储在节点中。然后，你可以执行一个抽象的过程来提高每个子树的基数。通过这种方法，您可以保证该树总是等于随机构建的BST

来源

2017-04-01 14:21:07 lrleon

使用不同的方法删除具有2个节点的二叉搜索树中的节点？

回答

相关问题