Oppgavesett 8 - Balanserte trær

Oppgavene blir tema på øvingen fredag 23. mars. Innleveringen skal bestå av en pdf-fil med korte kommentarer og dokumentasjon (utskrifter etc.). Legg også ved godt dokumenterte java filer. Alt pakkes i en zipfil, med navn assignment08-*.zip der * er etternavnene til gruppemedlemmene. Javafilene skal tilhøre en pakke med navn package assignment08.

Fristen for innlevering er tirsdag 20.mars 09:00.

Alle oppgavene dreier seg om ulike aspekter av binære søketrær, og spesielt AVL-balanserte trær. Dere kan ta utgangspunkt i klassen Bst som vi programmerte i forelesning nr 13.

Oppgave 1

A

Hvorfor er et såkalt balansert søketre en viktig og mye brukt datastruktur?

B

Forklar hva som menes med et AVL-balansert tre. Gi et eksempel på et tre som oppfyller AVL kravene, og ett som ikke gjør det, inkludert forklaringer. Treet skal ha en høyde på min. 4 (dvs. min. 5 nivåer inkl. rota).

C

Ved innsetting av en node i et AVL-tre kan balansen ødelegges. Forklar i hvilke tilfeller dette kan skje, og hvordan man kan rebalansere treet. Bruk rikelig med figurer.

D

                   B
                 /   \
                /     \
               A       D
                     /   \
                    /     \
            	   C       E

Sett inn en node med verdi 'F' dette treet. Forklar hvorfor treet etter innsettingen ikke er AVL-balansert. Foreta en reparasjon av treet etter innsettingen. Tegn/kommenter hvert trinn i prosessen.

Oppgave 2

*A

Implementer en metode void print(Node root) i class Bst, som skriver ut et tre til System.out som en grafisk figur (f.eks. noe lignende som i oppgave 1D). Dokumenter at klassen virker.

B

Legg til en int bf i class Node som inneholder nodens balansefaktor. Ved hver innsetting av en node skal nodenes balansefaktor oppdateres.

Forklar hvordan du tror dette kan gjøres på en effektiv måte (bruk gjerne figurer og eksempler), og beskriv deretter metoden med presis pseudokode.

*C

Implementer metoden void insert(Node n, Node root) i class Bst som setter inn en node og oppdaterer samtidig balansefaktorene. Legg til ekstra variable og metoder i Node hvis du mener det er hensiktsmessig. Dokumenter at klassen virker.

*D

Implementer metoden Node rightSingleRotation(Node root) i class Bst som regner foretar en enkel rotasjon av subtreet med rotnoden root som er høyre-høyre skjevt. Metoden returner rota i det roterte subtreet. Dokumenter at klassen virker.

Oppgave 3

Vi har følgende binærtre:

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

Etter en såkalt speiling ser treet ut slik:

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

Implementer en metoden void mirror(Node root) i class Bst, som speiler treet. Dokumenter at klassen virker.