構造帰納法は、アルゴリズムの終了特性を証明する通常の方法だと思いますが、ツリーアルゴリズムの帰納法によって証明するのはそれほど簡単ではありません。今、私は事前注文ツリートラバーサルアルゴリズムが終了可能であることを証明するのに苦労しています:
preorder(node)
if node == null then return
visit(node)
preorder(node.left)
preorder(node.right)
どのように証明すればよいですか?
構造帰納法は、アルゴリズムの終了特性を証明する通常の方法だと思いますが、ツリーアルゴリズムの帰納法によって証明するのはそれほど簡単ではありません。今、私は事前注文ツリートラバーサルアルゴリズムが終了可能であることを証明するのに苦労しています:
preorder(node)
if node == null then return
visit(node)
preorder(node.left)
preorder(node.right)
どのように証明すればよいですか?
木の高さの強い誘導によって。
アルゴリズムは高さ 0 のツリーで終了します。これは、高さ 0 のツリーには子のないルートがあるためです。visit(node)
ルート上は単一のステップであり、両方であるため、にアクセスしnode.left
てnode.right
終了しますNULL
。
高さ のすべての木で事前順序トラバーサルが終了すると仮定すると、高さ の0, 1, 2, .. n
すべての木で終了することが証明されn+1
ます。それを見てみましょう:
visit(node)
ワンステップなので終了。
preorder(node.left)
ツリーの高さが である場合、高さn+1
はnode.left
高々 のツリーでn
あり、強い帰納的仮説により、事前順序トラバーサルは高さが より小さいか等しいツリーで終了するため、終了しますn
。
preorder(node.right)
と同じnode.left
。
ツリーにはサイクルが含まれていません。サイクルがあった場合、アルゴリズムは永久に実行されます。したがって、サイクルがないことが証明の重要なポイントです。他のポイントは左または右であり、メモリの制約によって最終的に null を指すようにバインドされます。