結論
次の条件が成り立つとき、かつそのときに限り、頂点を赤く塗ると良いです:（根については不成立としておきます）
- 高さ*1が奇数で、
- かつ親の高さが偶数
そうすると、高さが $h$ の AVL 木は黒高さ $\lceil \frac h 2 \rceil$ の赤黒木になります。
塗った結果の例
縦座標は高さです。AVL 木ですから、親と子の高さの差は $2$ 以下です。また赤黒木を 2-3-4 木と見たときの頂点を四角で囲っています。2-3-4 木としての高さと、AVL 木としての高さが対応していることも視覚的にわかりやすいです。
証明
- 根が黒であること: 塗り方の定義に書いてあります。
- 赤頂点が連続しないこと: 赤頂点の親の高さは偶数なので黒頂点です。
- 全ての頂点について、その左右の黒高さが等しいこと: 左右の子の高さから黒高さを計算すると、自分が偶数、子が奇数のときだけ予定より $1$ 高くなってしまうように見えますが、この場合は（またこの場合に限り）子が赤くなり $1$ 減りますから、よいです。
直感的な理解
まずは先ほどの図のように、高さを縦座標として AVL 木を書きます。次に、下から $2$ 層づつに区切ります。すると各層の連結成分の大きさは $1$ 頂点以上 $3$ 頂点以下になりますから、これを 2-3-4 木とみなし、それに基づいて色を塗っていけばよいです。
*1:ある点から最も遠い葉へのパス上の頂点の個数
