Ich mach mal den Anfang für die nächsten zwei Wochen P3 ;)

Und zwar habe ich da zu Aufgabe 1 folgende Frage:
Was itst ein links-vollständiger Binärbaum und wie ist dessen Arraydarstellung zu verstehen [img]http://www.sternenvolk.de/symb/26.gif[/img]

Edit: Google hat doch glatt eine Seite mit links-vollständig aufgetan :) ist die Array darstellung so zu verstehen, dass zuerst die Wurzel kommt, dann die beiden Knoten in Ebene 1, dann die 4 in Ebene 2 etc ?

Links-vollständig bedeutet, dass ein Baum der Höhe h bis zur Höhe h-1 vollständig, d.h. jeder Knoten hat zwei Söhne, sein muss.
Die Knoten der Höhe h liegen so weit links wie möglich. Wenn also ein Knoten der Höhe h keinen linken Sohn hat, kann er auch keinen rechten Sohn haben.
So ist außerdem gewährleistet, dass es keine Löcher im Baum gibt.

ui, es geht wieder los ;)

kann nur zustimmen, in der vorlesung wurde nur eine solche array-darstellung für bäume eingeführt (seite 26, folie I-51),

über links-vollständig steht auf seite 33, folie I-65 was

Schön, wieder was zum nachlesen :)

und gleich die nächste Frage:

Angenommen ich habe einen 4-Wege-Suchbaum und habe bisher 2, 3, 4 eingefügt. Dann habe ich den Wurzelknoten in dem die Zahlen 2, 3, 4 in dieser Folge stehen. Angenommen ich füge nun eine 1 ein, werden die anderen beiseite geschoben oder ein neuer Knoten eröffnet? Die Beispiele im Skript umschiffen dieses Problem sehr elegant durch die Wahl der Zahlen [img]http://www.sternenvolk.de/symb/28.gif[/img]

hmm, folie I-71 mit 85,90,95 is wohl doch eindeutig ;)

hmm, folie I-71 mit 85,90,95 is wohl doch eindeutig ;)

*aua* und ich hab vorhin noch gedacht das wäre nicht das was ich Suche, danke für den Hinweis ;)

Ok, hier kommt die nächste Runde [img]http://www.sternenvolk.de/symb/24.gif[/img]

Wir sollen bei dem M-Wege-Baum ja die durchschnittliche Pfadlänge angeben. Ist das mal irgendwo vernünftig definiert?
Ich meine, zählen innere Knoten mit oder nicht, Zählt ein Knoten der 3 Elemente enthält 3fach etc?

neues bildchen? der zaphod auch..,

naja ich bin jetzt auch überfragt, dafür gibts ja termine

Was itst ein links-vollständiger Binärbaum und wie ist dessen Arraydarstellung zu verstehen [img]http://www.sternenvolk.de/symb/26.gif[/img]
Edit: Google hat doch glatt eine Seite mit links-vollständig aufgetan :) ist die Array darstellung so zu verstehen, dass zuerst die Wurzel kommt, dann die beiden Knoten in Ebene 1, dann die 4 in Ebene 2 etc ?

Rein logisch betrachtet denke ich das auch, bin mir aber noch nicht ganz sicher [img]http://www.sternenvolk.de/symb/2.gif[/img]
http://wwwagr.informatik.uni-kl.de/~tombers/ESSY2/ESSY2_F02_2.pdf
http://www.stud.fernuni-hagen.de/q5635942/1661-1801.pdf
http://www.fh-wolfenbuettel.de/fb/i/organisation/personal/ruediger/lehre/Inf/ThillmRue.pdf

Ich rege mich schon wieder ueber die Zeitangaben auf den Aufgabenzetteln auf [img]http://www.sternenvolk.de/symb/8.gif[/img] Fuer Aufgabe 1 habe ich nicht eine Stunde sondern etwas ueber zwei benoetigt
Jetzt moechte ich natuerlich meine Ergebnisse mit Euren vergleichen. Wie macht ihr aus dem Baum einen Heap? Ich sortiere einfach das Array absteigend, nicht gerade intelligent, aber es funktioniert [img]http://www.sternenvolk.de/symb/24.gif[/img]
Bessere Loesung ist sicherlich http://ist.unibw-muenchen.de/Lectures/WT2000/EinfuehrungII/Blaetter/Blatt8.pdf

007 018 021 014 004 026 005 009 006 015 013 001 002 011 Abb. 1 - initialisierter, linksvollständiger binärer Baum 026 021 018 015 014 013 011 009 007 006 005 004 002 001 Abb. 2 - Heap, der aus Abb.1 durch Sortieren hervorgeht

Fred: Vielleicht irre ich mich ja, aber ich glaube Du hast das Array genau falschrum sortiert. Teilwurzel <= Söhne ist die Heap-Eigenschaft.
Ich sortiere jeden Pfad von einem Blatt bis zu der Wurzel per "BubbleSort" beginnend bei dem ("linksseitig" gesehenen) ersten Blatt.

Was habt ihr eigentlich bei der Höhe des m-Wege-Baums rausbekommen? Ich hab 5 (Wurzel hat Höhe 1)

Stimmt: In der Wurzel muss das kleinste Element stehen, und jeder Knoten ist kleiner als seine (beiden) Nachfolger!

Fred: Vielleicht irre ich mich ja, aber ich glaube Du hast das Array genau falschrum sortiert. Teilwurzel <= Söhne ist die Heap-Eigenschaft.

Ich denke mal es ist egal, wierum man sortiert, wenn es nur um das Sortieren an sich geht und die Ordnung nicht einen speziellen Zweck symbolisiert.

Stimmt: In der Wurzel muss das kleinste Element stehen, und jeder Knoten ist kleiner als seine (beiden) Nachfolger!

Steht sicher so im Skript, oder warum behauptest Du das so fest [img]http://www.sternenvolk.de/symb/7.gif[/img]
Gegenbeispiel gibts z.B. auf http://gtsun.et.fh-osnabrueck.de/lehre/algorithmen/alds-skript/node20.html

Eine <= Relation kann man auch so auslegen, dass groessere Zahlen <= sind als kleinere Zahlen…

Ich weiß nicht ob ich mich nun arg täusche, aber ein Heap ist wie liller sagt genau anders herum sortiert. auf Folie I-64 steht ja Die Wurzel eines Teilbaums ist das Minimum des Teilbaums. Man muß jetzt also jeden Strang mit einem Verfahren ähnlich Bubblesort sortieren. Und zwar immer beginnend mit dem linken strang. So wollten wir das lösen… hat aber nun jemand ne Idee wie man das direkt im Array macht?

Ich weiß nicht ob ich mich nun arg täusche, aber ein Heap ist wie liller sagt genau anders herum sortiert.

Ist doch fuer das Prinzip des Heapsort schnurzegal! Die Ordnung muss man einmal festlegen, und dann dafuer sorgen, dass sie fuer jeden Knoten im Baum gilt. Ob nun groesser oder kleiner… wen interessiert's? Es sagt ja auch niemand, dass es falsch ist, eine Namensliste absteigend von z nach a zu sortieren.

Man muß jetzt also jeden Strang mit einem Verfahren ähnlich Bubblesort sortieren. Und zwar immer beginnend mit dem linken strang. So wollten wir das lösen… hat aber nun jemand ne Idee wie man das direkt im Array macht?

Dass Du Rekursion benutzen musst, ist Dir klar? Vater von i ist i/2, Kinder von i sind 2i und 2i+1. Dann sollte das eigentlich kein Problem mehr sein… oder doch? [img]http://www.sternenvolk.de/symb/23.gif[/img]

Ich verstehe nicht ganz… ihr stellt den Baum als Array dar? Wie das denn? Einfach ein Array von int-Werten? Ich dachte, man muß das mit einer Klasse node und einer Klasse heaptree machen… und dann halt sich rekursiv durchwuehlen…

Ich verstehe nicht ganz… ihr stellt den Baum als Array dar? Wie das denn? Einfach ein Array von int-Werten? Ich dachte, man muß das mit einer Klasse node und einer Klasse heaptree machen… und dann halt sich rekursiv durchwuehlen…

Aufgabe 1 soll man doch ganz klar in einem Array machen. Die Indizes haben dann folgende Bedeutung:
1: Wurzel
2: linkes Kind von 1
3: rechtes Kind von 1
4: linkes Kind von 2
5: rechtes Kind von 2
6: linkes Kind von 3
7: rechtes Kind von 3

usw.

"b) Entwickeln und implementieren Sie einen Algorithmus, der einen beliebigen links-vollständigen Binärbaum in einen Heap überführt. "
>>klingt nach baum und nicht nach array

"c) Wenden Sie (neben eigenen Testfällen) das resultierende Programm auf den oben gegebenen Binärbaum an und geben Sie das Ergebnis wiederum in Array-Darstellung aus."
>>klingt stark nach baum als baum und nur die ausgabe als array

>>klingt nach baum und nicht nach array

Das Array repraesentiert einen Baum!

Das ist jetzt aber doch recht weit ausgelegt. Dann ist ein Integer ja irgendwie auch 'n Baum, nur ohne Blätter, hmm?

Das ist jetzt aber doch recht weit ausgelegt. Dann ist ein Integer ja irgendwie auch 'n Baum, nur ohne Blätter, hmm?

Loetzinn! Ein Integer ist natuerlich kein Baum, aber ein einelementiger Array mit einem Integer ist ein Baum bzw. kann als Baum interpretiert werden.

>>klingt nach baum und nicht nach array

Das Array repraesentiert einen Baum!

Fred hat wie immer recht!

Ja gut. Nun trotz aller Behauptungen: Wie sieht denn die Begründung aus, dass ein Array einen Baum repräsentieren soll. Das ein Integer kein Baum ist, ist mir auch noch gerade klar. Ich stehe ja auf der anderen Seite, das ich Array und Baum nicht so ganz vereinbaren kann. Sicher, Array und Baum sind beides verkettete Listen, aber danach hört es für mich auch schon auf.

Die Darstellung im Array ist doch nur eine mögliche Art und Weise. Sie hat den Vorteil, dass man sich keinen neuen Behälter zusammenbasteln muss. Schließlich ist es doch egal wie ich einen Baum INTERN repräsentiere, wenn nichts explizieit in der Aufgabenstellung gefordert ist.

@Fred
Wir wurden in unserer P3-Ü extra darauf hingewiesen, dass wir
eine Heap so verstehen sollen, dass das kleinste Element in der Wurzel usw. steht! Dies ist natürlich nur Definitionssache und man kann einen Heap genauso andersherum definieren. Wäre nur blöd wenn man wegen so einer Sache einen Punkt abgezogen bekommt, wie es mir auf dem ersten Zettel mit LinkedList passiert ist [img]http://www.sternenvolk.de/symb/10.gif[/img]

Die Darstellung im Array ist doch nur eine mögliche Art und Weise. Sie hat den Vorteil, dass man sich keinen neuen Behälter zusammenbasteln muss. Schließlich ist es doch egal wie ich einen Baum INTERN repräsentiere, wenn nichts explizieit in der Aufgabenstellung gefordert ist.

Ähm. Dem habe ich nicht widersprochen. Ich habe meinen Baum auch in ein Array gestopft. Das heißt aber noch lange nicht, dass Arrays Bäume repräsentieren? Wenn ich ein Buch zerpflücke und die Zettel in meinen Rucksack werfe, repräsentiert mein Rucksack doch kein Buch? [img]http://www.sternenvolk.de/symb/baby.gif[/img] Ich verstehe Euch nicht.

Yo leutz,
hat schon jemand aus Aufgabe 3 den B* Baum aufgemalt??
Würde den gern mal sehen.so zum Vergleich, müssen ja nicht die einzelnen Schritte sein, aber das Resultat wäre nicht schlecht!

Nach den ersten 7 Zahlen sieht das doch so aus, oder?:

17 33
/ | \
7,17 20,29 37,47


und wie geht's weiter?

Grrr…wieder nicht eingeloggt gewesen!
Das sieht ja schlimm aus!!! Ich meinte natürlich damit,
das der Baum so aussieht:
*17*33*
linker pointer auf 7*17
mittlerer pointer auf 20*29
und rechter pointer auf 37*47

Die Darstellung im Array ist doch nur eine mögliche Art und Weise. Sie hat den Vorteil, dass man sich keinen neuen Behälter zusammenbasteln muss. Schließlich ist es doch egal wie ich einen Baum INTERN repräsentiere, wenn nichts explizieit in der Aufgabenstellung gefordert ist.

Ähm. Dem habe ich nicht widersprochen. Ich habe meinen Baum auch in ein Array gestopft. Das heißt aber noch lange nicht, dass Arrays Bäume repräsentieren? Wenn ich ein Buch zerpflücke und die Zettel in meinen Rucksack werfe, repräsentiert mein Rucksack doch kein Buch? [img]http://www.sternenvolk.de/symb/baby.gif[/img] Ich verstehe Euch nicht.

Gutes Beispiel: Ein Buch ist doch nur ein Behälter für Informationen, die dort in einer bestimmten Art abgelegt sind.
In deinem Rucksack liegen die selben Informationen eben in einer anderen Weise, nämlich unsortiert, vor.

Gutes Beispiel: Ein Buch ist doch nur ein Behälter für Informationen, die dort in einer bestimmten Art abgelegt sind.
In deinem Rucksack liegen die selben Informationen eben in einer anderen Weise, nämlich unsortiert, vor.

Ja genau. Der Inhalt ist gleich. Aber der Behälter ist kein Baum/Buch mehr, sondern ein Array/Rucksack.

Fred hat Recht, danke Fred. Es fiel mir heute, als die Gedanken wanderten (d.h. M1-Vorlesung) wie Schuppen von den Augen.
Wenn man den Index eines Kindes berechnen kann, braucht man ja nicht mehr, das reicht fuer die ganze Aufgabe.
Haette ich brav eine Node-Klasse etc. geschrieben, waere das Array-maessige Ausgeben ein grosses Problem geworden.

Gut, dass ich noch nicht weit bin ;-))

Sicher, Array und Baum sind beides verkettete Listen

Die Begriffe "Array" und "Baum" funktionieren auf zwei verschiedenen Ebenen. Ein Array ist eine Ansammlung von Daten des gleichen Typs, die physikalisch im Speicher hintereinander angeordnet sind und per Index angesprochen werden koennen. Was Du als Programmierer mit dem Array machst ist Dir ueberlassen. Ein Array an sich steht ansonsten erst mal fuer gar nichts.
Ein "Baum" ist ein abstrakter Datentyp, in dem Relationen zwischen Elementen eingefuehrt werden, Stichwort: Vater/Sohn. Die zugrundeliegende Datenstruktur muss es also moeglich machen, von jedem beliebigen Element den Vater und die Soehne bestimmen zu koennen. Eine moegliche Implementierung (!) ist das Verwenden einer Node-Klasse, deren Exemplar auf andere Exemplare verweisen. Bei m-Wege-Baeumen oder stark entarteten binären Baumen sollte dieser Weg eingeschlagen werden.
Fuer den Spezialfall des linksvollstaendigen Binaerbaumes ist der Aufwand, mit Exemplaren einer Node-Klasse zu jonglieren, nicht gerechtfertigt. Wenn man die (gedachten) Knoten des Baumes von oben nach unten sowie von links nach rechts abzaehlt und dabei mit 1 an der Wurzel beginnt, ergibt sich eine vorteilhafte Numerierung, da das "Rumwandern" im Baum von Vater zu Sohn oder umgekehrt nicht mehr ueber Zeiger erledigt werden muss, sondern sich auf einfache Integer-Arithmetik beschraenkt (linker Sohn = 2*Vater, rechter Sohn = 2*Vater+1, Vater = Sohn/2).

Und ein Array ist mit Sicherheit keine verkettete Liste, wie Du oben schrobst [img]http://www.sternenvolk.de/symb/25.gif[/img]

Die Darstellung im Array ist doch nur eine mögliche Art und Weise

Genau. Wobei ich da gerade ein bischen ueber die Begrifflichkeit des Sowieso-Behaelters stolpere. Ein Array ist ja ganz klar ein technischer Behaelter. Aber was ist ein Baum? Fuer einen fachlichen Behaelter ist er mir irgendwie zu unspezifisch und abstrakt.

Wir wurden in unserer P3-Ü extra darauf hingewiesen, dass wir eine Heap so verstehen sollen, dass das kleinste Element in der Wurzel usw. steht! Dies ist natürlich nur Definitionssache und man kann einen Heap genauso andersherum definieren. Wäre nur blöd wenn man wegen so einer Sache einen Punkt abgezogen bekommt, wie es mir auf dem ersten Zettel mit LinkedList passiert ist

Danke fuer den Hinweis! Wobei ich einen Punktabzug auf dem ersten Zettel schon irgendwie nachvollziehen kann, wenn da die Ordnung EXPLIZIT vorgegeben ist. Durch den Begriff "Heap" alleine ist dagegen noch keine Ordnung festgelegt.

Ich habe meinen Baum auch in ein Array gestopft. Das heißt aber noch lange nicht, dass Arrays Bäume repräsentieren?

Generell repräsentieren Arrays gar nichts. Erst die Verwendung durch den Programmierer gibt dem speziellen Array einen Sinn.

Wenn ich ein Buch zerpflücke und die Zettel in meinen Rucksack werfe, repräsentiert mein Rucksack doch kein Buch?

Du kannst ein Buch (fachlicher Behaelter) nicht mit einem Array (technischer Behaelter) vergleichen. (Es verbietet Dir ja nicht einmal jemand, das Buch als Array zu implementieren.)

Ja genau. Der Inhalt ist gleich. Aber der Behälter ist kein Baum/Buch mehr, sondern ein Array/Rucksack

Wieso ist ein Rucksack ein Array???

Wenn man den Index eines Kindes berechnen kann, braucht man ja nicht mehr, das reicht fuer die ganze Aufgabe

Eben. Die Implementierung als Array hat nebenbei erwaehnt natuerlich den Nachteil, dass nicht einfach ganze Teilheaps mit einer einzigen Tauschoperation austauschen kann, aber das ist fuer die erste Aufgabe ja auch gar nicht noetig, elementeweises Tauschen genuegt vollkommen.

Du solltest Heiliger werden… so sehr wie du dich um das baumtechnische Seelenwohl der anderen kümmerst [img]http://www.sternenvolk.de/symb/22.gif[/img]

LOL. Naja, wenn hier jemand etwas anscheinend nicht verstanden hat und Sachen durcheinander würfelt, so das nachher überhaupt keiner mehr durchblickt isses besser, wenn das mal eine klar stellt.
Und genau das hat Fred gemacht. Thnx Fred [img]http://www.sternenvolk.de/symb/28.gif[/img]

Du solltest Heiliger werden… so sehr wie du dich um das baumtechnische Seelenwohl der anderen kümmerst [img]http://www.sternenvolk.de/symb/22.gif[/img]

Und Du solltest Dich ein bischen mehr um Dein eigenes Wohl kuemmern und nicht noch um 3:36 UniMatiX Beitrage tippern [img]http://www.sternenvolk.de/symb/25.gif[/img]

Ich hab jetzt nicht ganz mitgekriegt, wie ihr die Sache mit dem Heap gelöst habt, aber was ist denn nu richtig??? Wenn man das z.B. bei Aufgabe 1d) mitreinnehmen will, spielt das doch ne Rolle, ob:

1)Wurzel <= Nachfolger, oder
2)Wurzel >= Nachfolger

Ich dachte immer, das der erste Fall richtig ist. Nun nach ein bißchen googl'n…finde ich etwa 50:50 Meinungen zu beiden!!! [img]http://www.sternenvolk.de/symb/3.gif[/img] Dabei sind Beispiele in Musterlösungen von Klausuren dabeigewesen, in denen ein Baum nur wegen 1) (da dort ein Heap nach 2) definiert wurde) als FALSCH gesehen wurde (laut Musterlösung)! Sprich: sind nun die kleinsten Schlüssel näher an der Wurzel oder doch die größten???

in wie fern sind denn die anderen interpretationen interessant?,
im skript steht doch einwandfrei, das das kleinste element oben stehen soll, im aufgabenzettel steht nix anderes, also solls so gemacht werden,
da hat noch nicht mal Fred widersprochen ;))

Wir fragen einfach am Donnerstag nach und gut is.

Du solltest Heiliger werden… so sehr wie du dich um das baumtechnische Seelenwohl der anderen kümmerst [img]http://www.sternenvolk.de/symb/22.gif[/img]

Und Du solltest Dich ein bischen mehr um Dein eigenes Wohl kuemmern und nicht noch um 3:36 UniMatiX Beitrage tippern [img]http://www.sternenvolk.de/symb/25.gif[/img]

Ups, das war ich nicht *sich rausred* da hat wer die Serverzeit umgestellt, ehrlich. Würd mich hüten nach Midnight noch auf den Beinen zu sein.

wie war das jetzt noch mal mit den pfadlängen?:
kleinste: die vom blatt mit der geringsten höhe
grösste: höhe des baums - 1
durchschnitt: pfadlänge aller blätter / anzahl aller blätter

richtig so definiert?

sind nun die kleinsten Schlüssel näher an der Wurzel oder doch die größten???

Geht das schon wieder los? [img]http://www.sternenvolk.de/symb/22.gif[/img]
Per Definition ist ein Heap ein binärer Baum, in dem für jeden Knoten gilt, dass dieser in einer bestimmten, transitiven Relation sowohl zu seinem linken als auch zu seinem rechten Sohn steht. Aus der Transitivität ergibt sich automatisch auch, dass der Knoten zu allen seinen Unterknoten in dieser Relation steht.
Welche Relation das ist, haengt vom jeweiligen Einsatzgebiet ab. Wenn Du einen Heap z.B. als Prioritaetswarteschlange verwenden moechtest, so sollte man fuer den Fall, dass kleinere Zahlen eine hoehere Priotitaet symbolisieren, die = Relation zu verwenden.
Besteht die Aufgabenstellung lediglich aus der Implementation eines beliebigen Heap ohne spezielles Einsatzgebiet und ist keine Ordnung explizit vorgegebn, so spielt es fuer die "Richtigkeit" der Implementation keine Rolle, welche Relation Du verwendest.
Du hast ja selbst gesehen, dass bei einem Zahlenheap beide Varianten (=) in der Praxis vorkommen. Wer sich nach dem BEISPIELheap aus dem Skript richtet und die <= Relation verwendet geht natuerlich kein Risiko ein, Punkte abgezogen zu bekommen, weil man sich als Student immer auf die vorhanden Skripte berufen kann.
Es wuerde mich allerdings stark wundern, wenn ein kompetenter Uebungsgruppenleiter wegen einer vom SkriptBEISPIEL abweichenden Ordnung noergelt, der Sortieralgorithmus zur Sicherstellung der Heapeigenschaft aber ansonsten in Ordnung ist…

im skript steht doch einwandfrei, das das kleinste element oben stehen soll, im aufgabenzettel steht nix anderes, also solls so gemacht werden, da hat noch nicht mal Fred widersprochen ;))

Ich sage nur, dass jemand, der = Relation gewesen sein. Das heisst aber nicht, dass die >= Relation falsch ist.
Auf eine normale Liste uebertragen wuerde das ja bedeuten: eine alphabetisch aufsteigende Liste ist eine sortierte Liste, waehrend eine alphabetisch absteigend sortierte Liste keine sortierte Liste ist. Kommt irgendwie nicht hin, oder?

wie war das jetzt noch mal mit den pfadlängen?
kleinste: die vom blatt mit der geringsten höhe

Genau, wobei leere Blaetter nicht zaehlen, das muessen schon echte sein [img]http://www.sternenvolk.de/symb/23.gif[/img]

grösste: höhe des baums - 1

Joa, ich habe die groesste implementiert und die Hoehe dann als 1 mehr realisiert, aber wie rum man das macht ist natuerlich egal.

durchschnitt: pfadlänge aller blätter / anzahl aller blätter

Genau, wobei ich es unsinnig finde, die durchschnittliche Pfadlaenge als int zurueckzugeben.

richtig so definiert?

AFAIK schon, aber darauf gebe ich keine Garantie. Fuer mich macht es so einfach am meisten Sinn

Was ist eigentlich, wenn man zwei Objekte mit identischem Schluessel einfuegt? Bin ich heute mit Julian drueber gestolpert. Die Definition des mWege Suchbaumes verbietet dies nicht. Aber die Methode find(key) gibt ja lediglich ein einziges Objekt zurueck… schlecht oder?

NP: Beethoven

Was ist eigentlich, wenn man zwei Objekte mit identischem Schluessel einfuegt? Bin ich heute mit Julian drueber gestolpert. Die Definition des mWege Suchbaumes verbietet dies nicht. Aber die Methode find(key) gibt ja lediglich ein einziges Objekt zurueck… schlecht oder?

da sind 2 interessante sätze auf der definition von folie I-69 (falls sie nicht einfach nur ein beispiel ist ;)) )

"die schlüsselwerte sind aufsteigend geordnet, Ki <= Ki+1 "(wohlbemerkt kleinergleich, also mit doppelten)

"die elemente von unterbäumen sind kleiner/ grösser als die umschliessenden schlüsselwerte" (wohlbemerkt echt kleiner/ grösser, also keine doppelten, oder max. 3 und keine zwischenbäume…)

-> wenn man doppelte zulässt, hat man probleme mit der 2. bedingung, und davon abgesehen ist es ziemlich undefiniert, wo man denn das x. element des gleichen schlüsssels einfügt ;),
wenn man keine doppelten zulässt, ist die erste bedingung bisschen ungenau, aber sonst alles ok

–> also ne übungsfrage ;)

die elemente von unterbäumen sind kleiner/grösser als die umschliessenden schlüsselwerte" (wohlbemerkt echt kleiner/ grösser, also keine doppelten, oder max. 3 und keine zwischenbäume…)

Das ist ja furchtbar! Andererseits sollte es bei vernuenftiger Wahl des Schluessels natuerlich niemals vorkommen, dass zwei Schluessel identisch sind. Fragt sich dann nur, warum Ki <= Ki+1, irgendwie muss es ja doch erlaubt sein… [img]http://www.sternenvolk.de/symb/5.gif[/img]

Noch ne Frage zu I-73: Was ist der Unterschied zwischen der ersten und der dritten Formel? Bin ich blind? [img]http://www.sternenvolk.de/symb/3.gif[/img]

Noch ne Frage zu I-73: Was ist der Unterschied zwischen der ersten und der dritten Formel?

Es gibt keinen! [img]http://www.sternenvolk.de/symb/25.gif[/img]

Bin ich blind?

weiß nich.. zum Tippen reicht es offenbar gerade noch [img]http://www.sternenvolk.de/symb/22.gif[/img]

Noch ne Frage zu I-73: Was ist der Unterschied zwischen der ersten und der dritten Formel?

Es gibt keinen! [img]http://www.sternenvolk.de/symb/25.gif[/img]

Ach so, super. Sollte da eigentlich was anderes stehen, oder sinds nur zwei Formeln, die wichtig sind?

Ich hab mal 'ne Frage zu den B*-Bäumen:
Auf Folie I-105 sind diese ja definiert worden, nur leider steht nicht dabei, wieviele Elemente die Wurzel als Blatt aufnehmen kann, bevor gesplittet werden muss! Ich hab mich jetzt zwar für 2k* entschieden, aber wenn es 2k wären, wäre mein ganzer schöner Baum hinfällig. Hab ich einfach irgendwo was übersehen oder wurde einfach vergessen, das zu definieren?
Und dann noch eine Frage zum Splitten:
Auf Folie I-113 wurde angegeben, daß nach dem Split-Vorgang das entstehende linke Blatt k* Elemente enthält, das rechte k* +1 Elemente. Auf der Folie I-112 wurden aber beim Splitten links k* +1 und recht k* Elemente eingefügt! Was ist denn nun richtig?

Achso, falls jemand vergleichen möchte, mein B-Baum sieht nach dem Einfügen aller Elemente so aus:
20 28 33 51 || 7 17 | 25 27 | 29 31 | 37 47 | 60 80 90

Der B*-Baum so:
20 29 47 || 7 17 | 25 27 | 31 37 |51 60 || 7 | 17 | 20 | 25 |27 |28 29 | 31 | 33 37 | 47 | 51 | 60 | 80 90

Noch ne Frage zu I-73: Was ist der Unterschied zwischen der ersten und der dritten Formel?

Es gibt keinen! [img]http://www.sternenvolk.de/symb/25.gif[/img]

Ach so, super. Sollte da eigentlich was anderes stehen, oder sinds nur zwei Formeln, die wichtig sind?

na das kann man sich ja wohl denken, was da stehen soll,
x e K(Pb): x>Kp

Achso, falls jemand vergleichen möchte, mein B-Baum sieht nach dem Einfügen aller Elemente so aus:
20 28 33 51 || 7 17 | 25 27 | 29 31 | 37 47 | 60 80 90

Der B*-Baum so:
20 29 47 || 7 17 | 25 27 | 31 37 |51 60 || 7 | 17 | 20 | 25 |27 |28 29 | 31 | 33 37 | 47 | 51 | 60 | 80 90

Ähmm…also bei 3a) sieht mein Baum so aus:

29 || 17,25 | 51,80 || 7 | 20 | 27,28 | 31,33 | 60 | 90

oder meinste ne andere Aufgabe?

Ähmm…also bei 3a) sieht mein Baum so aus:
29 || 17,25 | 51,80 || 7 | 20 | 27,28 | 31,33 | 60 | 90
oder meinste ne andere Aufgabe?

man beachte, das für k=2 in einen knoten 4 elemente passen, da gibt es doch extra das applet wo man nur draufdrücken muss (und vorher k=2 einstellen..)

Ich sortiere jeden Pfad von einem Blatt bis zu der Wurzel per "BubbleSort" beginnend bei dem ("linksseitig" gesehenen) ersten Blatt.

Du gehst wirkich jeden Pfad von unten nach oben? Das kann man aber noch optimieren [img]http://www.sternenvolk.de/symb/17.gif[/img]

Fred:
Sicherlich nicht die schnellste Methode, allerdings finde ich die persönlich am elegantesten [img]http://www.sternenvolk.de/symb/17.gif[/img]

Mein B*-Baum war wohl falsch, der sieht mittlerweile so aus:

20 33 || 7 17 | 27 29 | 37 47 51 60 || 7 | 17 | 20 | 25 27 | 28 29 | 31 33 | 37 | 47 | 51 | 60 | 80 90

mit Wurzel als Blatt höchstens 2k* Einträge, und ansonsten beim Splitten nach Einfügen von "Key_x" erst Key_x zu dem passenden Blatt hinzufügen, danach Key_k* ermitteln und Blatt splitten.

20 33 || 7 17 | 27 29 | 37 47 51 60 || 7 | 17 | 20 | 25 27 | 28 29 | 31 33 | 37 | 47 | 51 | 60 | 80 90

Ich habe im Angebot:
29 ||
17 25 27 | 33 37 51 80 ||
7 17 | 20 25 | 27 28 | 29 | 31 33 | 37 | 47 51 | 60 80 | 90

oder auch:
+--+ /29\ /+--+\ / \ +------------------+ +-----------------------+ |17 | 25 | 27| |33 | 37 | 51 | 80| /-----|-------|----\ /----|------|-----|-----\ / | | \ / | | | \ +----+ +-----+ +-----+ +--+ +-----+ +--+ +-----+ +-----+ +--+ |7 17| |20 25| |27 28| |29| |31 33| |37| |47 51| |60 80| |90| +----+ +-----+ +-----+ +--+ +-----+ +--+ +-----+ +-----+ +--+
Will nicht nochmal wer sein B*-Baum-Ergebnis dazulegen?
Ich finde die Dinger sind wahnsinnig schlecht zu checken

/; ;\ __ \\____// /{_\_/ `'\____ \___ (o) (o } _____________________________/ :--' Muh! ,-,'`@@@@@@@@ @@@@@@ \_ `__\ ;:( @@@@@@@@@ @@@ \___(o'o) :: ) @@@@ @@@@@@ ,'@@( `====' :: : @@@@@: @@@@ `@@@: :: \ @@@@@: @@@@@@@) ( '@@@' ;; /\ /`, @@@@@@@@@\ :@@@@@) ::/ ) {_----------------: :~`,~~; ;;;; : : ; : ; ; : `'`' / : : : : : : )_ \__; ";" :_ ; \_\ `,',' :__\ \ * `,'* \ \ : \ * 8`;'* * `^' \ :/ `^' `-^-' \v/ : \/ Kei' Allohol is aoch keine Lösung…. *hicks*

hmm… ohne Zweizeiligkeit sieht das besser aus ;-)

Zaphi, das ist hier der P und nicht der Offtopic Bereich

:´¯ `·. .·´¯`: '·. •`·. .·´• .' `:--·´ `·--:´ ;´`; `·. ' ' .·´ ; ; ;`·-·´; (¯' '¯)

Ich habe im Angebot:
29 ||
17 25 27 | 33 37 51 80 ||
7 17 | 20 25 | 27 28 | 29 | 31 33 | 37 | 47 51 | 60 80 | 90

Meiner sieht bis auf die 28 genau so aus:
29 ||
17 25 27 | 33 37 51 80 ||
7 17 | 20 25 | 27 | 28 29 | 31 33 | 37 | 47 51 | 60 80 | 90

Das lässt, hoffen, dann checke ich nochmal genau, warum die 28 da bei mir steht :)

So, hab nochmal gecheckt, emine 28 war daneben gegangen, mein Ergebnis stimmt jetzt überein [img]http://www.sternenvolk.de/symb/28.gif[/img]

Servus,

wie sieht es in 3. b) mit dem Löschen aus dem B*-Baum aus? Das Skript ist diesbezüglich ja nicht sehr ergiebig, und in einem anderen Skript habe ich ein doch recht umfangreiches Manual zum Löschen und Handling gefunden, wenn nach dem Löschen in einem Blatt weniger als k* Schlüssel übrig sind (Stichworte Ausgleichen und Mischen).

Habt ihr da sowas berücksichtigt oder einfach nur "stumpf" die Schlüssel (bzw. das Blatt?) gelöscht?

Bei mir passiert ziemlich wenig beim Löschen (hatte unser ÜG-Leiter aber auch schon vorher angemerkt).
25 aus Blatt löschen, im Knoten drin lassen
20 aus Blatt löschen, Blatt wird gelöscht weils leer ist, 25 aus Knoten löschen

Wie hoch ist ein Baum, der nur aus einer Wurzel besteht? 1 oder 0?

0
steht im Skript beim Anfang der Bäume

Eigentlich 0 oder? In einem Binärbaum wäre es ja bspw. auch die 2^0, denn es gibt ja immer nur eine Wurzel. Gleiches bei 3^0, 4^0, n^0 = 1. Von daher würd ich sagen Höhe = 0. Oder liege ich falsch?

in einem binärbaum ist das so,

in m-wege-baum ist es aber 1, wenn die wurzel nicht leer ist,
vergleiche I-74, schranken für die höhe eines m-wege-suchbaums, I-81 für b-bäume (wahrscheinlich auch b*)

Wie ist Höhe definiert?
Ich würde h beim B-Baum und h* beim B*-Baum nehmen und die sind für einen Baum, der nur aus der Wurzel besteht 1 (Beispiel I-80). Höhe 0 wäre dann der leere Baum.

in einem binärbaum ist das so, in m-wege-baum ist es aber 1, wenn die wurzel nicht leer ist,

Kann ich mich da 100% drauf verlassen? Ich brauchs fuer die Implementation der getHeight() Methode des mWegeSuchbaums, da gebe ich einfach die maximale Pfadlaenge+1 zurueck.

na doll, 100% kann ich überhaupt nix sagen ;),
nur: ich bin davon überzeugt, dass die höhe eines nichtleeren m-baumes nach folie I-74 die untere schranke 1 hat,
so stehts da ja geschrieben..

Wo wir schon bei Genauigkeit sind:
Auf Folie I-105 Seite 53 ist unter Punkt 4 ein "Blattknoten" genannt. Damit ist doch das Blatt selbst gemeint oder nicht? Weil in 2 wird wieder "nur" von Blättern geredet…

Ich bin verwirrt!

Wo wir schon bei Genauigkeit sind:
Auf Folie I-105 Seite 53 ist unter Punkt 4 ein "Blattknoten" genannt. Damit ist doch das Blatt selbst gemeint oder nicht? Weil in 2 wird wieder "nur" von Blättern geredet…

Ja das ist schon das gleiche, keine Sorge. Ein Blatt ist ja auch ein Knoten, also kann man auch Blattknoten sagen.

Will nicht nochmal wer sein B*-Baum-Ergebnis dazulegen?
Ich finde die Dinger sind wahnsinnig schlecht zu checken

me hat auch so

Denkt dran, heute 23:59 ist Abgabetermin - ich haette es fast verschlafen [img]http://www.sternenvolk.de/symb/2.gif[/img] und das kaeme natuerlich nicht so gut.

Will nicht nochmal wer sein B*-Baum-Ergebnis dazulegen?

Ebenso :-)

ne frage in loser verbinung zum personenreader:

kann man eine eingelesene txt.datei mit stringtokenizer nach tabs trennen?,

bzw:
ich will ne excel-tabelle in java übernehmen,
wie mach ich das am geschicktesten?
(bisher meine idee: als tab-txt speichern (kann man anderes trennzeichen einstellen?)),
und dann so mühsam analog zum personenreader einlesen,

bin für alle java-bibliotheken offen ;)

kann man eine eingelesene txt.datei mit stringtokenizer nach tabs trennen?,

bzw:
ich will ne excel-tabelle in java übernehmen,
wie mach ich das am geschicktesten?
(bisher meine idee: als tab-txt speichern (kann man anderes trennzeichen einstellen?)),
und dann so mühsam analog zum personenreader einlesen,

Jap, das geht allerbestens so. Alternativ gibts noch das CSV-Format, das nimmt ; als Trennzeichen. So oder so denke ich bist du mit nem selbstgebastelten Reader am besten bedient, denn eine Library muss immer jeden beliebigen Fall aktzeptieren können und wäre demnach wohl entsprechend komplex zu bedienen.

W I E ?


(wie heisst der befehl, was ist das zeichen für tab ;) )

W I E ?


(wie heisst der befehl, was ist das zeichen für tab ;) )

[img]http://www.sternenvolk.de/symb/7.gif[/img]
String s = .....; StringTokenizer st = new StringTokenizer(s, "\t"); String s1 = st.nextToken(); ...
besser? [img]http://www.sternenvolk.de/symb/28.gif[/img]

jo danke [img]http://www.sternenvolk.de/symb/22.gif[/img] \t also..