枝分かれの果て [GRE CS]

GRE・CS問題第10問。「2分木」とかの一般的な場合であるk分木について。

で、この問題、図を書いてみれば一発で分かる類のもんで、だから、ちゃんと図を作って提示しよう、と思ったんだけど、軽くてフリーですいすいと木が書けるようなソフトがないんだよね。だから、とりあえず文字だけによる説明（あとで、何かいいソフト見つけたら、画像を追加アップするかも）。

最初に、あんま説明も要らないと思うけど、「k分木」とは何ぞや、ということについて。まず、「2分木」が「木の性質を持ち、かつ各点について最大2つの子しかもたないもの」だったことを思い出そう。そうすりゃ、「k分木」ってのは、件の定義の「2」を「k」に変えるだけ。

で、問題はどんなかって言うと、「高さh、頂点数nのk分木の、最大の葉の数は？」というもの。簡単っしょ？

まず、高さ1、つまり「根」しかないk分木を考えよう。このとき、最大の葉の数は明らかにk（=k1）。次に、高さ2のk分木を考えると、前のステップで導出した根からk個の子が出てるものとなる。だから、そのk個のおのおのに対して、最大kの葉が出来うるんだから、全体として取りうる葉の最大値はk2……ってえことは？　そう、高さhの場合、最大の葉の数はkhであろうことが用意に推測できる。

ってなわけで、問題文に出てくる「n」なんて、全然関係のない、ちょっとだけ意地悪な問題でした。