binary decision treeの証明

質問

上記にも記載してますが、n個のinternal nodes（内部節）がある場合、最大でn+1個のexternal nodes(外部節）が存在します。

この証明をinduction（帰納法）を使って表したいのですが、どうすればいいのでしょうか？
バイナリーですので、2^nでlogを使えばいいのかと考えてますが、数学的根拠が難しく、悩んでいます。

お手数ですが、よろしくお願いします。

回答No.1

kumoringo · ベストアンサー

左の子の内部節数をm、右の子の内部節数をnとして新しい木を作ると、
左の外部節数≦m+1
右の外部節数≦n+1
だから、
(新しい木の外部節数)≦m+n+2=(m+n+1)+1=(新しい木の内部節数)+1

回答No.3

arrysthmia

普通に考えると、外部節の最大数は、n+2。
n=1 の場合を図示して御覧。

回答No.2

Tacosan

decision は全然関係なくて binary tree の話ですね. どのように binary (decision) tree を定義しているのか分かりませんが, 普通の定義に従って帰納法を使うと #1 の通り. ただしこれではもちろん完答ではありません.
ところで「上記にも記載してますが」ってなんだ.