私は現在取り組んでいるプロジェクトのためにシンボル テーブルを構築しています。シンボル テーブルを保存および作成するために利用できるさまざまな方法の利点と欠点について、皆さんの意見をお聞きしたいです。
かなり調べてみましたが、最も一般的に推奨されているのはバイナリ ツリー、リンク リスト、ハッシュ テーブルです。上記のすべてにはどのような利点と欠点がありますか? (C++ で作業中)
ベストアンサー1
これらのデータ構造間の標準的なトレードオフが適用されます。
- バイナリツリー
- 実装の複雑さは中程度（ライブラリから取得できない場合）
- 挿入はO(logN)
- 検索はO(logN)
- リンクリスト（未ソート）
- 実装の複雑さが低い
- 挿入はO(1)
- 検索はO(N)
- ハッシュテーブル
- 実装が非常に複雑
- 挿入は平均してO(1)である
- 平均して検索はO(1)