asdfasdf

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

                8       2       15      17      4       43      47

        f) Formele (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