5.txt

5.txt

inorder (reflect t) = rev (inorder t) について

(i) t = Lf の時、成り立つことを示せばよい。

<左辺> = inorder (reflect Lf)
       = inorder Lf             reflectの定義より
       = []                     inorderの定義より

<右辺> = rev (inorder Lf)
       = rev Lf                 inorderの定義より
       = []                     revの定義より

よって、両辺が同じになったので、成り立つ。

(ii) t = t1, t2で成り立つと仮定して、t = Br (v, t1, t2)が成り立つことを示せばよい。

<左辺> = inorder (reflect (Br v, t1, t2))
       = inorder (Br v, (reflect t2), (reflect t1))             reflectの定義より
       = (inorder (reflect t2)) @ v @ (inorder (reflect t1))    inorderの定義より

<右辺> = rev (inorder (Br v, t1, t2))
       = rev ( (inorder t1) @ v @ (inorder t2) )                inorderの定義より
       = (rev (inorder t2)) @ v @ (rev (inorder t1))            revの定義より
       = (inorder (reflect t2)) @ v @ (inorder (reflect t1))    仮定より

よって、成り立つ

(i), (ii)より、成り立つ。