/**
 *   Løsning til eksamen i AlgMet, desember 2024, oppgave 2.
 *
 *   @file     EX_H24_2.TXT
 *   @author   Frode Haug, NTNU
 */



OPPGAVE A:
==========

    Når "J" fjernes:
        - "J" har et høyre barn uten sitt venstre barn, derfor er
        - den ANDRE setningen med  "else if (!fjernes->right->left) ....."  aktuell.

        - Treet under "G" etter at "J" er fjernet:

                             G
                          /     \
                       ....       K
                                /   \
                               I     L
                              /
                             H


    Når "M" fjernes:
        - vil ingen av de to første situasjonene være aktuelle, derfor er
        - den TREDJE setningen med  "else ......"  aktuell.
          Her vil den sekvensielt etterfølgende noden ("N")
          erstatte den som fjernes ("M").

        - Treet etter at "M" er fjernet:

                             N
                          /     \
                        G         R
                      /   \     /   \
                    ...   ...  O    ...
                                \
                                ...


    Når "R" fjernes:
        - vil ingen av de to første situasjonene være aktuelle, derfor er
        - den TREDJE setningen med  "else ......"  aktuell.
          Her vil den sekvensielt etterfølgende noden ("S")
          erstatte den som fjernes ("R").

        - Treet etter at "R" er fjernet:

                             M
                          /      \
                       ....        S
                                 /   \
                               O       U
                              / \     / \
                           ...   ... T  ...





OPPGAVE B:
==========

 Korteste sti fra "A" til ALLE de andre nodene vil involvere kantene:

         AD   AE   BD   BF   BI  CE   DH   GH



   Prioritetskøen etterhvert:

              H-1d   A-1d   E-2a   G-2h          F-3b
              A-1d   G-2h   G-2h   B-2d   B-2d   I-4b   I-4b
         D*   B-2d   B-2d   B-2d   C-4e   C-4e   C-4e   C-4e   C-4e





OPPGAVE C:
==========

    OPTISKE ILLUSJONER ILLUSTRERER OPTISKE SAKER


    Har bokstavfrekvensen:
                    ' '   A   E   I   J   K   L   N   O   P   R   S   T   U
                k    0    1   5   9  10  11  12  14  15  16  18  19  20  21
       frekvens[k]   4    1   6   4   1   3   4   1   3   2   5   5   3   2




    Dette medfører følgende forelder-array:
                k   ' '   A   E   I   J   K   L   N   O   P   R   S   T   U
       frekvens[k]   4    1   6   4   1   3   4   1   3   2   5   5   3   2
       forelder[k]  -33  28  36  33 -27 -31 -32  27  31 -29 -34  34 -30  29

                k    27  28  29  30  31  32  33  34  35  36  37  38  39
       frekvens[k]    2   3   4   6   6   8   8  10  12  14  18  26  44
       forelder[k]  -28  30  32 -35  35  37 -36 -37  38 -38  39 -39   0



 
    Tegnet som et tre/en trie:                39
                                       /               \
                                   37                      38
                                /      \               /        \
                              32        34            35        36
                            /    \    /    \        /    \    /    \
                          29      L  S      R     31      30 E      33
                         /  \                    /  \    /  \      /  \
                        U    P                  O    K 28    T    I   ' '
                                                      /  \
                                                     A    27
                                                         /  \
                                                        N    J




    Vi får altså følgende bitmønster:
               ' '   A      E    I     J     K   L      N    O    P   R   S   T     U
       bits    1111 10100 110 1110 101011 1001 001 101010 1000 0001 011 010 1011 0000
       kode[k]   15    20   6   14     43    9   1     42    8    1   3   2   11    0
       len[k]     4     5   3    4      6    4   3      6    4    4   3   3    4    4




    Totalt antall bit i kodet melding blir:
        (4*4) + (1*5) + (6*3) + (4*4) + (1*6) + (3*4) + (4*3) +
        (1*6) + (3*4) + (2*4) + (5*3) + (5*3) + (3*4) + (2*4)   =   161 bits
                                                                    ========