Warum handelt es sich hierbei nicht um einen ausgeglichenen Baum? Definition: "Ein Baum ist genau dann ausgeglichen, wenn sich für jeden Knoten die Höhe der zugehörigen Teilbäume um höchstens eins unterscheidet" Von welchem Knoten ist die Höhe der Teilbäume größer als eins? Was wird überhaupt als Teilbaum definiert?
Angehängte Dateien:
-
Baum.jpg
18 KB
Vorher konntest du keine verkettete Liste, nun lass die Finger von ausgeglichenen Baeumen, das kommt irgendwann spaeter, wenn du die Pointer drauf hast. Siehe auch Niklaus Wirth, Algorithmen und Datenstrukturen.
Jetzt Nicht schrieb: > Vorher konntest du keine verkettete Liste, nun lass die Finger von > ausgeglichenen Baeumen, das kommt irgendwann spaeter, wenn du die > Pointer drauf hast. Ganz abgesehen davon, dass ich mir nicht vorstellen kann, dass jemand an 1nem Abend den ganzen Themenkreis 'einfach verkettete Liste' durch hat und soweit zumindest leidlich beherrscht. Was ist mit den Operationen 'Knoten an beliebiger Stelle einfügen', 'suchen in der Liste', 'löschen aus der Liste', 'Liste sortieren', um nur einige zu nennen? Wie gut bzw. schlecht lassen sich unterschiedliche Sortieralgorithmen implementieren, wenn man die Umsortierung nicht durch Datenkopieren sondern durch Pointer umhängen realisieren will (was bei grossen Records Sinn macht). Wie unterscheiden sich Implementierungen, die für die Root anstatt eines Pointers ein Strukturobjekt ansetzen, ist die Implementierung einfacher oder komplizierter (Hinweis: die komplexeste Operation ist praktisch immer 'Knoten löschen'). Was ist eine vernünfitige Codeorganisation? Welche Funktionen wird man mit welchen Funktionsschnittstellen machen, damit man die Funktionalität 'e.v. Liste' einsatzfähig bei seinen Werkzeugen liegen hat? Welche Hilfsfunktionen sind sinnvoll um die an der Modulschnittstelle sichtbaren Funktionen zu vereinfachen? Da gibt es noch genügend Thematiken, die praktisch laufend immer wieder vorkommen und die studiert werden wollen.
:
Bearbeitet durch User
Karl Heinz schrieb: > Was ist mit den Operationen 'Knoten an beliebiger Stelle einfügen' usw. Das war von Interesse, als ich mir eine B-Tree-+-Datenbank programmiert habe - aber das macht heute niemand mehr, also wozu lehren und lernen. Georg
Der Baum, hat Äste -das ist das Beste. Doch wäre er kahl, dann wär's ein Pfahl. MfG Paul
Angehängte Dateien:
-
baum.JPG
11 KB
hallo, mich würde das auch mal interessieren, warum der obige Baum nicht ausgeglichen sein soll! Links vom Knoten habe ich ja die Teilhöhe 2 und rechts die Teilhöhe 0? Da dieser Unterschied größer als 1 ist, handelt es sich um keinen ausgeglichenen Baum? Bei meinem Beispiel (dieser ist ausgeglichen), hat der linke Teilbaum die Höhe 3 und der rechte die Höhe 1. Also wäre dieser auch nicht ausgeglichen nach der Definition?
Angehängte Dateien:
-
259051.jpg
2,2 KB -
261537.jpg
2,4 KB
Fragant schrieb: > Warum handelt es sich hierbei nicht um einen ausgeglichenen Baum? extern schrieb: > mich würde das auch mal interessieren, warum der obige Baum nicht > ausgeglichen sein soll! Das ist doch offensichtlich, wart ihr beide etwa nie in der Vorlesung oder mangelt es allgemein an logischem Verständnis ? Sicher, daß ihr das richtige Studienfach gewählt habt, Zocken steht nicht auf dem Lehrplan.
erklären, kannst du es wohl auch nicht. Genau darin liegt auch mein Problem, wie man den Baum ausgeglichen zeichnet ist schon klar, kann nur nichts mit der Definition anfangen. Ps: Warum hast du etwas am rechten Baum eingezeichnet? Der ist auch so ausgeglichen.
extern schrieb: > Ps: Warum hast du etwas am rechten Baum eingezeichnet? Der ist auch so > ausgeglichen. Wo ist denn der ausgeglichen? Im ersten Bild hat der Baum links 2 Knoten, rechts 0 (--> Differenz größer als 1: Nicht ausgeglichen) Das zweite Bild hat links 3 Knoten, rechts 1 (--> Differenz größer als 1: ebenfalls nicht ausgeglichen) Was ist denn daran so unklar, daß es noch erklärt werden muß?
extern schrieb: > erklären, kannst du es wohl auch nicht. Was willst du denn da gross erklären? Wenn die Blätter auf unterster Ebene alle auf gleicher Tiefe sitzen, dann ist der Baum ausgeglichen. Da das offensichtlich nur dann geht, wenn im Baum alle Knoten besetzt sind, wandelt man noch ein bischen ab. Die untersten Blätter eines Baumes dürfen sich in der Ebene maximal um 1 unterscheiden. Jeder der die Begriffe "wenig ausgefranst" und "stark ausgefranst" (zb bei einem Stoff) unterscheiden kann, sollte da eigentlich keine Schwierigkeiten haben. Ein Baum ist dann ausgeglichen, wenn seine 'Blätterkante' glatt oder zumindest "wenig ausgefranst" ist. > Ps: Warum hast du etwas am rechten Baum eingezeichnet? Der ist auch so > ausgeglichen. Wo ist der denn ausgeglichen? Aus Sicht des Wurzelknotens hat sein linker Teilbaum eine Höhe von 3 und der rechte Teilbaum eine Höhe von 1. Die Differenz ist offensichtlich größer als 1, also ist der Baum nicht ausgeglichen. Einfach Hinschauen reicht auch schon. Die 'untere Kante', also alle Blätter des Baumes, sind recht offensichtlich nicht (zumindest nahzu) auf derselben Stufe. Ehrlich: Das Konzept eines ausgeglichenen Baumes ist doch ziemlich intuitiv verstehbar. Wo habt ihr denn da immer nur Probleme? Die einzige Frage, die sich stellt, lautet doch: Müssen in einem ausgeglichenem Baum auch alle Telibäume selbst ausgeglichen sein oder nicht? Im allgemeinen wird man dies fordern, weil ansonsten ein balanzierter Baum nicht besonders nützlich ist, weil man die erwünschte Such-Komplexität, die in der Ordnung O(log2(n)) liegt, nicht erreichen kann. Und genau darum gehts ja schliesslich. Die Höhe des Baumes ist die maximale Anzahl an Suchschritten, mit der ich jeden Knoten im Baum finden kann. Und diese Anzahl will ich natürlich so klein wie möglich haben. Also sollen alle überhaupt vorhandenen Blätter so kleinen Abstand von der Wurzel haben, wie nur überhaupt möglich ist. Ganz was anderes ist es, einen nicht ausgeglichenen Baum in einen ausgeglichenen zu überführen. Das ist in der Tat eine erstaunlich komplizierte Operation.
:
Bearbeitet durch User
ok, ich erklärt das alle ein bisschen anders als ich es kennengelernt habe, jetzt verstehe ich auch warum ihr das so einfach findet. Ich habe aus ziemlich sicherer!!! Quelle gelernt, dass der rechte Teilbaum ausgeglichen ist und der untere nicht.
extern schrieb: > ok, ich erklärt das alle ein bisschen anders als ich es kennengelernt > habe, jetzt verstehe ich auch warum ihr das so einfach findet. > > Ich habe aus ziemlich sicherer!!! Quelle gelernt, dass der rechte > Teilbaum ausgeglichen ist und der untere nicht. Ein Teilbaum kann ja durchaus ausgeglichen sein. Dewegen muss ein Baum als ganzes noch lange nicht ausgeglichen sein. Ob ein Teilbaum ausgeglichen ist oder nicht, interessiert aber nur insofern, als man diese Eigenschaft prüfen will um zu bestimmen, ob der ganze Baum ausgeglichen ist oder nicht. Abgesehen davon ist die Ausgeglichenheit eines Teilbaumes recht uninteressant. Es ist die Ausgeglichenheit des kompletten Baumes, die praktisch relevant ist. Und ja: Ein Baum beginnt beim Wurzelknoten und nicht in der Ebene darunter.
:
Bearbeitet durch User
Georg schrieb: > Das war von Interesse, als ich mir eine B-Tree-+-Datenbank programmiert > habe - aber das macht heute niemand mehr, also wozu lehren und lernen. Man lernt für die Prüfung und fürs Leben, solche Fragen stellt man nicht, sonst wird man der Ketzerei beschuldigt. Früher hatte man solche Leute sofort verbrannt, Informatikstudenten steckt man in den ungekühlten Serverraum.
Nicht böse sein. Aber wenn man sich für Informatik interessiert, dann gehört da selbstverständlich auch ein gewisses Grundlagenwissen über Datenstrukturen dazu. Ich weiss, Grundlagen sind heute nicht mehr hipp. Und genau so sehen dann auch viele Programme in ihren Internas aus: mit der heissen Nadel und ohne Hirn und Verstand zusammengeklöppelt. Ein Aufbau der benutzten Datenstruktur, dass einem Angst und Bang wird und bei dem man erst mal haufenweise Stunden investieren muss um wenigstens die gröbsten Schnitzer zu beseitigen. Wenns dann so weit ist, das Programm zu erweitern oder Fehler zu finden, dann sind genau die Profis gefragt, die ihr Handwerk noch gelernt haben. Die holen dann die Kastanien wieder aus dem Feuer, die die Script-Kiddies reingeworfen haben.
:
Bearbeitet durch User
Karl H. schrieb: > ....mit der heissen Nadel > und ohne Hirn und Verstand zusammengeklöppelt. Na, na! Die meisten Klöppelarbeiten sind Spitze! https://www.youtube.com/watch?v=A5rP_e3KkJI ;-) mfG Paul
extern schrieb: > ok, ich erklärt das alle ein bisschen anders als ich es kennengelernt > habe, jetzt verstehe ich auch warum ihr das so einfach findet. > > Ich habe aus ziemlich sicherer!!! Quelle gelernt, dass der rechte > Teilbaum ausgeglichen ist und der untere nicht. Nicht alle Profs/Lehrenden verstehen den Stoff, den sie lehren sollen, zu 100%. Beim AVL-Baum z.B.: Ein Baum ist ein AVL-Baum gdw. für alle Knoten gilt: Die Höhe des linken und rechten Teilbaums eines Knotens unterscheidet sich um maximal 1. Stichwort wäre höhenbalanciert. Allgemeiner wäre dann balanciert/ausgeglichen mit der Definition z.B.: Kein Blatt ist sehr viel weiter von der Wurzel entfernt als alle anderen Blätter. Beispiel: Rot-Schwarz-Baum, der nur fast ausgeglichen ist, aber trotzdem eine maximale, logarithmische Gesamthöhe garantiert und daher garantiert, dass Suchen, Einfügen und Löschen in O(log n) machbar sind.
Benutzt eigentlich jemand wirklich solche Bäume? Ok, früher im Studium hat man sowas programmiert. Aber im richtigen Programmiererleben habe ich keine mehr benutzt. Die Datenmengen war zu klein, der Aufwand lohnte nicht. Dann nimmt man gleich C++ Template Klassen. Oder nimmt eine DB. Die benutzen bestimmt intern noch die Bäume, aber von Hand habe ich seit 15 Jahren keinen mehr gehabt. Wie schaut es bei euch aus? Programmiert ihr noch Anwendungen mit eigenen Bäumen?
PittyJ schrieb: > Wie schaut es bei euch aus? Programmiert ihr noch Anwendungen mit > eigenen Bäumen? Meistens reichen assoziative Listen. Ansonsten fertige Libs dazu genutzt, aber auch selten. Vor Jahren habe ich mal selber was implementiert, mittels Arrays, weil es schneller ist (dynamisch Speicher anfordern und freigeben kostet Zeit), hat nat. andere Nachteile die waren aber nachrangig. Grosse Datenmengen gehen heute direkt in die DB und lasse die die Drecksarbeit machen, die ist darauf optimiert.
Wie tut ihr heutzutage ein Menü (z.B. für eine Anzeige) implementieren, als über einen Baum?
Frank schrieb: > Wie tut ihr heutzutage ein Menü (z.B. für eine Anzeige) implementieren, > als über einen Baum? Nicht alles was hinkt ist ein Vergleich. Ein baum in dem Sinne des Threads wird für einen schnellen zugriff auf ein Element genutzt, das braucht man bei einem Menü nicht. Und wenn der Baum noch ausgeglichen ist, dann müsste man in jedem Menü die gleiche Anzahl von Einträgen haben, was auch nicht wirklich Praktisch ist.
Karl H. schrieb: > Wenns dann so weit ist, das Programm zu erweitern oder Fehler zu finden, > dann sind genau die Profis gefragt, die ihr Handwerk noch gelernt haben. > Die holen dann die Kastanien wieder aus dem Feuer, die die > Script-Kiddies reingeworfen haben. Und werden gut dafür bezahlt und freuen sich! Eric (mit Kastanienblasen auf den Händen)
PittyJ schrieb: > Wie schaut es bei euch aus? Programmiert ihr noch Anwendungen mit > eigenen Bäumen? Hab ich vor 25 Jahren oder so gemacht, kompliziert war nach meiner Erinnerung eigentlich nur der Ausgleich beim Löschen. Ich schätze mal, es gibt noch ein paar hundert Programmierer auf der Welt, die das wie ich mal gemacht haben und noch wissen wie's geht, und einige zig, die sich bei den Datenbankherstellern im Prinzip noch damit beschäftigen, aber selbst die werden an den seit Jahrzehnten ausgereiften Algorithmen nur selten was ändern. Also ein typisch akademisches Problem: theoretisch durchaus interessant, aber ohne praktische Bedeutung. Etwa so wie Theorien zum Compilerbau: keiner von den Studenten baut sich jemals einen Compiler selbst. extern schrieb: > Ich habe aus ziemlich sicherer!!! Quelle gelernt, dass der rechte > Teilbaum ausgeglichen ist und der untere nicht. Da es sowieso kein Schwein mehr interessiert, ist es doch völlig egal, welche Bäume dein Prof für ausgeglichen hält und welche nicht. Falls das geprüft wird, musst du dich halt nach seinen Marotten richten. Georg
Thread beobachten
Seitenaufteilung abschaltenBitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.