- 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
