アルゴリズムとデータ構造
演習第 11 回
サーチ2(平衡木)

平衡木(へいこうぎ) (アルゴリズムC 第2巻 p.27) として 2-3-4 木 (アルゴリズムC 第2巻 p.28) を扱います。 通常の木とは違い、バランスのとれた(平衡した)木を作ることができます。 木が平衡している(木の高さが低い)と、 データの探索を速く行うことができます。

問題1印刷用 PostScript

(1) 次のデータから 2-3-4 木を作成しなさい。 ただし、途中の過程も書くこと。

C O C A C O L A

(2) (1) で作成した木を赤黒木で書き直しなさい。

演習第7回でやったような二分木の作り方では、 バランスの悪い偏った木ができることがある。2-3-4 木を用いれば、 バランスのとれた(平衡した)木を作ることができます。

二分木では 2-ノード という手が二本のノード(2-ノード)だけでしたが、2-3-4 木ではこれに加えて
3-ノード データが二つ入って、手が三本の 3-ノード
4-ノード データが三つ入って、手が四本の 4-ノード
を用います。

(1) 2-3-4 木を作る手順は次のようになります。

  1. 木を辿って、データを入れる場所を探していく
  2. 辿る途中に 4-ノードがあれば分割(split)する
  3. データを入れる

分割とは、4-ノードの真ん中のデータを親ノードに渡すことです (アルゴリズムC 第2巻 p.30) 。
分割

以下の例を参考にして作ってみてください。
2-3-4 木

(2) 赤黒木 (アルゴリズムC 第2巻 p.32) は 2-3-4 木を 2-ノードだけで表したものです。 ただし、3-ノードや 4-ノードは次のように赤い手を使って表現します。
赤黒木への変換

問題2

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

整列したデータを入れた場合に偏った木ができるのは、 二分木の欠点のひとつです。赤黒木では改善されていることを確認してください。

問題3

木の高さを求める関数 int treelevel(NodePointer node); を作成し、ex11-2-RB.c を次のように変更しなさい。

treelevel 関数はループでも再帰でも良いですが、多分再帰の方が作りやすいです。 また、ランダムに AZ を返す関数 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 になりました。赤黒木ではどのくらいの高さになるか調べてみてください。


Written by わかまつなおき