WEKO3
アイテム
2分探索木における挿入・探索アルゴリズムの解析
https://ipsj.ixsq.nii.ac.jp/records/15738
https://ipsj.ixsq.nii.ac.jp/records/15738da890b93-8931-49b4-8d4d-e01edfa7f28e
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-JNL2606016.pdf (497.4 kB)
|
Copyright (c) 1985 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | Journal(1) | |||||||
|---|---|---|---|---|---|---|---|---|
| 公開日 | 1985-11-15 | |||||||
| タイトル | ||||||||
| タイトル | 2分探索木における挿入・探索アルゴリズムの解析 | |||||||
| タイトル | ||||||||
| 言語 | en | |||||||
| タイトル | An Analysis of Insertion and Search Algorithms of a Binary Search Tree | |||||||
| 言語 | ||||||||
| 言語 | jpn | |||||||
| キーワード | ||||||||
| 主題Scheme | Other | |||||||
| 主題 | 論文 | |||||||
| 資源タイプ | ||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||||
| 資源タイプ | journal article | |||||||
| 著者所属 | ||||||||
| 熊本大学工学部 | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Faculty of Engineering, Kumamoto University | ||||||||
| 著者名 |
中村, 良三
× 中村, 良三
|
|||||||
| 著者名(英) |
Ryozo, Nakamura
× Ryozo, Nakamura
|
|||||||
| 論文抄録 | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | 2分探索木で 見出しの探系頻皮という重みを付けて一般化したモデルにおける挿入・探索アルゴリズムの系統的な解析は見当たらない.すなわち 任意の順序で登録される個々の見出しが 2分木のどの位置に どのような確率で配置され 2分木がどのように構成されるかという挿入アルゴリズムの解析から この2分木において個々の見出しの探索頻度を考慮した探索コストを評価する探索アルゴリズムの解析に至る系統的な解析は明らかでない.本稿では この問題に対する挿入・探索アルゴリズムの系統的な解析を提示する.はじめに 挿入アルゴリズムの解析では ある順序で登録される見出しが ある指定された探索回数で挿入できる可能な場所の数を 新しい順列を生成する方法をもとに解析的に求め それを表す母関数を導き出している.そして ある順序で登録される見出しが 2分木のどの位置にどのような割合で配置されるかを表す確率を求めている.次に 探索アルゴリズムの解析では この母関数を用いることによって 個々の見出しの探索頻度を考慮した探索コストの評価式を見通しよく系統的に導出できることを示している. | |||||||
| 書誌レコードID | ||||||||
| 収録物識別子タイプ | NCID | |||||||
| 収録物識別子 | AN00116647 | |||||||
| 書誌情報 |
情報処理学会論文誌 巻 26, 号 6, p. 1106-1112, 発行日 1985-11-15 |
|||||||
| ISSN | ||||||||
| 収録物識別子タイプ | ISSN | |||||||
| 収録物識別子 | 1882-7764 | |||||||
