バイナリツリー検索ノードの複雑さを削除

Question

私はバイナリツリー検索ノードの削除の複雑さを計算しようとしています。私は3つすべてのケース（最悪、平均複雑さと最高）より複雑に計算したい。数式を選択する方法？ 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））時間もかかります。それが最善のケースです。

すべてのノードが右/左の子を次のノードとして使用すると、最悪の場合があります。このケースは、ソートされた項目（たとえば1,2,3,4,5など）をツリーに挿入すると表示されることがあります。したがって、このツリーの高さはNで、削除操作はO（N）時間かかるでしょう。この場合、バイナリ検索ツリーはリンクされたリストではありません。

だから、平均的複雑さは、これはあなたのノードでバランスが取れているかどうかに依存