どのバランスの取れた BST が C++ で簡単にコーディングできるかを知りたいのですが、それでも O(logn) とほぼ同じ複雑さがあります。
私はすでに Red Black ツリーを試しましたが、コーディングがより簡単な代替手段が必要です。私は過去にTreapsと仕事をしたことがありますが、パフォーマンスが向上するか、実装がより簡単なオプションを模索することに興味があります.
あなたの提案は何ですか？
1254 次
1 に答える
3
私の経験では、一般的にAVL ツリーは Treap よりも優れたパフォーマンスを発揮し、実装も難しくありません。
それらは、挿入または削除後に不均衡になるツリーのブランチを回転させることによって機能します。これにより、完全なバランスが保証されるため、奇妙なデータに「だまされる」ことはありません。
一方、Treap はランダムに分散され、大規模なデータ セットではほぼバランスが取れていますが、それでも完全な O(logn) は得られません。さらに、非常に不均衡な方法で挿入されるデータセットに遭遇する可能性があり、アクセス時間が O(n) に近づく可能性があります。
詳細については、ウィキペディアのページをご覧ください: en.wikipedia.org/wiki/Avl_tree
于 2014-07-29T16:08:53.193 に答える