首页 文章

在二叉搜索树中删除

提问于
浏览 次
6

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

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

例如：
A：

50
/
10 75
/ /
1 60 90

B：

10
/
1 75

结果树应该是：

50

60

90

我想到了两种方法：
A1：
node * deleteTree（node * A，node * B）;
取树B的根 . 从树A中删除此节点（通过正常的BSt删除方法） . 接下来将问题分为两部分 - B的左子树和B的右子树 . 对于每个子树，递归 . 对于左子树，占用已删除节点的节点应作为树A的根 . 对于右子树，已删除节点的inorder后继应作为树A的根服务器 .

A2：另一种方法有点奇怪 . 我找到树A的inorder和preorder遍历 . 使用二进制搜索和递归查找并删除树B中的所有节点（我们不修改预订） . 最后从inorder（剩余）和预订（不变）重新构建我们的bst .

问题A：找到一种有效的BST方式 .
问题B：找到任何二叉树（不仅仅是BST）的有效方法 .

algorithm binary-tree binary-search-tree

2 回答

  • 7

    我看到它的方式，你为什么不进行b的顺序遍历 . 然后，在数组不为空之前，从a中定期删除数组索引的值 . 遍历为O（n），每个索引的删除将为O（logn） . 总的来说，这个操作将是O（nlogn） .

    回复于
  • 0

    问题A.

    我假设这两棵树是 balancer 的 .

    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);
    }
}

    时间复杂度：

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

    因此根据主定理，总体复杂度是 O(N) . 空间复杂度为 O(1) . 一个缺点是我毁了B.

    PS：我手头没有BST实现，所以我无法为你测试代码 . 但我认为这个想法是正确的 .

    问题B

    对一棵树使用哈希表并遍历另一棵树 . 您将获得时间和空间复杂性的 O(N) .

    回复于

相关问题