4

二分探索木の複雑さを知りたいです。

完全な情報が見つかりません。二分探索木の次の操作の複雑さを知りたい

  1. 要素を追加/挿入する
  2. 要素を削除するには
  3. 要素を見つける (私が知っているように、これは ですO(log(n)))
4

3 に答える 3

10

二分探索木での挿入、削除、検索は次のとおりです。

  • O(N)最悪の場合;
  • O(log(N))平均的な場合。
于 2013-03-23T12:39:54.297 に答える
7

二分木のバランスがとれている場合、3 つの複雑性はすべてO(log(N)). ツリーのバランスを取っていない場合は、O(N).

于 2013-03-23T13:00:06.253 に答える
0

検索が効果的です。ただし、不均衡な構造（多くの場合）は、検索/挿入/削除操作のO（N）につながる可能性があります。そのため、O（log n）ではバイナリヒープまたは他の種類のバランスの取れたツリーが優先されます。。

于 2013-03-23T13:18:40.510 に答える