4. sada domácich zadaní

Najneskorší termín odovzdania: 19.3.2017 (nedeľa) o 21:00
Odovzdávané súbory: Osoba.java, Uzol.java

Doplňujúce požiadavky:

  • riešenia, ktoré nebude možné skompilovať (t.j. riešenia so syntaktickými chybami) nebudú hodnotené,
  • zdrojový kód správne naformátujte (CTRL+SHIFT+F),
  • komentovaný zdrojový kód

Jedináčikovia v generácii (3 body)

V triede Osoba implementujte metódu pocetJedinacikovVGeneracii, ktorá vráti počet všetkých potomkov tejto osoby, ktorí sú v zadanej generácii potomkov tejto osoby a zároveň sú jedináčikovia (ich rodič má len jedno dieťa). Pri číslovaní generácií platí, že generáciu 1 tvoria deti osoby, generáciu 2 vnúčatá osoby, generáciu 3 pravnúčatá osoby, atď.

import java.util.*;

public class Osoba {
        private String meno;
        private List<Osoba> deti = new ArrayList<Osoba>();

        public Osoba(String meno) {
                this.meno = meno;
        }

        public void pridajDieta(Osoba dieta) {
                deti.add(dieta);
        }

        public int pocetJedinacikovVGeneracii(int generacia) {
                // Riesenie?
        }
}
[$[Get Code]]

Vyvážené stromy? (3 body)

Do triedy Uzol pridajte metódu jeVyvazeny, ktorá vráti, či strom, ktorého koreňom je daný uzol, je uzlovo vyvážený. Povieme, že strom je uzlovo vyvážený, ak (1) počet prvkov uložených v ľavom a pravom podstrome sa líši nanajvýš o 1 a (2) ľavý a pravý podstrom daného uzla sú vyvážené.

public boolean jeVyvazeny();
[$[Get Code]]

Bonus (pre fajnšmekrov): +3 body za riešenie bežiace v čase O(n), kde n je počet uzlov stromu, ktorého koreňom je uzol, na ktorým túto metódu voláme (Rada: vytvorte inú pomocnú privátmu metódu alebo metódy, ktorá vám umožnia úlohu vyriešiť v uvedenom čase). Pre udelenie bonusu sa vyžaduje argumentácia, prečo má uvedený algoritmus časovú zložitosť O(n).

Binárne vyhľadávacie stromy (2 body)

Do triedy Uzol pridajte statickú metódu vytvorBVS, ktorá vráti referenciu na novovytvorený koreňový uzol binárneho vyhľadávacieho stromu naplného zadanými hodnotami. Vytvorený binárny strom musí mať zároveň minimálnu možnú výšku.

public static Uzol vytvorBVS(Set<Integer> hodnoty);
[$[Get Code]]

Trieda Uzol:

public class Uzol {
        private int hodnota;
        private Uzol lavy;
        private Uzol pravy;

        public Uzol(int hodnota, Uzol lavy, Uzol pravy) {
                this.hodnota = hodnota;
                this.lavy = lavy;
                this.pravy = pravy;
        }

        public int getHodnota() {
                return hodnota;
        }

        public void setHodnota(int hodnota) {
                this.hodnota = hodnota;
        }

        @Override
        public String toString() {
                StringBuilder sb = new StringBuilder();
                if (lavy != null)
                        sb.append("(" + lavy.toString() + ") ");

                sb.append(hodnota);

                if (pravy != null)
                        sb.append(" (" + pravy.toString() + ")");

                return sb.toString();
        }
}
[$[Get Code]]