内部ノード数 n の 2色木の Black Height を h であらわすと以下の不等式が成り立つ。

2^(h-1) - 1 ≦ n ≦ 2^(2*h-1) - 1

よって、 h = O(log(n))


とある本に書いてあります。

これっておかしいですよね？

h は n の関数ではありません。内部ノード数から2色木の Black Height は一意的にはきまらないからです。

もちろん、　O(log(n)) の左辺には n の関数が来るきまりです。

ですので、 h = O(log(n)) と書くのはおかしいのではないでしょうか？