2分探索木における挿入・探索アルゴリズムの解析
スポンサーリンク
概要
- 論文の詳細を見る
2分探索木で, 見出しの探索頻度という重みを付けて一般化したモデルにおける挿入・探索アルゴリズムの系統的な解析は見当たらない. すなわち, 任意の順序で登録される個々の見出しが, 2分木のどの位置に, どのような確率で配置され, 2分木がどのように構成されるかという挿入アルゴリズムの解析から, この2分木において個々の見出しの探索頻度を考慮した探索コストを評価する探索アルゴリズムの解析に至る系統的な解析は明らかでない. 本稿では, この問題に対する挿入・探索アルゴリズムの系統的な解析を提示する. はじめに, 挿入アルゴリズムの解析では, ある順序で登録される見出しが, ある指定された探索回数で挿入できる可能な場所の数を, 新しい順列を生成する方法をもとに解析的に求め, それを表す母関数を導き出している. そして, ある順序で登録される見出しが, 2分木のどの位置にどのような割合で配置されるかを表す確率を求めている. 次に, 探索アルゴリズムの解析では, この母関数を用いることによって, 個々の見出しの探索頻度を考慮した探索コストの評価式を見通しよく系統的に導出できることを示している.
- 一般社団法人情報処理学会の論文
- 1985-11-15
著者
関連論文
- 電子新聞に対する動的クラスタリング手法の提案
- 個人属性を考慮した情報フィルタリング
- ユーザの好みを考慮した新聞記事のランキング
- マルチエージェントによる新聞記事のランキング方式の提案
- 線形法における探索アルゴリズムの解析
- 分離連鎖法における挿入・探索アルゴリズムの解析
- キャッシュコヒーレンスプロトコルにおけるオーナーシップに関する考察
- キャッシュコヒーレンスプロトコルに対する一考察
- PERTチャートにおけるクリティカルパスを求める並列アルゴリズム(アルゴリズム理論)
- 3U-4 統計的手法によるネットワーク利用可能帯域の推定と予測
- 入れ子構造を許す言語処理で用いる名前表の一構成法とその解析
- 任意に回転したパターンと回転角度を認識する複写学習モデル
- 位置ずれ・回転パターンを認識するニューラルネットワーク
- JavaによるLANシミュレータの実現
- JavaによるLANシミュレータの実現
- SNMPによるネットワーク不正アクセス検出エージェントの実現
- オブジェクト指向によるLAN構築支援システムの設計
- Microprogrammed E-MIXによるアセンブリ言語教育支援システムの設計と開発
- 結合グラフ証明手続きにおける効率的な探索戦略
- 2分探索木における探索アルゴリズムの解析
- 線形ハッシュ法における探索アルゴリズムの解析
- 並列トポロジカル整列アルゴリズム(計算科学と数値シミュレーションの理論と実践)
- DAGの最長路を求める並列アルゴリズム
- 有向グラフの強連結成分を求める並列アルゴリズム
- 並列トポロジカル整列アルゴリズム
- 2分探索木を平衡化する並列アルゴリズム
- マルチプロセッサシステムにおける並列タスクスケジューリングについての一考察
- 2分探索木を通りがけ順になぞる並列アルゴリズム
- 有向グラフの最長路を求める効率良い並列アルゴリズム
- 疎な有向グラフの強連結成分を求める効率良い並列アルゴリズム
- 回転パターンを自動生成するニューラルネットワーク
- 2分探索木における挿入・探索アルゴリズムの解析
- 入れ子構造を許す言語処理で用いる名前表の一構成法とその解析