Untitled

Aufgabe 1:

        a) n log n

        b) n²

        c) n²

        d) n² (da auch Quicksort basiert)

        e)      15      2       43      17      4       8       47

                SW: 5

                8       2       43      17      4       15      47

                SW: 3

                8       2       15      17      4       43      47

                SW: 1

                2       4       8       15      17      43      47

        f) Formel (3*i)+1, Start bei 1, i vorheriger Wert -->   1,3,13,40,(121). 121 ist schon zu groß.

       

Aufgabe 2:

        a) Maximale Abstand der Knoten bis zur Wurzel.

        Hat man einen Baum mit einem Knoten dann ist die Tiefe 1,

        hat man zwei Knoten, so ist die Tiefe 2.

        Hat man einen Baum mit 5 Ebenen (d.h. Ebene 0 ist die Wurzel), so ist die Tiefe 6!

        Tiefe = Anzahl aller Knoten incl. Wurzel auf dem maximalen Weg.

       

        b)

        public int depth() {

                return depth(root);

        }

 

        public int depth(TreeNode<E> node) {

                int linkeTiefe = 0;

                int rechteTiefe = 0;

 

                if (node.left != null) {

                        linkeTiefe = depth(node.left);

                }

                if (node.right != null) {

                        rechteTiefe = depth(node.right);

                }

                if (linkeTiefe >= rechteTiefe) {

                        return ++linkeTiefe;

                } else {

                        return ++rechteTiefe;

                }

        }

       

Aufgabe 3:

        a) Der Baum muss 10 Ebenen haben, da 2^10=1024 > 1000. 10 Ebenen bedeutet eine Tiefe von 11.

        b) Tiefe 5 bedeutet, das der Baum 4 Ebenen hat -> (2^4)-1 = 15 Werte.

        c) Da die Werte absteigend eingefügt werden, degeneriert der Baum zu einer Liste, die von der Wurzel aus

        immer nach links wächst. Dieser "Baum" hätte eine Tiefe von 1000.

        d) Strategie: sich einen vollständigen binären Baum mit leeren Knoten aufmalen

        und dort dann z.B. den rechten Teilbaum abdecken. Jetzt sieht man nur noch die Wurzel und den linken Teilbaum.

        Zählt man nun die Anzahl der Knoten im linken Teilbaum, so erhält man in diesem Beispiel 7 Knoten.

        Jetzt weiß man, dass in die Wurzel der Wert aus der einzufügenden Menge muss, für den es 7 kleinere Werte gibt.

        Im Beispiel wäre das die 8.

        Lösung: 8|4|12|2|6|10|13|1|3|5|7|9|11

        e) Der symmetrische Nachfolger der 8 ist die 9

                Man ersetzt die 8 durch die 9. Der Baum ist nun nicht mehr vollständig, sonder nur noch voll

               

Aufgabe 4:

        a) Die Methode genügt den Bedingung nicht. Durch die Verwendung der Randomfunktion kommt, wenn man das gleiche

        Objekt zweimal hasht, jeweils ein andere Hashwert heraus. Bei im SInne von equals gleichen Objekten kann nur durch

        Zufall der selbe Hashwert herauskommen. --> totaler Bullshit die Hashfunktion

        b) HashSet<Person> set = new HashSet<Person>();

                for (Person p : typen) {

                        if (!set.contains(p)) {

                                set.add(p);

                        }

                }

               

        c)      Person donald = new Person();

                donald.fname="Donald";

                donald.lname="Duck"

                if (set.contains(donald)) {

                        System.out.println("Donald ist drin");

                } else {

                        System.out.println("Donald ist nicht drin");

                }

               

                Ich erwarte, dass Donald nicht im Hashset ist? oO

       

        d)public int hashCode() {

                return fname.hashCode()+lname.hashCode();

        }