Burt Rosenberg

Problem Set 7 _{Due: 22 November, 1994}^{Out: 8 November, 1994}

Goals

Practice with self-balancing tree.

Reading Assignment

For this homework, you should have read all chapters in Condensed Pascal up to 18. Please also read Chapter 18, in order to follow this week’s class discussion.

Programming Assignment

Write a 2-4 tree program. It should take keyboard input, break it into words, and insert new words into your 2-4 tree. Repeated words will increment a count associated with each word. You will be able to use large amounts of your previously written code. In particular, MyString software is relevant to the current project. However, MyString software must be modified to a NuString, which is a pointer to a MyString. This is generally how data is passed in working programs — using pointers to data rather than actual copies of the data. Extra Credit: Write Delete and Pretty-Print for your 2-4 tree program.

Example Output

Input: ROMEO AND JULIET, ACT II, SCENE II.
[JULIET appears above at a window.]
      But, soft! what light through yonder window breaks?
      It is the east, and Juliet is the sun!-
      Arise, fair sun, and kill the envious moon,
      Who is already sick and pale with grief,
      That thou her maid art far more fair than she:
[]-- 1:_min 1:but 1:~max

                            []-- 1:_min 1:but 1:soft 1:~max

                                                        []--+--- 1:_min
                                                            |    1:but
                                                            +--- 1:soft
                                                                 1:what
                                                                 1:~max

[]--+--- 1:_min
|    1:but
+--- 1:light
1:soft
1:what
1:~max

[]--+--- 1:_min
|    1:but
+--- 1:light
|    1:soft
+--- 1:through
1:what
1:~max

[]--+--- 1:_min
|    1:but
+--- 1:light
|    1:soft
+--- 1:through
     1:what
     1:yonder
     1:~max
[]--+--- 1:_min
|    1:but
+--- 1:light
|    1:soft
+--- 1:through
|    1:what
+--- 1:window
1:yonder
1:~max

[]--+---+--- 1:_min
|   |    1:breaks
|   |    1:but
|   +--- 1:light
|        1:soft
+---+--- 1:through
|    1:what
+--- 1:window
1:yonder
1:~max

[]--+---+--- 1:_min
|   |    1:breaks
|   |    1:but
|   +--- 1:it
|        1:light
|        1:soft
+---+--- 1:through
    |    1:what
    +--- 1:window
         1:yonder
         1:~max
[]--+---+--- 1:_min
|   |    1:breaks
|   |    1:but
|   +--- 1:is
|        1:it
|        1:light
|        1:soft
+---+--- 1:through
|    1:what
+--- 1:window
1:yonder
1:~max

[]--+---+--- 1:_min
|   |    1:breaks
|   |    1:but
|   +--- 1:is
|        1:it
|        1:light
|        1:soft
+---+--- 1:the
|    1:through
|    1:what
+--- 1:window
1:yonder
1:~max

[]--+---+--- 1:_min
|   |    1:breaks
|   |    1:but
|   +--- 1:east
|   |    1:is
|   |    1:it
|   +--- 1:light
|        1:soft
+---+--- 1:the
    |    1:through
    |    1:what
    +--- 1:window
         1:yonder
         1:~max

[]--+---+--- 1:_min
|   |    1:and
|   |    1:breaks
|   |    1:but
|   +--- 1:east
|   |    1:is
|   |    1:it
|   +--- 1:light
|        1:soft
+---+--- 1:the
|    1:through
|    1:what
+--- 1:window
1:yonder
1:~max

[]--+---+--- 1:_min
|   |    1:and
|   |    1:breaks
|   |    1:but
|   +--- 1:east
|   |    1:is
|   |    1:it
|   +--- 1:juliet
|        1:light
|        1:soft
+---+--- 1:the
|    1:through
|    1:what
+--- 1:window
1:yonder
1:~max

[]--+---+--- 1:_min
|   |    1:and
|   |    1:breaks
|   |    1:but
|   +--- 1:east
|   |    2:is
|   |    1:it
|   +--- 1:juliet
|        1:light
|        1:soft
+---+--- 1:the
    |    1:through
    |    1:what
    +--- 1:window
         1:yonder
         1:~max
[]--+---+--- 1:_min
|   |    1:and
|   |    1:breaks
|   |    1:but
|   +--- 1:east
|   |    2:is
|   |    1:it
|   +--- 1:juliet
|        1:light
|        1:soft
+---+--- 2:the
|    1:through
|    1:what
+--- 1:window
1:yonder
1:~max

[]--+---+--- 1:_min
|   |    1:and
|   |    1:breaks
|   |    1:but
|   +--- 1:east
|   |    2:is
|   |    1:it
|   +--- 1:juliet
|        1:light
|        1:soft
+---+--- 1:sun
|    2:the
|    1:through
|    1:what
+--- 1:window
1:yonder
1:~max

[]--+---+--- 1:_min
|   |    1:and
|   +--- 1:arise
|   |    1:breaks
|   |    1:but
|   +--- 1:east
|   |    2:is
|   |    1:it
|   +--- 1:juliet
|        1:light
|        1:soft
+---+--- 1:sun
    |    2:the
    |    1:through
    |    1:what
    +--- 1:window
         1:yonder
         1:~max

[]--+---+--- 1:_min
|   |    1:and
|   +--- 1:arise
|        1:breaks
|        1:but
+---+--- 1:east
|   |    1:fair
|   |    2:is
|   |    1:it
|   +--- 1:juliet
|        1:light
|        1:soft
+---+--- 1:sun
|    2:the
|    1:through
|    1:what
+--- 1:window
1:yonder
1:~max

[]--+---+--- 1:_min
|   |    1:and
|   +--- 1:arise
|        1:breaks
|        1:but
+---+--- 1:east
|   |    1:fair
|   |    2:is
|   |    1:it
|   +--- 1:juliet
|        1:light
|        1:soft
+---+--- 2:sun
|    2:the
|    1:through
|    1:what
+--- 1:window
1:yonder
1:~max

[]--+---+--- 1:_min
|   |    2:and
|   +--- 1:arise
|        1:breaks
|        1:but
+---+--- 1:east
|   |    1:fair
|   |    2:is
|   |    1:it
|   +--- 1:juliet
|        1:light
|        1:soft
+---+--- 2:sun
    |    2:the
    |    1:through
    |    1:what
    +--- 1:window
         1:yonder
         1:~max
[]--+---+--- 1:_min
|   |    2:and
|   +--- 1:arise
|        1:breaks
|        1:but
+---+--- 1:east
|   |    1:fair
|   |    2:is
|   |    1:it
|   +--- 1:juliet
|        1:kill
|        1:light
|        1:soft
+---+--- 2:sun
|    2:the
|    1:through
|    1:what
+--- 1:window
1:yonder
1:~max

[]--+---+--- 1:_min
|   |    2:and
|   +--- 1:arise
|        1:breaks
|        1:but
+---+--- 1:east
|   |    1:fair
|   |    2:is
|   |    1:it
|   +--- 1:juliet
|        1:kill
|        1:light
|        1:soft
+---+--- 2:sun
|    3:the
|    1:through
|    1:what
+--- 1:window
1:yonder
1:~max

[]--+---+--- 1:_min
|   |    2:and
|   +--- 1:arise
|        1:breaks
|        1:but
+---+--- 1:east
|   |    1:envious
|   |    1:fair
|   +--- 2:is
|   |    1:it
|   +--- 1:juliet
|        1:kill
|        1:light
|        1:soft
+---+--- 2:sun
    |    3:the
    |    1:through
    |    1:what
    +--- 1:window
         1:yonder
         1:~max

[]--+---+--- 1:_min
|   |    2:and
|   +--- 1:arise
|        1:breaks
|        1:but
+---+--- 1:east
|   |    1:envious
|   |    1:fair
|   +--- 2:is
|   |    1:it
|   +--- 1:juliet
|   |    1:kill
|   +--- 1:light
|        1:moon
|        1:soft
+---+--- 2:sun
    |    3:the
    |    1:through
    |    1:what
    +--- 1:window
         1:yonder
         1:~max

                        []--+---+--- 1:_min
                            |   |    2:and
                            |   +--- 1:arise
                            |        1:breaks
                            |        1:but
                            +---+--- 1:east
                            |   |    1:envious
                            |   |    1:fair
                            |   +--- 2:is
                            |   |    1:it
                            |   +--- 1:juliet
                            |   |    1:kill
                            |   +--- 1:light
                            |        1:moon
                            |        1:soft
                            +---+--- 2:sun
                                |    1:that
                                |    3:the
                                +--- 1:through
                                |    1:what
                                +--- 1:window
                                     1:yonder
                                     1:~max

                                                    []--+---+--- 1:_min
                                                        |   |    2:and
                                                        |   +--- 1:arise
                                                        |        1:breaks
                                                        |        1:but
                                                        +---+--- 1:east
                                                        |   |    1:envious
                                                        |   |    1:fair
                                                        |   +--- 2:is
                                                        |   |    1:it
                                                        |   +--- 1:juliet
                                                        |   |    1:kill
                                                        |   +--- 1:light
                                                        |        1:moon
                                                        |        1:soft
                                                        +---+--- 2:sun
                                                            |    1:that
                                                            |    3:the
                                                            +--- 1:thou
                                                            |    1:through
                                                            |    1:what
                                                            +--- 1:window
                                                                 1:yonder
                                                                 1:~max

[]--+---+--- 1:_min
|   |    2:and
|   +--- 1:arise
|        1:breaks
|        1:but
+---+--- 1:east
|   |    1:envious
|   |    1:fair
|   +--- 1:her
|        2:is
|        1:it
+---+--- 1:juliet
|   |    1:kill
|   +--- 1:light
|        1:moon
|        1:soft
+---+--- 2:sun
    |    1:that
    |    3:the
    +--- 1:thou
    |    1:through
    |    1:what
    +--- 1:window
         1:yonder
         1:~max

                        []--+---+---+--- 1:_min
                            |   |   |    2:and
                            |   |   +--- 1:arise
                            |   |        1:breaks
                            |   |        1:but
                            |   +---+--- 1:east
                            |       |    1:envious
                            |       |    1:fair
                            |       +--- 1:her
                            |            2:is
                            |            1:it
                            +---+---+--- 1:juliet
                                |   |    1:kill
                                |   +--- 1:light
                                |        1:maid
                                |        1:moon
                                |        1:soft
                                +---+--- 2:sun
                                    |    1:that
                                    |    3:the
                                    +--- 1:thou
                                    |    1:through
                                    |    1:what
                                    +--- 1:window
                                         1:yonder
                                         1:~max

                                                    []--+---+---+--- 1:_min
                                                        |   |   |    2:and
                                                        |   |   +--- 1:arise
                                                        |   |        1:art
                                                        |   |        1:breaks
                                                        |   |        1:but
                                                        |   +---+--- 1:east
                                                        |       |    1:envious
                                                        |       |    1:fair
                                                        |       +--- 1:her
                                                        |            2:is
                                                        |            1:it
                                                        +---+---+--- 1:juliet
                                                            |   |    1:kill
                                                            |   +--- 1:light
                                                            |        1:maid
                                                            |        1:moon
                                                            |        1:soft
                                                            +---+--- 2:sun
                                                                |    1:that
                                                                |    3:the
                                                                +--- 1:thou
                                                                |    1:through
                                                                |    1:what
                                                                +--- 1:window
                                                                     1:yonder
                                                                     1:~max

[]--+---+---+--- 1:_min
|   |   |    2:and
|   |   +--- 1:arise
|   |        1:art
|   |        1:breaks
|   |        1:but
|   +---+--- 1:east
|       |    1:envious
|       |    1:fair
|       +--- 1:far
|            1:her
|            2:is
|            1:it
+---+---+--- 1:juliet
    |   |    1:kill
    |   +--- 1:light
    |        1:maid
    |        1:moon
    |        1:soft
    +---+--- 2:sun
        |    1:that
        |    3:the
        +--- 1:thou
        |    1:through
        |    1:what
        +--- 1:window
             1:yonder
             1:~max

                        []--+---+---+--- 1:_min
                            |   |   |    2:and
                            |   |   +--- 1:arise
                            |   |        1:art
                            |   |        1:breaks
                            |   |        1:but
                            |   +---+--- 1:east
                            |       |    1:envious
                            |       |    1:fair
                            |       +--- 1:far
                            |            1:her
                            |            2:is
                            |            1:it
                            +---+---+--- 1:juliet
                                |   |    1:kill
                                |   +--- 1:light
                                |   |    1:maid
                                |   +--- 1:moon
                                |        1:more
                                |        1:soft
                                +---+--- 2:sun
                                    |    1:that
                                    |    3:the
                                    +--- 1:thou
                                    |    1:through
                                    |    1:what
                                    +--- 1:window
                                         1:yonder
                                         1:~max

                                                    []--+---+---+--- 1:_min
                                                        |   |   |    2:and
                                                        |   |   +--- 1:arise
                                                        |   |        1:art
                                                        |   |        1:breaks
                                                        |   |        1:but
                                                        |   +---+--- 1:east
                                                        |       |    1:envious
                                                        |       |    2:fair
                                                        |       +--- 1:far
                                                        |            1:her
                                                        |            2:is
                                                        |            1:it
                                                        +---+---+--- 1:juliet
                                                            |   |    1:kill
                                                            |   +--- 1:light
                                                            |   |    1:maid
                                                            |   +--- 1:moon
                                                            |        1:more
                                                            |        1:soft
                                                            +---+--- 2:sun
                                                                |    1:that
                                                                |    3:the
                                                                +--- 1:thou
                                                                |    1:through
                                                                |    1:what
                                                                +--- 1:window
                                                                     1:yonder
                                                                     1:~max

[]--+---+---+--- 1:_min
|   |   |    2:and
|   |   +--- 1:arise
|   |        1:art
|   |        1:breaks
|   |        1:but
|   +---+--- 1:east
|       |    1:envious
|       |    2:fair
|       +--- 1:far
|            1:her
|            2:is
|            1:it
+---+---+--- 1:juliet
    |   |    1:kill
    |   +--- 1:light
    |   |    1:maid
    |   +--- 1:moon
    |        1:more
    |        1:soft
    +---+--- 2:sun
        |    1:than
        |    1:that
        |    3:the
        +--- 1:thou
        |    1:through
        |    1:what
        +--- 1:window
             1:yonder
             1:~max

                        []--+---+---+--- 1:_min
                            |   |   |    2:and
                            |   |   +--- 1:arise
                            |   |        1:art
                            |   |        1:breaks
                            |   |        1:but
                            |   +---+--- 1:east
                            |       |    1:envious
                            |       |    2:fair
                            |       +--- 1:far
                            |            1:her
                            |            2:is
                            |            1:it
                            +---+---+--- 1:juliet
                                |   |    1:kill
                                |   +--- 1:light
                                |   |    1:maid
                                |   +--- 1:moon
                                |        1:more
                                |        1:she
                                |        1:soft
                                +---+--- 2:sun
                                    |    1:than
                                    |    1:that
                                    |    3:the
                                    +--- 1:thou
                                    |    1:through
                                    |    1:what
                                    +--- 1:window
                                         1:yonder
                                         1:~max