二进制搜索树中的删除 [英] deletion in a binary search tree

问题描述

我得到了两个二进制搜索树。例如，A和B。接下来，我被要求从树A中删除树B。

通过删除，我的意思是从A删除B中存在的所有节点。
注意：B不一定是A的子树。

例如：

A ：

  50 
 / \ 
 10 75 
 / / \ 
 1 60 90 
  

B：

  10 
 / \ 
 1 75 
  

结果树应为：

< blockquote>

  50 
 \ 
 60 
 \ 
 90 
  

我想到了两种方法：

A1：

node * deleteTree（node * A，node * B）;

取树B的根。删除此节点fr om树A（通过常规BSt删除方法）。接下来，将问题分为两部分-B的左子树和B的右子树。对于每个子树，递归。对于左侧的子树，占据已删除节点的节点应作为树A的根。对于右侧的子树，已删除节点的有序继承者应作为服务器的树A的根。

A2：另一种方法有些奇怪。我找到了树A的有序遍历和预排序遍历。使用二进制搜索和递归查找和删除树B中的所有节点（我们不修改前序）。最后，从顺序（剩余）和预定（未更改）重建我们的bst。

问题A：找到一种有效的BST方法。

问题B：找到任何二叉树（不仅仅是BST）的有效方法。

解决方案

问题A

我假设两棵树是平衡的。

  void deleteTree（node * A，node * B ）
 {
 if（A == NULL || B == NULL）
 return; 
 
 if（A-> data == B-> data）
 {
 deleteTree（A-> left，B-> left）; 
 deleteTree（A-> right，B-> right）; 
 removeNode（A）; //正常的BST删除
} 
否则if（A-> data> B-> data）
 {
 Node * right = B-> right; 
 B-> right = NULL; 
 deleteTree（A-> left，B）; 
 deleteTree（A，right）; 
} 
 else //（A-> data< B-> data）
 {
 Node * left = B-> left; 
 B-> left = NULL; 
 deleteTree（A-> right，B）; 
 deleteTree（A，左）; 
} 
} 
  

时间复杂度：

  T（N）= 2 * T（N / 2）+ O（1）
  

因此根据主定理，总体复杂度为 O（N）。空间复杂度为 O（1）。一个缺点是我破坏了B。

PS：我手头没有BST实施，因此无法为您测试代码。但是我认为这个想法是正确的。

问题B

对一棵树使用哈希表，然后遍历另一棵树。时间和空间复杂度都会得到 O（N）。

I have been given two binary search trees. For example, A and B. Next, I was asked to delete the tree B from the tree A.

By deletion, I mean delete all the nodes present in B from A. Note: B is not necessarily a subtree of A.

eg:
A:

      50   
     / \  
    10  75  
   /   / \  
  1   60   90                 

B:

     10
     / \
    1   75

Resulting tree should be:

     50
       \
        60
         \ 
          90

Two approaches came to my mind:
A1:
node* deleteTree(node* A, node* B) ;
Take the root of tree B. Delete this node from tree A(by normal BSt deletion method). Next divide the problem into two parts - for the left subtree of B and the right subtree of B. For each of the subtree, recurse. For the left subtree, the node which occupied the node which was deleted should serve as the root for tree A. For the right subtree, the inorder successor of the deleted node should server as the root for tree A.

A2: The other approach is a little weird. I find the inorder and preorder traversal of tree A. Find and delete all the nodes in tree B using binary search along with recursion(we dont modify the preorder). Finally recostruct our bst from the inorder(remaining) and the preorder(unchanged).

Prob A: Find an efficient way for BST.
Prob B: Find an efficient way for any Binary tree(not just BST).

解决方案

Problem A

I assume the two trees are balanced.

void deleteTree(node* A, node* B)
{
    if(A == NULL || B == NULL)
        return;

    if(A->data == B->data)
    {
        deleteTree(A->left, B->left);
        deleteTree(A->right, B->right);
        removeNode(A); // Normal BST remove
    }
    else if(A->data > B->data)
    {
        Node* right = B->right;
        B->right = NULL;
        deleteTree(A->left, B);
        deleteTree(A, right);
    }
    else // (A->data < B->data)
    {
        Node* left = B->left;
        B->left = NULL;
        deleteTree(A->right, B);
        deleteTree(A, left);
    }
}

Time complexity:

T(N) = 2 * T(N / 2) + O(1)

So the overall complexity is O(N) according to master theorem. The space complexity is O(1). One drawback is I destructed B.

PS: I don't have a BST implementation at hand so I can't test the code for you. But I think the idea is correct.

Problem B

Use hash table for one tree and traverse another. You will get O(N) for both time and space complexity.

这篇关于二进制搜索树中的删除的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！