二項木
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/11/05 08:19 UTC 版)
二項ヒープは二項木の集合として実装される（二分ヒープと比較すると、二分ヒープは単一の二分木から構成される）。二項木は再帰的に定義される。 次数 0の二項木は1つのノードをもつ。 次数 k の二項木は一つの根(root)をもち、その子はそれぞれ次数 k-1, k-2, …, 2, 1, 0の二項木の親である。 次数 k の二項木は 2 k {\displaystyle 2^{k}} のノードを持ち、高さはk である。 その構造の特有さから、マージ操作は簡単に行うことができる。例えば、次数 k の二項木を作るには、次のようにする。 次数 k-1の2つの木 T a {\displaystyle T_{a}} と T b {\displaystyle T_{b}} があるとする。 T a {\displaystyle T_{a}} （または T b {\displaystyle T_{b}} ） の一番左の子として、 T b {\displaystyle T_{b}} （または T a {\displaystyle T_{a}} ）を付け加える。 この特徴は二項ヒープのマージ操作の中核を成すものであり、従来のヒープに優る大きな利点となっている。
※この「二項木」の解説は、「二項ヒープ」の解説の一部です。
「二項木」を含む「二項ヒープ」の記事については、「二項ヒープ」の概要を参照ください。
ウィキペディア小見出し辞書の「二項木」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- 二項木のページへのリンク
