UL/FRI/VSP-RI/OAPS1/Vaje/2006-01-12

Urejen seznam

Želimo imeti objekte urejene po vrstnem redu.

Potrebujemo metode

• dodaj

moramo redefinirati, ker dodaja na napačno mesto (ne po urejenosti)

• obstaja

ni potrebno redefinirati

• izloci

ni potrebno redefinirati

• toString

ni potrebno redefinirati

public class SeznamP<T extends Element> extends Seznam<T>
  public SeznamP(String ime) {  //konstruktor - za neko ime naredi seznam
    super(ime);
  }
 
  public void dodaj(T el) {          //redefinicija dodajanja
    Clen nov = new Clen(el);         //naredimo nov objekt vsebujoc element
    if(zacetek == null || el.manjsi(zacetek.element)) {   //ce je seznam prazen ali
      nov.naprej = zacetek;                               //je element manjsi od prvega
      zacetek = nov;                                      //vrinemo element na zacetek
    }
    else {                              //drugace poiscemo pravo mesto za vstavljanje
      Clen pom = zacetek;               //naredimo clen, ki kaze na zacetek
      while(pom.naprej != null && pom.naprej.element.manjsi(el))  //dokler ni na koncu seznama
        pom = pom.naprej;                     //ali ne najde manjsega  -> naj se pomika naprej
      nov.naprej = pom.naprej;                 
      pom.naprej = nov;             //vstavi novi element
    }
    velikost++;
  }
}

class TestSeznam {
  public static void main(String[] args) {
    //SeznamP<String> s = new SeznamP<String>("S"); //napaka, string ni tipa element
    SeznamP<Student> s = new SeznamP<Student>("S");
    s.dodaj(new Student(...));
 
    System.out.println(s);
  }
}

Drevesa

Izpolnjeno drevo

drevo, ki nima praznih mest

indeksi: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11
         7, 3, 2, 4, 1, 5, 8, 9, 6, 5,  1,  9

Popolnoma izravnano drevo

predstavnik uravnoteženih dreves

7 3 2 4 1 5 8 9 6 5 1 9
# """"""""""" """""""""
             7
            / \

3 2 4 1 5 8   9 6 5 1 9
# """"" """   # """ """
       3           9
      / \         / \ 

2 4 1    5 8    6 5   1 9
# " "    # "    # "   # "
   2      5      6     1
  / \    /      /     /
 4   1  8      5     9

Dvojiško iskalno drevo

(BST - binary search tree)

7 3 2 4 1 5 8 9 6 5 1 9

      7
     / \
    3   8
   / \   \
  2   4   92
 /     \
12      52
         \
          6

Brisanje

• B0

isto

• B1

      7
     / \
    3   8
   / \   \
  2   4   92
 /     \
1       52
         \
          6

• B6

      7
     / \
    3   8
   / \   \
  2   4   92
 /     \
1       52

• B4

      7
     / \
    3   8
   / \   \
  2   52  92
 /     
1       

• B7

poiščemo največji element v levem poddrevesu (gremo 1x levo, potem desno dokler se da)

      52
     / \
    3   8
   /     \
  2       92
 /     
1       

• B5

ko brišemo petko z indeksom brišemo samo 1 element iz indeksa

      5
     / \
    3   8
   /     \
  2       92
 /     
1   

• B5

      3
     / \
    2   8
   /     \
  1       92

Naloga iz izpita

Določi zaporedje elementov od 1 do 10 tako, da bo algoritem za gradnjo popolnoma izravnanega drevesa in algoritem za gradnjo binarnega iskalnega drevesa izgradil natanko isto drevo.

Za PID velja, da za enako št. elementov vedno zgradi enako strukturo Da bo BST morajo biti vsa na levi manjša (6) in vsa na desni večja (4)

1 2 3 4 5 6 7 8 9 10

      __6__
     /     \
    3       9
   / \     / \ 
  2   5   8  10
 /   /   /
1   4   7

6 3 2 1 5 4 9 8 7 10
    ___ ___   ___ __
  _________ ________

Obhodi

Izpiši drevo iz prejšnje naloge z obhodom.

Nivojski obhod

po nivojih

6 3 9 2 5 8 10 1 4 7

Premi obhod

koren - levi - desni

6 3 2 1 5 4 9 8 7 10

Vmesni obhod

levi - koren - desni

1 2 3 4 5 6 7 8 9 10

Obratni obhod

levi - desni - koren

1 2 4 5 3 7 8 10 9 6