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



OPPGAVE A:
==========
                   notukhost
    H: 4   I: 5    kotunhost    'K' vandrer forbi 'N'
    H: 4   I: 6    khtunoost    'H' vandrer forbi 'O'
    H: 4   I: 7    khounotst    'O' vandrer forbi 'T'
    H: 4   I: 8    khosnotut    'S' vandrer forbi 'U'
    H: 4   I: 9    khosnotut        (ingenting skjer)
    H: 1   I: 2    hkosnotut    'H' vandrer forbi 'K'
    H: 1   I: 3    hkosnotut        (ingenting skjer)
    H: 1   I: 4    hkosnotut        (ingenting skjer)
    H: 1   I: 5    hknosotut    'N' vandrer forbi 'S' og 'O'
    H: 1   I: 6    hknoostut    'O' vandrer forbi 'S'
    H: 1   I: 7    hknoostut        (ingenting skjer)
    H: 1   I: 8    hknoostut        (ingenting skjer)
    H: 1   I: 9    hknoosttu    'T' vandrer forbi 'U'





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

    "NOTUKHOST satt inn i:

    1)  Heap:      U T O T K H O N S


    2)  Binært søketre:        N
                             /   \
                           K       O
                          /          \
                         H            T
                                    /   \
                                    O    U
                                    \   /
                                     S T

 
    3)  2-3-4 tre:            O T
                           /   |   \
                         HKN   OS   TU


    4)  Red-Black tre:         O
                           /      \\     (eller OT, OS og TU rotert andre veien)
                         K          T
                       // \\      /   \
                      H     N    O     T
                                  \\    \\
                                    S     U





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

    Når "J" fjernes:
        - "J" har ingen høyre barn, derfor er
        - den FØRSTE setningen med  "if (!fjernes->right) ....."  aktuell.

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

                             G
                          /     \
                       ....       I
                                /
                               H

    Når "K" 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 ("L")
          erstatte den som fjernes ("K").

        - Treet etter at "K" er fjernet:

                             L
                          /     \
                        G         O
                      /   \     /   \
                    ...   ...  M    ...
                                \
                                 N


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

        - Treet under "K" etter at "O" er fjernet:

                             K
                          /     \
                       ....       P
                                /   \
                               L    ...
                                \
                                ...