4. sada domácich zadaní

Najneskorší termín odovzdania: 15.3.2020 (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

Potomkovia so staršími súrodencami (3 body)

Do triedy Osoba z prednášky o stromoch pridajte metódu, ktorá vráti počet potomkov v rodostrome tejto osoby (o osobe v koreni rodostromu nevieme počet súrodencov, takže ju neuvažujeme), ktorí majú aspoň 𝑘 starších súrodencov. Predpokladáme, že deti osoby sú v jej zozname usporiadané podľa dátumu narodenia (prvé dieťa v zozname je najstaršie).

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 pocetPotomkovSoStarsimiSurodencami(int k) {
                // 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]]