Datenstrukturen beim Binärbaum?
(a) Baue so den Baum, der sich aus der Liste 1, 5, 9, 11, 23, 47, 55, 56, 99 ergibt auf.
(b) Wieviele Vergleiche brauchen wir bei der binären Suche nach 56 und 1 in diesem Baum?
(c) Wenn wir nun eine binäre Suche auf dem Binärbaum durchführen würden (also mal unter der Annahme, wir hätten ihn schon implementiert), mit wie vielen Baumelementen muss dann kein Vergleich durchgeführt werden, wenn ein Blatt durchsucht wird?
d) Als Tiefe eines Knotens bezeichnet man die Länge des Pfades von der Wurzel zu ihm und als Höhe des Baumes die Länge eines längsten Pfades (hier: Länge 4, vier Schritte bis zum untersten Knoten (=Blatt), der immer von der Wurzel zu einem Blatt laufen muss)
Ich bin bei den Fragen etwas aufgeschmissen, denn ich habe mich bei a) versucht (siehe Bildanhang), mir ist nur leider nicht klar, was jetzt nicht erlaubt ist oder welcher der beiden von mir skizzierten Bäume richtig ist oder ob man es ganz anders machen muss. Könnte mir bitte jemand helfen, der es richtig kann, damit ich es auch gut verstehen und lernen kann. Das fände ich wirklich toll!
Liebe Grüße, Sebastian
Die Frage d) war noch nicht fertig:
Bäume können für Suchvorgänge perfekt aufgebaut sein oder sehr ungünstig. Wie hoch ist minimal ein Binärbaum, wenn in ihm einschließllich der Wurzel 1000 Knoten untergebracht werden, wie hoch ist der Baum maximal, wie hoch könnte man ihn dann datentechnisch auch bezeichnen?
meine 2 Vorschläge für den Binärbaum a) - was ist richtig, oder beides falsch?
da die fragen leider aufeinander aufbauen, wäre es hilfreich zu wissen, ob ich a) richtig gelöst habe. falls a) richtig ist, würde ich zu b) folgendes sagen:
b) man benötigt jeweils 2 vergleiche
1 Antwort
Einfache kleine Übung. Allerdings fehlt noch etwas bei der Aufgabe. a) Beginnt mit 'Baue so' - da fehlt also einiges an Vorgeplänkel. (Wenn die Liste eine Einfügereihenfolge wäre, wäre das alles ziemlich witzlos).
Die Sache ist doch die: Wie soll der Baum konstruiert werden, nach welchen Regeln und Vorgaben. würde ich die sortierte Liste aus a als Einfügereihenfolge nutzen, so würde 1 zur Wurzel werden, 5 das rechte Kind, 9 deren rechtes Kind usw. .
Der Baum wäre entartet (zeichne es mal auf, es wird Dir für Aufgabenteil d) helfen). Es muß also vor der Aufgabe irgendeine weitere Information geben, denn wenn ich sage, baue so auf ... dann muß dieses so irgendwo definiert worden sein.
Und nur mit diesem so kann man dann auch sagen, ob Deine Lösung hinkommt.
------
Ich kann Dir gerne noch etwas zur d) mit auf den Weg geben, ein vollbesetzter Baum hat in der Tiefe T genaue 2^T Knoten (prüfen! nicht glauben!), somit bei Höhe h auch 2^h Blätter. Die Gesamtzahl der Knoten im Baum der Tiefe T (inkl. Blätter) ergibt sich dann als (2^(T+1))-1 (auch prüfen, überlege Dir warum das so ist). Die minimale Tiefe T ergibt sich dann unweigerlich aus diesem Zusammenhang.
super danke, dann zeichne ich den baum gleich einmal in der vorgegebenen reihenfolge auf, zumindest probiere ich es, aber ich fürchte das wird ein einzelner strang, da sie nach größe sortiert sind, deswegen dachte ich, ich solle einen günstigen baum zeichnen?
Vielleicht das hier als erweiterete Aufgabenstellung?
In unserer binären Suche (für die der Binärbaum ja optimiert werden soll) benötigen wir zu Beginn immer genau ein Element, den Median unserer Liste. Daher werden wir unserem Binärbaum zunächst auch mal genau dieses eine Element mitgeben. Unser binäre Suche Algorithmus vergleicht im ersten Schritt das gesuchte Element mit dem Median (also unserem ersten Baumelement), gibt es wieder, wenn sie übereinstimmen, geht zum Median der linken Teilliste, wenn das gefundene Element größer als das gesuchte ist und zum Median der rechten Teilliste, wenn das gefundene Element kleiner als das gesuchte ist. Wir brauchen also genau zwei Zeiger von unserem ersten Element (welches wir fortan entsprechend dem Baumnamen Wurzel nennen wollen), einen auf den Median der linken Teilliste (der kleiner als die Wurzel ist) und einen auf den Median der rechten Teilliste (der größer als die Wurzel ist):
Da wir unseren Algorithmus rekursiv definiert haben, werden wir immer nur für jedes Element (wir wollen es zukünftig mal Knoten nennen) zwei Zeiger auf die nächsten zwei Mediane brauchen, bis wir schließlich bei den untersten Elementen (die wir wieder entsprechend unserer Baumanalogie Blätter nennen wollen) ankommen.Wir haben also für jedes Element genau zwei Zeiger, sehen also auch schon, dass der Speicherbedarf unseres Baumes dem der doppelt verketteten Liste entspricht.
Aha! dann schaue mal auf d) zweiter Teil, wie hoch wird ein Baum denn maximal, wenn er total entartet und an welche andere Datenstruktur erinnert er Dich?
Das ist eben genau die Frage, was ich zeichen sollt. Gibt es eine Vorbedingung wie: Zeichne den binären Suchbaum der durch eien binäre Suche entstünde? Oder steht da, wie sähe ein optimaler Baum aus, oder ...
Wenn ich von der binären Suche ausginge, dann wäre in der Tat der Median der Liste (der Teillisten) jeweils die Wurzel des Baumes (Teilbaumes).
------------------
[1, 5, 9, 11, 23, 47, 55, 56, 99] n=9, Median wäre floor(9/2)=4 -> 23 auswählen (da wir ab 0 zählen)
[1, 5, 9, 11] - [23] - [47, 55, 56, 99] l/r Teilliste n=4, Median 2, ergo 3. Element auswählen:
[23]
/ \
[1, 5] - [9] - [11] [47, 55] - [56] - [99]
Nächster Schritt Median =1
[23]
/ \
/ \
[9] [56]
/ \ / \
[1] - [5] [11] [47] - [55] [99]
(Wobei 1 linker Nachfolger von 5, 47 linker Nachfolger von 55 - Ein Algorithmus wie die Binärsuche orientiert sich nicht an Symmetrieempfindungen ;-) ).
Ich zähle entgegen der Aufgabenstellung auch eine Tiefe von lediglich 3.
jetzt verstehe ich langsam ein bisschen mehr :) also der entartete baum wäre ja wie eine lange schlange (habe das bild dazu jetzt mehrfach versucht hochzuladen, dass hat nur leider nicht funktioniert, warum weiß ich gerade nicht
)
das heisst, dann wäre mein zuerst gezeichneter baum mit der 23 als wurzel oben richtig?
oder zählen sie die wurzel als 1 mit, dann wären es 4 aber wie sollte ich das begründen? tiefe des knotens wäre abhängig von der gesuchten zahl und höhe des baumes wäre der längste pfad, meiner meinung nach dann 3 oder, habe ich das flasch verstanden und die wurzel zählt extra?
Du nennst es Schlange, andere nennen es einfach verkettete Liste ;-). Und der Suchaufwand ist dann maximal n bzw. n/2 im Mittel.
Dein Baum mit der 23 als Wurzel ist fast richtig, wie gesagt, ein Algorithmus wie die Binärsuche ist 'stur' und arbeitet gleichartig, deswegen ist der rechte Nachfolger der 23 auch die 56, nicht die 55, siehe meine textuelle Darstellung.
Naja, bei der Suche mußt Du natürlich jeden Knoten bis zur Tiefe T anfassen, d.h. wenn ich eine Zahl in Tiefe T finde, habe ich natürlich die Tiefen 0..T betrachtet und ich brauche daher T+1 Schritte. Wie gesagt, der normalen Definition nach, die auch im Text steht, ist die Tiefe die Zahl der 'Kanten' auf dem Pfad, die ist immer um 1 niedriger als die Zahl der Knoten.
--------
Wie dem auch sei, ich muß, wenn ich mir jetzt Aufgabenteil b) anschaue, die Zahl der betrachteten Knoten anschauen - die Frage ist, ob das der Aufgabe genügt, denn eigentlich habe ich für jeden Knoten ohne Treffer 2 Vergleiche, für den mit Fund nur einen.
c) ist ein bisschen verquer, ich bin nicht sicher, was gefragt ist. So wie ich die Frage verstehe, wäre das #Knoten-1. Gut möglich, daß das aber anders gemeint ist.
super, ich zähle auch nur eine tiefe von 3, dann habe ich das zumindest schon mal verstanden :) bei d) wüsste ich gerne, ob höhe und tiefe die gleiche bedeutung haben? falls, ja, hätte ein maximaler also ungünstiger binärbaum eine höhe von 999 und ein günstiger also minimaler, gibt es da vielleicht eine formel, vielleicht so etwas wie (2 hoch x) - 1 = 1000?
er hat sich vertan, die tiefe ist 3, wir haben die info gerade bekommen
aber der unterschied zwischen tiefe und höhe? ich habe bei wiki geguckt, dort steht, dass die höhe die maximale tiefe des baumes darstellt (wenn ich das richtig verstanden habe) aber dann wäre die fragestellung meines lehreres falsch, oder?
das kann man mit der erklärung und zeichnung super für a) verstehen, danke
super, jetzt kommt langsam die erleuchtung, hoffe ich, ich versuche es mal gesamt zu lösen und dann zu schicken
ich habe die 4 teilaufgaben mal versucht zu lösen, sie sind hier hinterlegt, aber 2 sachen sind mir noch unklar, die sind farblich markiert: https://app.box.com/s/s0vkll4npqcohdftahcyo3gj5194lm63
bitte unbedingt einmal drüber gucken, das wäre riesig nett, denn ich komme sonst nicht weiter
H ist Tmax, oder Tmax+1, je nach Definition. Die zweite Definition hat einen Vorteil:
Um ein Blatt in Tmax zu erreichen, muß ich Tmax innere Knoten besuchen, muß ich das Blatt auch prüfen (z.B: bei Suche), dann fasse ich Tmax+1=h Knoten an.
Weiterer Vorteil, ein Baum der Höhe h=0 wäre leer, während h=1 nur die Wurzel enthält, die in Tiefe 0 liegt.
Aber das ist nur eien Offsetverschiebung aus Bequemlichkeit, die Zusammenhänge als solches ändern sich dadurch nicht.
Okay, Du hast Dir soweit Mühe gegeben, schaue wir uns b) an, ich mache lookup(1):
Ist 1==23? nein, ist 1<23 ja (linken Nachfolger nehmen)
Ist 1==9? Nein, ist 1<9 Ja (links)
Ist 1==5? Nein, ist 1<5 Ja (links)
ist 1==1? Ja -> gefunden, zurückgeben
------
Die 1 liegt auf Tiefe T=3, ich schaue mir genau T innere Knoten an, wobei ich eigentlich 2 Vergleiche benötigt, sowie ein Vergleich im Blatt. (Alternativ: innerer Knoten, der den Wert trägt). Verallgemeinert: 2T+1 Vergleiche, oder 2(T+1)-1.
----------------------------------------------
Die c) ist etwas komisch, wenn ich ein Blatt durchsuche, durchsuche ich nur dieses, also fasse ich ja auch nur diesen einen Knoten an. Wenn die Frage allerdings wäre, wieviel Knoten ich anfasse um zu einem Blatt zu gelangen, dann sind wir wieder bei den 2T Inneren Knoten + Blatt, also können wir Gesamtzahl(Knoten)-2T-1 ignoerieren.
--------------------------------------
Zur d): Ein Baum maximaler Höhe entsteht dann, wenn alle inneren Knoten nur rechte (oder nur linke) Nachfolger haben, die Höhe des Baumes entspricht dann (je nach Definition) genau der Gesamtzahl der Elemente, oder Gesamtzahl der Elemente -1. (Hier haben wir wieder die Offsetverschiebung je nach Bedarf)
Ich werde jetzt aus Bequemlichkeit auch folgende Definition verwenden ein Baum mit Tiefe Tmax besitzt eine Höhe von Tmax+1, es macht die Betrachtung etwas einfacher.
Ein Baum nur aus der Wurzel hat 2^0=1 Blätter (die Wurzel ohne Nachfolger) und besitzt (2^H)-1 Knoten (2^1)-1=1. Ein Baum aus Wurzel und Nachfolgern besitzt 2^1 Blätter, auf Tiefe 1, jedoch besitzt er 3 Knoten, was zufällig (2^2)-1 entspricht, also (2^H)-1. (Denkst Du noch daran, daß wir H=Tmax+1 definiert haben?) Wieder eine Ebene mehr und wir haben 2^2 Blätter und 7 Knoten (2^3)-1.
Ich denke was leicht einzusehen ist:
Wenn ich eine vollbesetze Ebene aus Blättern habe, und eine weitere Ebene anhänge, dann wird aus jedem ehemaligen Blatt ein innerer Knoten, dessen beide Nachfolger nun Blätter sind. Steigt Tmax also um 1 (oder H), dann verdoppelt sich die Blattzahl.
Die Knotenzahl erhalte ich wenn ich für eine Höhe (Tiefe) die Potenzen aufsummiere, also 2^0(Baumwurzel),2^1(Tiefe 1),..,2^t. Das ist dann aber (2^(t+1))-1 oder eben bei H=t+1 (2^H)-1. Erinnere Dich zurück, das ist bequemerweise auch ein Maß für die Anzahl der Vergleiche, um einen Knoten in Tiefe t ausgewertet zu haben. Habe ferner im Hinterkopf, daß wir die ganze Zeit von einem voll besetzen Baum sprechen.
Wenn ich also (2^10)-1=1023 Elemente perfekt anordne, hat der ein Höhe von 10, die Blätter liegen in Tmax=9 und es gibt 512 Blätter. Wir erreichen ein Blatt nach dem Besuch von 9 inneren Knoten, und prüfen ingesamt 10 Knoten, wobei wir 2 Vergleiche je innerem Knoten udn nur 1 fürs Blatt aufwenden müssen.
--------------------------------------------
Allgemein, Ein Baum der Höhe H kann bis zu (2^H)-1 Knoten beherbergen, wenn wir also n Elemente unterbringen wollen ergibt sich: (2^H)-1=n 2^H=n+1 H=log_2(n+1).
Die Konsequenz: Ein Baum der 16 Mio Elemente berherbergt hat eine Höhe von 24, bei 4Milliarden 32. Vergleiche das mit einer linearen Suche in einer (ungeordneten) Liste.
achso, es geht beides, entweder Tmax als Baumhöhe oder Tmax+1 je nachdem ob ich die wurzel als 1 oder 0 definiere?
das bedeutet es geht beides entweder ist Tmax die Gesamthöhe des Baumes oder Tmax +1 je nachdem ob die Wurzel als 1 oder 0 definiert ist, ist das so richtig?
soll ich schreiben, ich baue den baum so, dass ich mit dem median beginne (das wäre das rechte bild)
ich baue den baum so, dass ich die unteren blätter zuerst einzeichne (linkes bild)
das habe ich nicht verstanden, ich verstehe, dass das hier für alle sehr einfach ist, aber es ist meine 4. stunde informatik und ich finde es noch nicht so leicht zu durchschauen - deswegen frage ich ja hier. wäre also riesig nett, wenn sich jemand kurz zeit nehmen könnte, mir hier weiter zu helfen, denn ich möchte nicht mit meinem brett vor dem kopf schlafen gehen, sondern gerne etwas verstanden und gelernt haben :) es fehlt also noch etwas bei a) was könnte es sein? ein text? ich habe leider keine ahnung, daher bitte ich um unterstützung ... die folgenden b) bis d) sind mir leider noch viel unklarer
könnten wir das vielleicht bitte zusammen gerade lösen?