完全二分木の定義について

Question

言語はJavaにしていますが、Javaに限った話ではないと思います。
完全二分木の定義についてです。
まず、私の使っている本には
「完全二分木は全ての葉が木の最下層にあり、派手ないノードは全て2つの子ノードを持っています。この条件を満たすには、ちょうど(2^n – 1)個のノードを持っていなければならない。」

http://www.ohshiro.tuis.ac.jp/~ohshiro/sougou/09/tree.html

また、こちらのサイトを参考にしますと、
「木の高さがkのとき，全ての葉の深さがk個またはk-1個となっている2分木」のことを完全二分木と定義しています。

この時点で食い違っていたので、さらに調べましたところ、
http://www.sophia-it.com/content/完全二分木
という記事を見つけました。
「完全2分木とは、2分木の木構造のうち、頂点（根）から最底辺（葉）に至る全てのノードが2つの子ノードを持ち、また、すべての葉が根から等しい距離にある構造のことである。

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

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

要は本で言っているのは、狭い意味での完全二分木であり、
http://www.ohshiro.tuis.ac.jp/~ohshiro/sougou/09/tree.html
こちらで言っているのは広い意味での完全二分木なのかと考えました。

広い意味での完全二分木の定義「木の高さがkのとき，全ての葉の深さがk個またはk-1個となっている2分木」を用いますと、木の高さが3の木で右側の葉（二つある）の高さが2となっている木のことも完全二分木と呼ぶわけですが、右側の葉が一つだけの場合も完全二分木と呼ぶのでしょうか？
すなわち、ノードの総数は10個で左側の部分木は完全二分木で、右側の部分木のノードは二つであるような木です。
伝わりませんでしたら、お知らせください。
回答お願いします。

Answer 1

日本語で完全二分木と呼ばれるものは二種類あるのは質問の通りですが、これは英語ではfull binary treeとcomplete binary treeとして区別されます。

このとき、full binary treeが質問にある狭義の完全二分木で、complete binary treeが広義の完全二分木と考えていただいて差し支えありません。

しかし、質問にある木はcomplete binary treeではないと思います。というのも、complete binary treeの定義は、

A binary tree in which every level (depth), except possibly the deepest, is completely filled. At depth n, the height of the tree, all nodes must be as far left as possible.

https://xlinux.nist.gov/dads/HTML/completeBinaryTree.htmlより

というものです。つまり、最後のレベルを除いたときにfull binary treeとなり、かつ葉が可能な限り左によっている、というのがその条件です。

下の図は質問にある木を図にしてみたものです（分かりにくくてごめんなさい）。このotherで囲われている部分が完全二分木でなければcomplete binary treeと呼べないのだと思います。

Comments

[退会済みユーザー]

回答ありがとうございます。
なんだか定義もpossiblyやpossibleなどあいまいさを含んでいるのですね。

[MakeNowJust]

full binary tree ⊆ complete binary treeであるためにpossiblyという単語が使われているだけで、別に曖昧ということは無いと思いますよ

Answer 2

数学的なデータ構造としての二分木を想定するのか、二分木探索(binary tree search)につかう二分木を想定するかで、変わってくると思います。

＜数学的＞
(a)「全ての葉が木の最下層にあり、葉でないノードは全て2つの子ノードを持っている二分木」というのは、数学的(Graph theory的)な"完全二分木"の定義でしょう。
しかし、このような二分木は葉の数が２のn乗の場合にしか作れないので、検索プログラムでつかうデータ構造としては不適切です（対象が８個や３２個なら検索できるけど、１０個だとエラーを起こすプログラムなんて、使い物になりませんからね）

(b)「葉でないノードは全て2つの子ノードを持っている二分木」(一方の子が無いノードは存在しない）は、純粋(pure)二分木と呼ばれたりします。ノードの２つの子を入れ替えるという操作が、どのノードに対しても行う事ができるという性質があります。

＜プログラム用＞
プログラムで二分木が使われるのは、二分木探索/二分木ソートをするためです。
プログラムの実行効率が良く、処理時間の見積もりが容易である事から、平衡二分木(balanced binary tree)が使われます。平衡の意味は「つり合っている」で、根から葉までの長さがつり合っている（違っていても、高々１しか違わない）純粋二分木の事です。
平衡二分木のうち葉が左型に寄せられているものが、完全二分木と呼ばれます。

子が片方しか無いノードが存在する場合、そのノードを子で置き換える事で純粋な二分木に出来ます。特別な事情がない限り子が片方しかないノードを含む二分木を使う事はありません。(もちろん、二分木に葉を追加している途中とかでは一時的に存在します)