二叉树搜索删除一个节点的复杂度

Question

我尝试计算二叉树搜索节点的复杂度 deletion.I 想计算所有 3 种情况下的复杂度（最差、平均复杂度和最佳）更多 detalied.How 选择数学公式？ T(n) = ?

    Nod* delete(Nod*& rad, const int& c)
{
    //Nod has:c(information:int),nextSt(left:pointer to Nod),nextDr(right pointer to Nod)
    Nod* aux;
    if (rad == NULL)
        return NULL;
    else
        if (c< rad->c && c != rad->c) {
            rad->nextSt() = delete(rad->nextSt(), c);
            return rad;
        }
        else
            if (c > rad->c) {
                rad->nextDr() = delete(rad->nextDr(), c);
                return rad;
            }
            else
                if (rad->nextSt() != NULL && rad->nextDr() != NULL) {
                    aux = minim(rad->nextDr());
                    rad->setElem(aux->element());
                    rad->nextDr() = delete(rad->nextDr(), rad->c);
                    return rad;
                }
                else {
                    aux = rad;
                    Nod* repl;
                    if (rad->nextSt() == NULL)
                        repl = rad->nextDr();
                    else
                        repl = rad->nextSt();
                    delete rad;
                    return repl;
                }

}

Answer 1

二叉搜索树上的移除操作总是需要O(h)的时间。其中 h 是树高。

所以如果你的树平衡良好，它的高度是 log(N)。删除操作也将花费 O(log(N)) 时间。这是最好的情况。

最坏的情况出现在所有节点都使用 right/left 个子节点作为下一个节点时。如果您将已排序的项目（例如 1、2、3、4、5）插入到树中，则可能会出现这种情况。所以这棵树的高度是 N 并且删除操作将花费 O(N) 时间。在这种情况下，二叉搜索树不是更好的链表。

所以平均复杂度在 log(N) 和 N

之间

有关二叉搜索树和复杂性理论的更多信息，请参阅 Cormen 的算法简介

二叉树搜索删除一个节点的复杂度

Binary tree search delete a node complexity

c++

complexity-theory

time-complexity