Ich habe eine Frage zu Übungsblatt 4, Aufgabe 1.3: In der hochgeladenen Lösung steht, dass (i) funktioniert, aber ich hatte beim Binary Search Tree den Ablauf so verstanden, dass das erste Element, das man zum Aufteilen des Arrays benutzt, in der Mitte des Arrays liegt. Dann kann das ja nicht 998 sein, wenn links davon 7 weitere aufgerufen werden, aber rechts davon maximal 2 weitere vorhanden sind?
Hi Sarah,
entschuldige die späte Rückmeldung, da ich seit Weihnachten bis heute im Urlaub war.
Wenn ich Deine Aussage richtig verstehe, vermute ich, dass Du annimmst, dass die gegebenen Binary Trees in Höhe balanciert sein müssen. Das ist für "einfache" Binary Trees (vgl. AVL Trees) nicht erforderlich, da die Binary Search Tree Property nur erfordert, dass
"For each non-leaf node x of a binary tree the following binary search tree property has to be satisfied: (1) for every node y in the left subtree of x: y.key ≤ x.key; and (2) for every
node y in the right subtree of x: y.key ≥ x.key;" (vgl. L8 Binary Search Tree, Slide 19)
Unabhängig davon macht die Aufgabenstellung auch keine Aussage über die Struktur der Bäume, da nur erfragt wird, ob die gegebene Reihenfolge möglich sein kann. Es könnte also sein, dass die gegebenen Bäume auch AVL Trees (sprich in Höhe der Sub-Trees jeder Node balanciert) sind.
Ich hoffe das klärt Deine Frage! Bitte gebe Bescheid, falls Du weitere Fragen hierzu hast.
LG
Fabian