0

平均および最悪の場合の時間の複雑さを見つけるのは少し難しいです。したがって、次のロジックでこの BST ノードの削除を行いました

二分探索木でノードを削除する場合、3 つのケースがあります。

1> The node to delete has no children. That's easy: just release its resources and you're done. Time complexity O(1)

2> The node has a single child node. Release the node and replace it with its child, so the child holds the removed node's place in the tree. Time complexity O(1)

3> The node has two children. Find the right-most child of node's left subtree. Assign its value  to root, and delete this child. **Here time compexity can be maximum O(N)**

To find the node to be deleted can be **maximum O(N)**

では、全体の平均と最悪の時間の複雑さをどのように計算しますか??

4

2 に答える 2

0

平均的なケースの複雑さは、削除の場合は O(log(n) です。 O(log(n))=O(log(n)) 最悪の場合は明らかに O(n) 詳細についてはhttp://en.wikipedia.org/wiki/Binary_search_tree#Deletion

于 2014-04-17T13:49:25.943 に答える
0

この場合、状況を説明するには最悪の複雑さで十分だと思います。

最悪の場合の複雑さを見つけるには、あなたが言及した 3 つの可能性のあるシナリオ (O(n) ケース) から最悪のシナリオを見つけるだけです。したがって、最悪の場合の複雑さは O(n) です。

いくつかのまれなケース (Quicksort など) では、人々は平均的なケースの複雑さと最悪のケースの複雑さを記述することを選択します。クイックソートの場合、ほとんどすべてのケースでクイックソートが O(n*log(n)) になり、非常にまれなケースで O(n^2) になるだけだからです。したがって、人々は平均的なケースと最悪のケースの複雑さの両方を説明します。

ただし、二分探索木からノードを削除する場合、葉ノードの削除 (子なしで最良のケース) は、2 つの子を持つノードの削除よりもはるかに頻繁に発生することも、はるかに少なく発生することもありません。 （特別なケースのために開発している場合を除きます）。

したがって、二分探索木からノードを削除する複雑さは O(n) です。

于 2012-08-16T16:39:29.840 に答える