完全2分木とは

完全2分木

完全2分木とは、2分木の木構造のうち、頂点（根）から最底辺（葉）に至る全てのノードが2つの子ノードを持ち、また、すべての葉が根から等しい距離にある構造のことである。

完全2分木は、左右のノードの数が等しい、木構造の深さをnとすればノードの数は2ⁿとなる、あるいは、完全2分木を2分探索木として探索（検索）する場合、深さの数だけ探索可能であることがあらかじめ保証されている、といった特徴がある。

完全2分木においては、全ての葉は根から同じ深さ（レベル）にある。ただし例外的に、深さが1だけ異なる葉が存在し、その1だけ深い葉が木全体の左側に詰めてあるタイプの2分木も、完全2分木とみなされる。

完全二分木と同じカテゴリーの他の用語

• 2分探索木
• 2分木
• FIFO
• LFU
• LIFO
• LRU
• Nクイーン問題
• アルゴリズム
• エイトクイーン問題
• キュー
• シェルソート
• スタック
• セレクションソート
• ソート
• ツリー構造
• バイナリサーチ
• バックトラック法
• ハッシュ法
• モンテカルロ法
• 関数
• 基本交換法
• 後方一致
• 降順
• 巡回セールスマン問題
• 昇順

• 選択ソート
• 前方一致
• 挿入ソート
• 木構造
• 有限要素法
• 離散化
• 有限要素法
• B木
• Levy曲線
• アセンディングソート
• サブセット
• モード
• 識別子
• 論理エラー
• 2分探索法
• 連結リスト
• 完全2分木
• AVL木
• ケーニヒスベルグの橋
• ド・モルガンの法則
• ラウンドロビンアルゴリズム
• 計算複雑度
• 後入れ先出し
• 整列
• 探索法

完全二分木について言及している用語

• 完全2分木

• ツリー構造