/**
 *   Løsning til eksamen i AlgMet, november 2025, oppgave 2.
 *
 *   @file     EX_H25_2.TXT
 *   @author   Frode Haug, NTNU
 */



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

    Keyene:             N   O   T   U   K   H   O   S   T
    k (alfabetnr):     14  15  20  21  11   8  15  19  20
    Hash1 (M = 11):     3   4   9  10   0   8   4   8   9
    Hash2:              1   3   1   3   1   1   3   2   1

    Indeksene:          0   1   2   3   4   5   6   7   8   9  10
                        -   -   -   N   -   -   -   -   -   -   -
                        -   -   -   N   O   -   -   -   -   -   -
                        -   -   -   N   O   -   -   -   -   T   -
                        -   -   -   N   O   -   -   -   -   T   U
                        K   -   -   N   O   -   -   -   -   T   U
                        K   -   -   N   O   -   -   -   H   T   U
                        K   -   -   N   O   -   -   O*  H   T   U
                        K   S*  -   N   O   -   -   O*  H   T   U
                        K   S*  T*  N   O   -   -   O*  H   T   U

                        (* = bokstaver som hashes på plass ved bruk av hash2 også.)





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

    Fringen etterhvert (NVd = Nodenavn, Vekt, dad):

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

                              H-2f   G-1h   B-1g
                       F-2c   E-2f   E-2f   E-2f   E-2f   A-1e
                  C*   D-2c   D-2c   D-2c   D-2c   D-2c   D-2c   D-1a


    Minimums spenntreet:   A ------ E       H
                           |          \   /   \
                           D     C --- F       G
                                              /
                                             B





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

    "gForeldre"-arrayen etterhvert:
          A  B  C  D  E  F  G
     A C: 1  -  A  -  -  -  -
     E B: 1  E  A  -  1  -  -
     D B: 1  E  A  E  2  -  -    Weight Balancing
     A D: E  E  A  E  4  -  -    Weight Balancing
     F G: E  E  A  E  4  1  F
     F C: E  E  E  E  6  E  F    Path Compression og Weight Balancing


     Resulterende skog:      E
                         / / | \ \ 
                        A B  C  D F
             		          |
                                  G