完全2分木
別名:完全二分木
【英】complete binary tree
完全2分木とは、2分木の木構造のうち、頂点(根)から最底辺(葉)に至る全てのノードが2つの子ノードを持ち、また、すべての葉が根から等しい距離にある構造のことである。
完全2分木は、左右のノードの数が等しい、木構造の深さをnとすればノードの数は2nとなる、あるいは、完全2分木を2分探索木として探索(検索)する場合、深さの数だけ探索可能であることがあらかじめ保証されている、といった特徴がある。
完全2分木においては、全ての葉は根から同じ深さ(レベル)にある。ただし例外的に、深さが1だけ異なる葉が存在し、その1だけ深い葉が木全体の左側に詰めてあるタイプの2分木も、完全2分木とみなされる。
- 完全2分木のページへのリンク