クラフトの不等式
二分木について、クラフトの不等式を適用すると、次が成り立つ。
∑ l ∈ l e a v e s 2 − d e p t h ( l ) ≤ 1 {\displaystyle \sum _{\ell \in \mathrm {leaves} }2^{-\mathrm {depth} (\ell )}\leq 1}
これは、木の葉ノードに関する総和である。深さとは、根からの距離を意味する。右図の木で言えば、この総和は次のようになる。
1 4 + 4 ( 1 8 ) = 3 4 ≤ 1 {\displaystyle {\frac {1}{4}}+4\left({\frac {1}{8}}\right)={\frac {3}{4}}\leq 1}