Algorithms and Data Structures
Excercise 11
Search 2 (Balanced Tree)

This exercise explains balanced tree.

Problem 1PostScript for printing

(1) Make 2-3-4 tree from the following data. Also, write the state at all stages of the calculation process.

C O C A C O L A

(2) Rewrite the tree made in (1) to red-black tree.

2-ノード 3-ノード 4-ノード

分割

2-3-4 木

赤黒木への変換

Problem 2

ex11-2-RB.c is a program which generates a red-black tree. Check that a red-black tree is correctly displayed (the place where * is marked is a red link). Although the functions used in this program, void rbtreeinsert(char c); NodePointer rotate(char v, NodePointer y); void split(char v); are much complicated, understand this program as much as possible.

Next, change this program and insert keys from A to Z into red-black tree in order.

Check that the result is balanced compared with the usual binary tree.

                                                                           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

Problem 3

Write the function named int treelevel(NodePointer node), which calculates the height of the tree and change ex11-2-RB.c as follows:

% ./a.out
      *U
   P
      *P
O
      N
         *L
   *H
         *G
      E
         *B
level: 3


The original Japanese document was written by Naoki Wakamatsu.
This translation document was written by Kenichi Maezu <m5061121@u-aizu.ac.jp>
and Hajime Matsui <m5061122@u-aizu.ac.jp> and checked by L. Pichl.