set :: insertの複雑さ

私は、セット内での挿入操作はlog（n）時間しかかかりません。そんなことがあるものか？set :: insertの複雑さ

挿入するには、最初に、新しい要素が座っていなければならないソートされた配列内の位置を見つけました。バイナリ検索を使用すると、log（n）が使用されます。その位置に挿入するには、それに続くすべての要素を1桁右にシフトする必要があります。別のn時間かかる。

私の疑問は、セットが配列として実装され、要素がソートされた順序で格納されていることです。私の理解が間違っていれば私を修正してください。

2012-10-08 bibbsey

'std :: set'がソートされた配列として実装されていると仮定しています。どうして？ –

cppreferenceから取られた：*セットは通常、赤黒の木として実装されています。* – chris

@ KonradRudolph：赤い黒のツリーを使ってセットが実装されていることを知りました。ありがとうchris – bibbsey

std::setは、通常、赤黒の2分探索木として実装されます。このデータ構造上への挿入は、木がバランスをとって維持されるので、O（log（n））の複雑さの最悪の場合を有する。

2012-10-08 06:39:09 cdhowie

あまりありません：変更は、再度O（ログn）操作であるリバランスを伴います。 –

赤黒のツリーでは、リバランスを考慮しても挿入にはO（log（n））の最悪ケースが必要です。 – cdhowie

もちろん、私はそれに反対しませんでした。しかし、あなたは木を変更することはO（1）だと言った。 *それは間違いです。 –

答えて