バランスの取れた検索ツリーの場合、すべてのケースで O(log(N)) です。不均衡な検索ツリーの場合、最悪のケースは O(N) です。たとえば、挿入 1、2、3、4、.. であり、最良のケースの複雑さは、バランスが取れている場合です。たとえば、挿入 6、4、8、3、5 7 です。 . 不均衡な検索ツリーの平均的なケースの複雑さをどのように定義しますか?
1419 次
1 に答える
4
二分木の平均の高さはシータ（sqrt（n））です。これは、次の論文で示されています（または参照されていますが、よくわかりません）：http ://www.dtc.umn.edu/~odlyzko/doc/arch/extreme.heights.pdf 。
しかし、おそらくあなたはランダムノードの平均的な深さにもっと興味があり、これはここで見ることができるようにシータ（log n）です：http：//www.toves.org/books/data/ch05-trees/index.html（セクション5.2.4）。
于 2010-02-25T05:24:49.403 に答える