Aufgabe 1: a) n log n b) n - Anonymous - m3f1a1cd7

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();
        }