翻訳と辞書
Words near each other
・ 平行調
・ 平行進化
・ 平行遊び
・ 平衛之
・ 平衝胞
・ 平衡
・ 平衡 (曖昧さ回避)
・ 平衡(感)覚
・ 平衡(状態)
・ 平衡-不平衡変換器
平衡2分探索木
・ 平衡不完全ブロック
・ 平衡不完全ブロック配列法
・ 平衡二分探索木
・ 平衡仮説
・ 平衡伝送
・ 平衡伝送路
・ 平衡側
・ 平衡側干渉
・ 平衡側接触


Dictionary Lists
翻訳と辞書 辞書検索 [ 開発暫定版 ]
スポンサード リンク

平衡2分探索木 : ミニ英和和英辞書
平衡2分探索木[へいこうにぶんたんさくぎ]
=====================================
〔語彙分解〕的な部分一致の検索結果は以下の通りです。

: [たいら, ひら]
 【名詞】 1. the broad 2. the flat 3. palm
平衡 : [へいこう]
  1. (n,vs) even scale 2. equilibrium 3. balance 4. equalization 5. equalisation 
: [ぶん, ふん]
  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 

平衡2分探索木 ( リダイレクト:平衡二分探索木 ) : ウィキペディア日本語版
平衡二分探索木[き]
平衡二分探索木(へいこうにぶんたんさくぎ、)とは、計算機科学において二分探索木のうち木の高さ(根からの階層の数)を自動的にできるだけ小さく維持しようとするもの(平衡木)である。平衡二分探索木は連想配列集合その他の抽象データ型を実装する最も効率のよいデータ構造の1つである。
==概要==

二分探索木上の大半の操作にかかるコストは木の高さに比例するので木の高さは低く保つのが望ましい。通常の二分探索木の主要な欠点は、キーが辞書順に挿入されるような普通の状況で木の高さが大きくなってしまうということである。結果として連結リスト同様のデータ構造になってしまい、全ての操作が高くつく結果となる。もしあらかじめ全てのデータが分かっているならば、値をランダムに追加することで木の高さを平均的に小さく保つことができるが、そのような贅沢はいつもできるわけではない。特に入力が一括して与えられることのないオンラインアルゴリズム(online algorithm)の場合はそうである。
平衡二分探索木は木に対する変換(例えば木の回転)を木の高さを減らすために必要に応じて行うことでこの問題を解決する。いくらかのオーバーヘッドは要するものの、それは後述の操作のオーバーヘッドを長い目で見て劇的に減らすことで正当化される。
木の高さは常に最低でも\lfloor\log n\rfloor以上である。k段目にはせいぜい2''k''ノードしか存在しないからである。完全な2分木は丁度この高さになる。平衡二分探索木を常に最小の高さに保つのは高くつくので、いつも正確に平衡している必要はない。その代わり、高さをこの下界の定数倍以内に維持する。
''n''をノードの数とした場合の計算量は以下のとおり。
ある実装では上記の時間は最悪時のものであり、違う実装では償却解析(Amortized analysis)した時間である。

抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)
ウィキペディアで「平衡二分探索木」の詳細全文を読む




スポンサード リンク
翻訳と辞書 : 翻訳のためのインターネットリソース

Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.