CSC403: HW Answers [2/2] Previous pageContents

3.3.1

    AES =>  E
           / \
          A   S

      E         E S
     / \   =>  / | \
    A  QSY    A  Q  Y
          
      E S         E S U             S
     / | \   =>  / | | \   =>    /     \
    A  Q TUY    A  Q T  Y       E       U
                               / \     / \
                              A   Q   T   Y

           S                   S      
        /     \             /     \   
       E       U    =>    E O       U  
      / \     / \        / | \     / \                     
     A  IOQ  T   Y      A  I  Q   T   Y

            S       
         /     \    
       E O       U  
      / | \     / \ 
     A  IN Q   T   Y

===========================================================
3.3.2

    LPY =>  P  
           / \ 
          L   Y

       P          L P
      / \    =>  / | \
    HLM  XY     H  M  XY
          
      L P         L P X             P
     / | \   =>  / | | \   =>    /     \
    CH M RXY    CH M R  Y       L       X
                               / \     / \
                              CH  M   R   Y

           P                   P      
        /     \             /     \   
       L       X    =>    C L       X  
      / \     / \        / | \     / \ 
    ACH  M   R   Y      A  H  M   R   Y

            P       
         /     \    
       C L       X  
      / | \     / \ 
     A EH  M   RS  Y

===========================================================
3.3.3

Tree is:

       E R
     /  |  \
    AC  HM  SX

Here's one class of solution:    

Insert order:
+ first three inserted must include one of E,R and one from a leaf on either side.
+ next two include other of E,R + one from the leaf not included before.
+ the three remaining, which are from three different leaves

These are

    AEH, RX 
    AEX, HR
    ARX, EH
    HRX, AE

where order within the groups doesn't matter
    A could be C
    H could be M
    X could be S

But it's also possible:

    AER, (C)HX
    ERX, (S)AH

===========================================================
3.3.5

1:
          *

2:
         * *

3:
          *
        /   \
       *     *       

4:
          *
        /   \
       *    **

5a:
          *
        /   \
      * *   **

5b:
         * *
       /  |  \
     *    *   *

6:
         * *
       /  |  \
     *    *   **

7a (add to 3-node of 6):
          *
       /     \
      *       *
     / \     / \
    *   *   *   *

7b (add to 2-node of 6):
         * *
       /  |  \
     **   *   **

8a (add to 2-node of 7a or 3-node of 7b):
          *
       /     \
      *       *
     / \     / \
    *   *   *   **

8b (add to 2-node of 7b):
         * *
       /  |  \
     **   **  **

9a (add to 2-node of 8a or 3-node of 8b)
          *
       /     \
      *       *
     / \     / \
    *   *  **   **

9b (add to 2-node of 8a or 3-node of 8b)
          *
       /     \
      *       *
     / \     / \
    *   **  *   **
    
9c (add to 3-node of 8a)
          *
       /     \
      *      * *
     / \    / | \
    *   *  *  *  *

10a (add to 2-node of 9a or 9b)    
          *
       /     \
      *       *
     / \     / \
    *   ** **   **

10b (add to 3-node of 9a or 2-node of 9c)
          *
       /     \
      *      * *
     / \    / | \
    *   *  *  *  **

10c (add to 3-node of 9b or 2-node of 9c)
          *
       /     \
      *      * *
     / \    / | \
    *   ** *  *  *

===========================================================
3.3.9

i)   no - not balanced
ii)  no - not balanced
iii) yes
iv)  yes

===========================================================
3.3.10

            S                       S
         /     \                 /     \
       E O       U    ==        O       U
      / | \     / \           // \     / \
     A  IN Q   T   Y          E   Q   T   Y
                             / \
                            A   N
                              //
                              I              

===========================================================
3.3.11

            P                        P        
         /     \                 /       \     
       C L       X    ==        L         X
      / | \     / \           // \       / \   
     A EH  M   RS  Y          C   M     S   Y  
                             / \      //       
                            A   H     R        
                              //             
                              E              
    
===========================================================
3.3.14

  A          B
   \\  =>  //
    B      A  

    B          B
  // \\  =>   / \ 
  A   C      A   C

    B            B    
   / \          / \   
  A   C   ==>  A   D
       \\        //
        D        C   

    B              B             D   
   / \            / \\         // \  
  A   D    ==>   A   D   ==>   B   E
    // \\           / \       / \
    C   E          C   E     A   C   

      D               D    
    // \          //     \   
    B   E   ==>   B       F  
   / \   \\      / \    //
  A   C   F     A   C   E   


        D                   D                   D      
    //     \            //     \\            /     \   
    B       F   ==>     B       F   ==>     B       F  
   / \    // \\        / \     / \         / \     / \
  A   C   E   G       A   C   E   G       A   C   E   G


        D                      D         
     /     \                /     \      
    B       F              B       F     
   / \     / \     ==>    / \     / \    
  A   C   E   G          A   C   E   H   
               \\                  //   
                 H                 G   
    

         D                    D                    D        
      /     \              /     \             /       \     
     B       F            B       F           B         H    
    / \     / \    ==>   / \     / \\   ==>  / \      // \   
   A   C   E   H        A   C   E   H       A   C     F   I
             // \\                 / \               / \ 
             G   I                G   I             E   G   

          D                     D        
      /       \             /       \    
     B         H           B          H   
    / \      // \    ==>  / \      //   \  
   A   C     F   I       A   C     F     J 
            / \   \\              / \  //  
           E   G   J             E   G  I  

          D                        D                        D                       H           
      /       \                /       \                /       \\              //      \       
     B          H             B          H             B          H             D        J     
    / \      //   \    ==>   / \      //   \\   ==>   / \       /   \   ==>   /   \     / \   
   A   C     F     J        A   C     F     J        A   C     F     J       B     F   I   K  
            / \  // \\               / \   / \                / \   / \     / \   / \      
           E   G  I  K              E   G  I  K              E   G  I  K    A  C  E  G     
           
On 2-3 threes:

  ABC  =>   B
           / \ 
          A   C

     B         B D
    / \   =>  / | \
   A  CDE    A  C  E

     B D           B D F             D      
    / | \    =>   / | | \  =>     /     \   
   A  C EFG      A  C E  G       B       F  
                                / \     / \ 
                               A   C   E   G

         D                   D       
      /     \             /     \    
     B       F    =>     B       F H   
    / \     / \         / \     / | \  
   A   C   E  GHI      A   C   E  G  I                         
                 
         D                    D                      D H         
      /     \              /     \              /     |     \       
     B       F H    =>    B       F H J   =>   B      F      J   
    / \     / | \        / \     / | | \      / \    / \    / \  
   A   C   E  G IJK     A   C   E  G I  K    A   C  E   G  I   K

3-nodes pile up on the right in intermediate states.
At most one red link from root to leaf.

===========================================================
3.3.15
On 2-3 threes:

  IJK  =>   J
           / \ 
          I   K

     J         H J
    / \   =>  / | \
  GHI  K     G  I  K

     H J           F H J             H      
    / | \    =>   / | | \  =>     /     \   
  EFG I  K       E  G I  K       F       J  
                                / \     / \ 
                               E   G   I   K

          H                  H      
       /     \           /       \   
      F       J   =>    D F       J   
     / \     / \       / | \     / \ 
   CDE  G   I   K     C  E  G   I   K
                 
          H                     H                      D H        
      /       \             /       \              /    |     \    
     D F       J   =>     B D F       J   =>     B      F       J  
    / | \     / \        / | | \     / \        / \    / \     / \ 
  ABC E  G   I   K      A  C E  G   I   K      A   C  E   G   I   K

3-nodes pile up on the left in intermediate states.  
All red links on path from root to least node.

Previous pageContents