On binary tree encodements (Q795519)

A data encoding scheme involving the linearization of binary trees is presented and analyzed. This encoding scheme is self-delimiting, uniquely deconcatenable and has other attractive properties for certain kinds of applications (such as associative memory). However, the number of legal memory configurations, \(d_ n\), that can be placed in an n-bit memory using this scheme is less than that \((2^ n)\) of standard binary. The number of n-bit legal memory configurations is shown to be 0 for \(n=0\), \({1\over2}C^ n_{n/2}\) for \(n>0\) and even, and \(C^{n-1}_{(n-1)/2}\) for \(n>0\) and odd. The number of n-node ordered forests of complete binary trees also corresponds to \(d_ n\). A comparison of \(d_ n\) and \(2^ n\) is performed to show that for large n the storage capacity loss due to the use of this scheme is insignificant. For example, in a \(10^ 6\)-bit memory, less than 12 bits of storage capacity are lost.