|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ 二 ： [に] 1. (num) two ・ 分 ： [ぶん, ふん] 1. (n,n-suf,pref) (1) part 2. segment 3. share 4. ration 5. (2) rate 6. (3) degree 7. one's lot 8. one's status 9. relation 10. duty 1 1. kind 12. lot 13. (4) in proportion to 14. just as much as 1 ・ 探索 ： [たんさく] 1. (n,vs) search 2. hunt 3. (item of) research 4. exploration 5. investigation ・ 探索木 ： [たんさくぎ] (n) search tree ・ 索 ： [さく] 【名詞】 1. rope 2. cord ・ 木 ： [き] 【名詞】 1. tree 2. wood 3. timber
二分探索木（にぶんたんさくぎ、）は、コンピュータプログラムにおいて、「左の子孫の値 ≤ 親の値 ≤ 右の子孫の値」という制約を持つ二分木である。探索木のうちで最も基本的な木構造である。 == 構造 == 構造は二分木と同じだが、「左の子孫の値 ≤ 親 ≤ 右の子孫の値」という制約を持つ。左の子孫の値と右の子孫の値の両方に等号をつけているが、実際にはどちらかに統一しておく必要がある。 平衡（左右のバランスがとれている状態）している状態では木の高さは O(log2 N) となる。ただし最悪の場合は、事実上の 線形リスト になり、木の高さは O(N) となる。木の形は挿入時のデータ出現順序に依存し、特にソート済みのデータを与えると線形リストになる点は注意を要する。データの出現順序によって大きく性能が劣化しないように、挿入・削除の際に木の平衡を取り直す処理を追加した二分探索木は平衡二分探索木と呼ばれる。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「二分探索木」の詳細全文を読む スポンサード リンク
|