という手が二本のノード（2-ノード）だけでしたが、2-3-4 木ではこれに加えて
データが二つ入って、手が三本の 3-ノード
データが三つ入って、手が四本の 4-ノードを用います。
平衡木（へいこうぎ） （アルゴリズムＣ 第２巻 p.27） として 2-3-4 木 （アルゴリズムＣ 第２巻 p.28） を扱います。 通常の木とは違い、バランスのとれた（平衡した）木を作ることができます。 木が平衡している（木の高さが低い）と、 データの探索を速く行うことができます。
(1) 次のデータから 2-3-4 木を作成しなさい。 ただし、途中の過程も書くこと。
C O C A C O L A
(2) (1) で作成した木を赤黒木で書き直しなさい。
演習第７回でやったような二分木の作り方では、 バランスの悪い偏った木ができることがある。2-3-4 木を用いれば、 バランスのとれた（平衡した）木を作ることができます。
二分木では
という手が二本のノード（2-ノード）だけでしたが、2-3-4 木ではこれに加えて
データが二つ入って、手が三本の 3-ノード
データが三つ入って、手が四本の 4-ノード
を用います。
(1) 2-3-4 木を作る手順は次のようになります。
分割とは、4-ノードの真ん中のデータを親ノードに渡すことです
（アルゴリズムＣ 第２巻 p.30）
。
以下の例を参考にして作ってみてください。
(2) 赤黒木
（アルゴリズムＣ 第２巻 p.32）
は 2-3-4 木を 2-ノードだけで表したものです。
ただし、3-ノードや 4-ノードは次のように赤い手を使って表現します。
ex11-2-RB.c は赤黒木を生成するプログラムである。
実行して赤黒木が表示されることを確認しなさい
（*が付いている所は赤いリンクである）。
また、この中で使われている関数
void rbtreeinsert(char c);
（アルゴリズムＣ 第２巻 p.34）
NodePointer rotate(char v, NodePointer y);
（アルゴリズムＣ 第２巻 p.37）
void split(char v);
（アルゴリズムＣ 第２巻 p.39）
はとても複雑であるが、教科書などを参考にしてできるだけ理解しなさい。
次にこのプログラムを変更して、A から Z
までのキーを順に赤黒木に入れなさい。
結果が通常の二分木と比べて平衡していることを確認すること。
演習第７回の問題２ に対して同様にキーを入れていった場合、このような木が作られます。
Z
Y
X
W
V
U
T
S
R
Q
P
O
N
M
L
K
J
I
H
G
F
E
D
C
B
A
整列したデータを入れた場合に偏った木ができるのは、 二分木の欠点のひとつです。赤黒木では改善されていることを確認してください。
木の高さを求める関数 int treelevel(NodePointer node);
を作成し、ex11-2-RB.c を次のように変更しなさい。
A 〜 Z を用いる
treelevel 関数はループでも再帰でも良いですが、多分再帰の方が作りやすいです。
また、ランダムに A 〜 Z を返す関数
char rand_ascii(void); を作ると良いでしょう。
まずは少ない個数で木と高さを表示させて、うまく動いているかを確認してください。
% ./a.out
*U
P
*P
O
N
*L
*H
*G
E
*B
level: 3
treelevel 関数は演習第７回の問題２ でもそのまま動くはずです。二分木と赤黒木の違いは、構造体 node の中に変数 red があるかどうかだけだからです。
演習第７回の問題２の二分木で、 同じ条件で実験を 10,000 回行ったときの平均の木の高さは 225 になりました。赤黒木ではどのくらいの高さになるか調べてみてください。