/**
 *   Løsning til eksamen i AlgMet, desember 2022, oppgave 1.
 *
 *   @file     EX_H22_1.TXT
 *   @author   Frode Haug, NTNU
 */



OPPGAVE A:
==========
          
    2-3-4 tre:                N
                         /         \
                       E             SU
                     /   \         /  |  \
                   AC   EHI      NN  ST   W



						Alle 3-noder kan vippes motsatt vei. 
    Red-Black tre:            N                Her er alle konsekvent høyre-rotert:
                         /         \
                       E             S
                     /   \         /  \\
                    /     \       /     U
                   A      H      N     / \
                    \\  // \\     \\  S   W
                     C  E   I      N   \\
                                        T





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

    "OBERSTDORF" sorteres vha. Quicksort.
    Oversikten/tabellen for hver rekursive sortering blir da:
    (NB: Partisjonselementet er skrevet med STOR bokstav,
         mens resten er skrevet med små bokstaver.)


                1  2  3  4  5  6  7  8  9 10
    Initielt:   O  B  E  R  S  T  D  O  R  F

                d  b  e  F  s  t  o  o  r  r
                d  b  E
                B  d
                            r  o  o  R  s  t
                            o  O  r
                                        s  T





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

    Nabomatrisen:    | A  B  C  D  E  F  G
                   --|--------------------
                   A | 0  0  0  0  0  0  1
                   B | 0  0  0  1  1  0  0
                   C | 0  0  0  1  0  1  1
                   D | 0  1  1  0  0  1  0
                   E | 0  1  0  0  0  1  0
                   F | 0  0  1  1  1  0  1
                   G | 1  0  1  0  0  1  0      (evt. 1 på diagonalen også)


    Dybde-først-søketreet når starter i D:   

                  .............
                  :  .........D
                  :  :       /
                  :  :      B
                  :  :     /
                  :  :    E
                  :  :   /
                  :  :..F..
                  :    /  :
                  :...C   :
                     /    :
                    G.....:
                   /
                  A