ツリー内に連続した要素を挿入するのは、ランダムな要素をツリーに挿入するより時間がかかります。

Question

これは宿題ではありません私はデータ構造体クラスを取っており、最近は木々を完成させました。授業の最後に、私の教授がこのイメージを示しました。

コンクリートブロックツリーは、セルフバランスのない2分木です。私はこれらの手順を完了するのにかかった時間についていくつか質問があります。

1. なぜそれがそこにランダムな要素を挿入するのにかかるよりも、ConcreteBTreeに10万シーケンシャル要素を挿入するためにそんなに多くの時間がかかるのでしょうか？私の直感は、要素が連続しているので、1,000,000個のランダム要素を挿入するのに要する時間よりも短い時間がかかるはずです。

2. ランダム要素を持つConcreteBTreeのinsert（）とfind（）の時間が近すぎるのはなぜですか？どちらも同じ時間の複雑さを持っているからですか？私は挿入がO（1）であったと私は本当にここで何が起こっているかを理解したいと思いますO（n）の

だっ見つけると思った、任意の説明をいただければ幸いです。ありがとう

Answer 1

バイナリツリーに順次項目（1,2,3,4 ...）を挿入すると、ノードは常に同じ側（たとえば左側）に追加されます。 ランダムな項目を挿入すると、ノードをランダムに左右に追加します。

新しいアイテムが以前に追加されたアイテムをすべて訪問する必要があり、ランダムに追加するときにO（n）ステップかかるため、リストを通常のリンクリスト（順次アイテム）として動作させるO（log N）ステップを平均する。

Answer 2

アルミンの回答Q1。

2.ランダムな要素を持つConcreteBTreeのinsert（）とfind（）の時間が近似していますか？どちらも同じ時間の複雑さを持っているからですか？私は、（1）の挿入はOだと思ったし、見つけるO（n）の

insertとfindが同じ仕事をしなければならないた - 彼らはあなたが下の最後のノードを探して一緒に入れている奇妙なものは何でもツリーを下りますその値はリンクされているか、そうであるか（そしてinsertの場合になります）、同様の時間を取って、同じ数の比較とノード・トラバーサルを行います。

平衡ツリー内のランダム要素の挿入はO（ログ N）です。セルフ・リバランスをしないツリーにランダムな値を挿入すると、いくらかの分岐が他の分岐よりかなり長くなるため、劇的に悪化することはありません。おそらくブランチ長のベル・カーブが得られます。 insertの唯一のO（1）は、挿入が行われるツリー内のノードを既に知っている場合（つまり、上記のステップが通常必要である場合）です。 findのツリー内のすべてのノードを訪問する必要がある場合はO（n）のみです。これは病理学的に不均衡なツリーの場合のみであり、リンクリストを効果的に形成します。ソートされた要素。