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?
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.
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
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?
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.
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.
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.
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.
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
Baum.jpg
(18 KB)
