Einführung in Bäume
-
Hi,
ich suche eine Einführung zu Bäumen. Das Problem ist, dass ich erst in der 11. Stufe bin und mir z.B. die Erklärungen auf Wikipedia mathematisch zu kompliziert sind. Gibt es Tutorials, die man mit weniger mathematischen Kenntnissen durcharbeiten kann?
MfG,
Michael E.
-
Die Idee ist einfach:
Halbiere den Suchraum.
Beispiel: 2, 5, 9
Der erste Knoten ist 5. Links davon wird 2 eingefügt, weil 2 < 5. Rechts wird 9 eingefügt, weil 5 < 9.
Also steigt mal links ab wenn man Knoten sucht die niedriger sind als der Schlüssen des ersten Knoten und rechts wenn sie höher sind.
Neben bei gibst noch die Probleme, das Knoten im Baum hoch oder runterwandern müssen, das der Baum ausgelichen sein soll.
-
naja, baeume halt. was willst du wissen?
gibt eben verschiedene arten von baeumen. der einfachste und damit auch verstuemmelste ist ne verkettete liste. dann gibts den baum mit je 2 aesten je knoten, der ist sehr haeufig. 3+ aeste je knoten werden selten gesichtet, weil sie spezielle aufgaben erfuellen.
dann gibts verschiedene arten, einen baum aufzubauen und zu ergaenzen. manche sind schnell und machen den baum schief, manche sorgen dafuer, dass der baum balanciert bleibt.
ein balancierter baum ist ein baum, der an jedem ast moeglichst gleich viele kindknoten hat. sinn dahinter: wenn man einen wert sucht, muss man nut log(knoten)/log(aeste pro knoten) operationen machen bis man am "blatt" (endknoten/ast) angekommen ist.
grobe uebersicht. genauer gehts bei wikipedia oder in diversen knuth buechern (hoffe ich; der hat schon viel geschrieben, aber noch nicht ueber alles).
-
Was willst Du denn wissen? Ich wuesste jetzt nicht, was es alles ueber Baeume zu schreiben gibt, dass man damit ein ganzes Tutorial fuellen kann...
-
Den Grundaufbau kenn ich schon. Jetzt gehts mir halt drum, mich mit speziellen Bäumen zu beschäftigen. Nur eignen sich die meisten Texte für mich eben nicht
[Edit] Na gut, wenn ich die einzelnen Bäume über Google such, findet sich schon was. Aber gibts keine Seite, wo möglichst viele Bäume erklärt werden?
-
Michael E. schrieb:
Hi,
ich suche eine Einführung zu Bäumen. Das Problem ist, dass ich erst in der 11. Stufe bin und mir z.B. die Erklärungen auf Wikipedia mathematisch zu kompliziert sind. Gibt es Tutorials, die man mit weniger mathematischen Kenntnissen durcharbeiten kann?
MfG,
Michael E.
-
SG1 schrieb:
Was willst Du denn wissen? Ich wuesste jetzt nicht, was es alles ueber Baeume zu schreiben gibt, dass man damit ein ganzes Tutorial fuellen kann...
Hm, ich wüßte ehrlich gesagt eher nicht, wie man das alles in ein einziges Tutorial packen könnte.
-
Jester schrieb:
SG1 schrieb:
Was willst Du denn wissen? Ich wuesste jetzt nicht, was es alles ueber Baeume zu schreiben gibt, dass man damit ein ganzes Tutorial fuellen kann...
Hm, ich wüßte ehrlich gesagt eher nicht, wie man das alles in ein einziges Tutorial packen könnte.
Wollt ich gerade auch sagen
-
kann doch aber auch kein problem sein, wikipedia zu lesen. wenn du probleme mit einem speziellen baum hast, sag.
-
In meinem TUM Skript zu DS1 gibts ein Kapitel zu Bäumen - es gibt doch einiges zu Bäumen zu sagen;) Aber wenn dir wiki schon zu mathematisch is, is das eher nix für dich
Aber für die grundlegende Arbeit mit Bäumen reicht eigentlich wirklich das Wissen aus, dass es einfach nur nen zusammenhängender, kreisfreier Graph is.
-
this->that schrieb:
Aber für die grundlegende Arbeit mit Bäumen reicht eigentlich wirklich das Wissen aus, dass es einfach nur nen zusammenhängender, kreisfreier Graph is.
Damit hast aber das Thema Implementierung noch kein Stück angekratzt. Da gibt's ja auch wieder jede Menge Möglichkeiten.
