Cvičenia: 4. týždeň

Ciele cvičení:

  • vedieť, ako v programoch uložiť a reprezentovať hierarchické údaje a štruktúry,
  • vedieť riešiť jednoduché úlohy s hierarchickými údajovými štruktúrami,
  • zoznámiť sa s aritmetickými stromami,
  • poznať binárne vyhľadávacie stromy a základné operácie nad nimi (test na prítomnosť hodnoty, pridanie a odobranie hodnoty),
  • vedieť analyzovať časovú zložitosť jednotlivých algoritmov.

Strom potomkov

  • Do triedy Osoba z prednášky pridajte metódu pocetGeneracii, ktorá vráti počet generácií potomkov danej osoby.
public int pocetGeneracii();
[$[Get Code]]
  • Do triedy Osoba z prednášky pridajte metódu pridajDoZoznamu, ktorá uloží všetky osoby stromu potomkov danej osoby do zoznamu osôb.
public void pridajDoZoznamu(List<Osoba> zoznam);
[$[Get Code]]

Binárne stromy

  • Nakreslite nejaký binárny strom s 10 uzlami s číselnými hodnotami v uzloch. Popíšte tento strom z hľadiska "stromových" parametrov (výška, koreň, listy, vnútorné uzly, ...).
  • Do triedy Uzol (z prednášky) pridajte statickú metódu, ktorá vráti referenciu na koreň stromu, ktorého opis je v zadanom reťazci.
public static Uzol stromZRetazca(String opisStromu)
[$[Get Code]]
Opis stromu je reťazec tvaru: (L) h (P), kde L je opis ľavého podstromu, P je opis pravého podstromu a h je hodnota v koreni stromu. Reťazec ((2) 7 ((5) 6 (11))) 2 (5 ((4) 9)) reprezentuje strom:
  • Do triedy Uzol (z prednášky) pridajte metódy na výpočet minimálnej uloženej hodnoty, počtu uložených hodnôt a výšku stromu.

Binárne stromy II

  • Nakreslite nejaký binárny strom s 10 uzlami s číselnými hodnotami v uzloch. Popíšte tento strom z hľadiska "stromových" parametrov (výška, koreň, listy, vnútorné uzly, ...). Vypíšte postupnosť spracovania hodnôt (uzlov) pri preorder, inorder a postorder prechode týmto stromom. Napíšte metódy, ktoré jednotlivé prechody realizujú.
  • Napíšte metódu, ktorá pre zadaný uzol vráti súčet hodnôt uložených v uzloch stromu, ktorého je zadaný uzol koreňom.
  • Napíšte metódu, ktorá pre zadaný uzol vráti výšku stromu, ktorého je zadaný uzol koreňom.
  • Predpokladajte, že poznáte postupnosť inorder a preorder spracovania hodnôt v binárnom strome, ktorý v každom uzle uchováva inú hodnotu. Navrhnite postup, ako zo znalosti týchto 2 postupností zrekonštruovať binárny strom. pre náročnejších: Ako by ste túto úlohu riešili pri znalosti postupností postorder a preorder prechodu?
  • Aký je minimálny a maximálny počet uzlov stromu s výškou h? Svoje tvrdenie dokážte (formálny dôkaz matematickou indukciou na výšku stromu h).
    • Dôsledok: Aká je minimálna možná výška a aká je maximálna možná výška binárneho stromu s n uzlami?

Binárne vyhľadávacie stromy

  • Pre náhodné vytvorenú postupnosť 10 čísel nakreslite binárny strom uchovávajúci tieto hodnoty, ktorý je navyše aj binárnym vyhľadávacím stromom.
  • Odsimulujte algoritmy na testovanie prítomnosti hodnoty, pridávanie a odoberanie hodnoty.
  • Navrhnite (a implementujte) algoritmus na overenie, či nejaký binárny strom je binárny vyhľadávací strom.
  • Akú postupnosť hodnôt dostaneme pri inorder prechode binárneho vyhľadávacieho stromu a prečo?
  • Napíšte metódu, ktorá v binárnom vyhľadávacom strome nájde minimálnu hodnotu.
  • Vyskúšajte http://people.ksp.sk/~kuko/bak/big/

Aritmetické stromy

  • Pre zadaný aritmetický výraz nakreslite prislúchajúci strom tohto výrazu.
  • Čo je výsledkom postupnosti inorder (postorder) prechodu tohto stromu?
    • Rozdiskutujte zápis výrazov v postfixovej notácii.
  • Do triedy Vyraz pridajte metódy na:
    • na výpis výrazu v postfixovej notácii
    • vyhodnotenie výrazu
  • Pre fajnšmekrov: Rozšírte triedu Vyraz o podporu premenných vo výraze.
/**
 * Trieda reprezentujuca aritmeticky vyraz
 */
public class Vyraz {

        /**
         * Rozhranie, ktore implementuju vsetky uzly aritmetickeho stromu
         */
        private interface Clen {
                @Override
                public String toString();
        }

        /**
         * Trieda implementujuca uzol stromu aritmetickeho stromu, ktory
         * reprezentuje binarnu operaciu
         */
        private static class BinarnaOperacia implements Clen {
                private char operator;
                private Clen lavyPodvyraz;
                private Clen pravyPodvyraz;

                public BinarnaOperacia(char operator, Clen lavy, Clen pravy) {
                        this.operator = operator;
                        this.lavyPodvyraz = lavy;
                        this.pravyPodvyraz = pravy;
                }

                @Override
                public String toString() {
                        return "(" + lavyPodvyraz.toString() + operator
                                        + pravyPodvyraz.toString() + ")";
                }
        }

        /**
         * Trieda implementujuca uzol aritmetickeho stromu, ktory reprezentuje
         * konstantu
         */
        private static class Hodnota implements Clen {
                private double hodnota;

                public Hodnota(double hodnota) {
                        this.hodnota = hodnota;
                }

                @Override
                public String toString() {
                        return Double.toString(hodnota);
                }
        }

        /**
         * Symboly operacii od najnizsej priority po najvyssiu
         */
        private static final String SYMBOLY_OPERACII = "+-*/";

        /**
         * Prevedie zadany vyraz do aritmetickeho stromu
         *
         * @param vyraz
         *            vyraz, ktory sa ma parsovat
         * @return referencia na koren aritmetickeho stromu
         */
        private static Clen prevedNaStrom(String vyraz) {
                // Odstranime zbytocne medzery
                vyraz = vyraz.trim();

                // Najdeme operator s najnizsou prioritou, ktory nie je v zatvorkach
                int operatorIdx = Integer.MAX_VALUE;
                int operatorPoz = -1;
                int pocitadloZatvoriek = 0;

                for (int i = 0; i < vyraz.length(); i++) {
                        char znak = vyraz.charAt(i);

                        if (znak == '(')
                                pocitadloZatvoriek++;

                        if (znak == ')')
                                pocitadloZatvoriek--;

                        int priorita = SYMBOLY_OPERACII.indexOf(znak);
                        if ((priorita != -1) && (pocitadloZatvoriek == 0) && (i > 0)) {
                                if (priorita < operatorIdx) {
                                        operatorIdx = priorita;
                                        operatorPoz = i;
                                }
                        }
                }

                // Rozdelime vyraz na podvyrazy
                if (operatorPoz != -1) {
                        return new BinarnaOperacia(SYMBOLY_OPERACII.charAt(operatorIdx),
                                        prevedNaStrom(vyraz.substring(0, operatorPoz)),
                                        prevedNaStrom(vyraz.substring(operatorPoz + 1)));
                }

                // Poznamka: Ak sme nenasli operator, tak je to alebo konstanta, alebo
                // cely vyraz je ozatvorkovany

                // Ak je cely vyraz ozatvorkovany, tak nechame rozparsovat jeho vnutornu
                // cast
                if ((vyraz.charAt(0) == '(')
                                && (vyraz.charAt(vyraz.length() - 1) == ')'))
                        return prevedNaStrom(vyraz.substring(1, vyraz.length() - 1));

                // Ak sme tu, tak to musi byt cislo
                try {
                        return new Hodnota(Double.parseDouble(vyraz));
                } catch (NumberFormatException e) {
                        throw new RuntimeException(
                                        "Zadany vyraz nie je korektny aritmeticky vyraz");
                }
        }

        /**
         * Koren aritmetickeho stromu vyrazu
         */
        private Clen koren;

        /**
         * Skontruuje novy aritmeticky vyraz
         *
         * @param vyraz
         *            retazec s aritmetickym vyrazom
         */
        public Vyraz(String vyraz) {
                koren = prevedNaStrom(vyraz);
        }

        @Override
        public String toString() {
                return koren.toString();
        }

        public static void main(String[] args) {
                Vyraz v = new Vyraz("(-3)+6/2+3*2");
                System.out.println(v);
        }
}
[$[Get Code]]

Pre E(xtra) skupinu:

  • Formálne (=matematicky, napr. priamy dôkaz) dokážte:
    • Ak limn→∞ f(n)/g(n) = c, kde c je z R, potom f(n) = O(g(n))
  • Ukážte, že predošlá implikácia nemôže byť zosilnená na ekvivalenciu tak, že skonštruujete algoritmus, ktorého časová zložitosť v najhoršom prípade na vstupe veľkosti n je taká funkcia T(n), že T(n) = O(g(n)), ale neexistuje c z R také, že limn→∞ T(n)/g(n) = c
  • Preskúmajte princípy a základné myšlienky samovyvažovacích binárnych vyhľadávacích stromov.