2.1 Worst-Case Entropyにnノードの順序木は2nビットで表現できると書いてあります。
これは深さ優先探索をして、ノードに入る時に 1 を、出る時に 0 を出力することで実現できます。各ノードに対して入る時と出る時にビットが出力されるので2ビット、これがnノードあるので2nビットです。
また 1 を ( に、 0 を ) に置き換えれば、これは木の括弧表現ということもできます。
例えば以下の通り。
Fig.1 11110000 or (((())))
Fig.2 11100100 or ((())())
Fig.3 11010100 or (()()())
これらのバイナリ表現はよく見ると、いずれも先頭に1が2つ、末尾に0が2つあります。
これらは常にそうなります（のはず）。
なぜか。
まず、先頭の1と末尾の0はルートノードを表しています。木の探索はルートからはじまってルートで終わるからです。
そして、ルートノード以外のノードについて1と0の対応をきちんと取るには、2番目が1、後ろから2番目が0でないといけません。
2番目が0だとルートノードの1と対応が取れてしまうし、後ろから2番目が1だとルートノードの0と対応が取れてしまうからです。
したがって、これらの4ビットは自明なので消してしまっても問題ありません。
結果、2n-4ビットあれば木のバイナリ表現ができることになります。
余談ですが、今回の内容はNavarro本に It is an easy exercise ... We leave as an exercise to the reader ... と書いてあってめちゃくちゃ面白かった。
この表現海外でも流行ってるのか。
