なぜこのバイナリツリーの検索に挿入よりも時間がかかりますか？

Question

私はいくつかの基本的なアルゴリズムを学び/理解しようとしていますが、今日はGoにバイナリツリーを書くことにしました。これは、構造体は次のようになります。

type Node struct { 
    Value int 
    Left *Node 
    Right *Node 
} 

ここで木がintが含まれているかどうかを確認するために私の機能です：

func (tree *Node) Contains(val int) bool { 
    if val == tree.Value { 
    return true 
    } else if val > tree.Value { 
    if tree.Right != nil { 
     return tree.Right.Contains(val) 
    } else { 
     return false 
    } 
    } else if val < tree.Value { 
    if tree.Left != nil { 
     return tree.Left.Contains(val) 
    } else { 
     return false 
    } 
    } else { // huh 
    return false 
    } 
} 

私は木のテイクにどのくらい異なる操作をテストするためのテスト機能を書きました。 Insert()関数34msに100,000個のランダムな整数を挿入するには、Contains()関数33msを使用して、ツリーに100,000の乱数が含まれているかどうかを確認します。ランダムな整数の数を1,000,000まで上げると、Insert()関数34msが実行されますが、私のContains()関数は突然321msを実行します。

なぜContains()の実行時間が大幅に増加するのですが、Insert()は実質的に同じですか？

Answer 1

Insert関数は、不均衡なツリーが非常に不均一なトラバーサル時間につながる可能性があるため、ツリーを定期的に再バランスする必要があります。その結果、Insertはとなるのが一般的に遅くなりますContainsです。

Insert関数がツリーを再調整しない場合、与えられた関数に必要な時間はO（log n）ではなくO（n）最悪のケースになり、かなり予測できません。

さらに、O（...）時間の複雑さについて話すとき、我々は一般的に最悪のケースの動作について話しています。たとえば、Containsがルートになったノードを探している場合は、サイズに関係なく直ちに復帰します。