平衡木(へいこうぎ) (アルゴリズムC 第2巻 p.27) として 2-3-4 木 (アルゴリズムC 第2巻 p.28) を扱います。 通常の木とは違い、バランスのとれた(平衡した)木を作ることができます。 木が平衡している(木の高さが低い)と、 データの探索を速く行うことができます。
(1) 次のデータから 2-3-4 木を作成しなさい。 ただし、途中の過程も書くこと。
C O C A C O L A
(2) (1) で作成した木を赤黒木で書き直しなさい。
演習第7回でやったような二分木の作り方では、 バランスの悪い偏った木ができることがある。2-3-4 木を用いれば、 バランスのとれた(平衡した)木を作ることができます。
二分木では
という手が二本のノード(2-ノード)だけでしたが、2-3-4 木ではこれに加えて
データが二つ入って、手が三本の 3-ノード
データが三つ入って、手が四本の 4-ノード
を用います。
(1) 2-3-4 木を作る手順は次のようになります。
分割とは、4-ノードの真ん中のデータを親ノードに渡すことです
(アルゴリズムC 第2巻 p.30)
。
以下の例を参考にして作ってみてください。
(2) 赤黒木
(アルゴリズムC 第2巻 p.32)
は 2-3-4 木を 2-ノードだけで表したものです。
ただし、3-ノードや 4-ノードは次のように赤い手を使って表現します。
ex11-2-RB.c は赤黒木を生成するプログラムである。
実行して赤黒木が表示されることを確認しなさい
(*
が付いている所は赤いリンクである)。
また、この中で使われている関数
void rbtreeinsert(char c);
(アルゴリズムC 第2巻 p.34)
NodePointer rotate(char v, NodePointer y);
(アルゴリズムC 第2巻 p.37)
void split(char v);
(アルゴリズムC 第2巻 p.39)
はとても複雑であるが、教科書などを参考にしてできるだけ理解しなさい。
次にこのプログラムを変更して、A
から Z
までのキーを順に赤黒木に入れなさい。
結果が通常の二分木と比べて平衡していることを確認すること。
演習第7回の問題2 に対して同様にキーを入れていった場合、このような木が作られます。
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 関数は演習第7回の問題2 でもそのまま動くはずです。二分木と赤黒木の違いは、構造体 node の中に変数 red があるかどうかだけだからです。
演習第7回の問題2の二分木で、 同じ条件で実験を 10,000 回行ったときの平均の木の高さは 225 になりました。赤黒木ではどのくらいの高さになるか調べてみてください。