Aus Das deutschsprachige Scratch-Wiki
Eine Baumstruktur ist eine Datenstruktur aus Kanten und Knoten, die wie ein Baum aufgebaut ist. Ein Baum besteht aus einer Wurzel und Blättern, sowohl in der realen Welt als auch in der Informatik. Bäume in der Informatik haben noch Kanten und innere Knoten. Rechts ist ein sehr kleiner, beschrifteter Baum zu sehen. Bei Bäumen in der Informatik ist die Wurzel meist oben, das heißt der Baum hängt quasi kopfüber.
- Ein Knoten ist ein Punkt, an dem sich eine Kante "spaltet".
- Eine Kante ist so etwas wie ein Ast: Einfach eine Verbindung zwischen zwei Knoten.
- Ein Blatt ist auch ein Knoten, jedoch hat es die besondere Eigenschaft, dass nach/unter ihr keine Knoten mehr folgen.
- Diese Knoten, die unter einem anderen Knoten folgen, das sind die Kindknoten des Knotens.
- Der Elternknoten eines Knotens ist - natürlich - der darüberliegende Knoten.
Binärer Suchbaum
Es gibt verschiedene Arten von Bäumen. In der Informatik wird zur Datenspeicherung oft ein binärer Suchbaum verwendet. Bei diesem Baum enthält jeder Knoten zwei Dinge (nicht immer): Einen sogenannten Schlüssel und den im Knoten gespeicherten Wert. Die Schlüssel sind Zahlen. Nach den Schlüsseln werden die Knoten sortiert und die Werte sind die Daten die abgerufen werden. So ähnlich wie bei einer nach Künstler sortierten Liste von Musikstücken: Der Schlüssel von einem Song ist dann der Künstler, weil die Songs nach Künstler sortiert sind. Und der Wert ist das Lied an sich.
Andere Eigenschaften sind, dass bei diesem Baum jeder innere Knoten höchstens zwei Kindknoten hat (binär bedeutet 2). Man kann die Kindknoten dann als linken Kindknoten und rechten Kindknoten betrachten. Ein linker Kindknoten muss immer einen geringeren Schlüssel besitzen als der Elternknoten. Der rechte Kindknoten immer einen höheren.
Darstellung
Es gibt verschiedene Möglichkeiten Bäume darzustellen. Man kann sie als
- Graph
darstellen, so wie in diesem Artikel auf den Bildern - als Einrückung darstellen:
|Wurzel
|___LinkesKind
|______LinksRechtesKind
|___RechtesKind
Verwendung
Bäume sind sehr gut zur Speicherung von sortierten Daten geeignet. Bei wenigen Elementen lohnt sich ein Baum noch nicht, aber schon schnell wird die Benutzung eines Baumes deutlich effizienter. Am besten sind zur Speicherung die binären Suchbäume geeignet.
Ein Beispiel: Du hast 16000 nach Titel sortierte Bücher einmal in einer Liste, und einmal in einem binären Suchbaum. Wenn du ein bestimmtes Buch suchst, brauchst du bei einer Liste durchschnittlich 8000 Durchgänge, bei dem Baum dagegen durchschnittlich nur ca. 13 Durchgänge. Damit ist der Baum 615 mal schneller! Je mehr Bücher, desto schneller ist der Baum im Gegensatz zur Liste.
Erstellung
Zum Erstellen eines Suchbaumes ist es am einfachsten, die Liste der Daten, die gespeichert werden soll, zuerst zu sortieren. Aus der Folge von Zahlen 5 3 1 6 2 4 wird dann 1 2 3 4 5 6.
Dann muss diese Liste geteilt werden: in ein Mittelteil, eine linke Seite und eine rechte Seite. Das Mittelteil ist eine Zahl, die genau in der Mitte steht. Wenn zwei Zahlen in der Mitte stehen, wie bei 1 2 3 4 5 6 die 3 und die 4, ist es egal welche Zahl das Mittelteil ist. Hier ist es einfach mal die 4. Die beiden Bereiche links und rechts davon sind die linke und die rechte Seite. In diesem Schritt wurde aus 1 2 3 4 5 6 schon 1 2 3 - 4 - 5 6. Das Mittelteil ist dann ein neuer Knoten. Die linke Seite ist der linke Kindknoten von dem Mittelteil-Knoten, die rechte Seite der rechte Kindknoten.
Jetzt hat der Mittelteil-Knoten aber zwei Listen als Kinder. Die beiden Listen müssen ebenfalls in Knoten umgewandelt werden. Das geschieht genau so wie eben. Zuerst kommt der linke Kindknoten, 1 2 3 dran. 2 ist das Mittelteil, 1 die linke Seite und 3 die rechte. Das Mittelteil ist ein neuer Knoten, links davon hängt die 1 und rechts davon die 3. Da die beiden Kinder der 2 keine Listen mehr sind, müssen diese auch nicht mehr umgewandelt werden. Aber es fehlt noch die andere Liste von eben!
Die andere Liste von eben, 5 6 muss auch noch umgewandelt werden. Hier ist entweder 5 oder 6 das Mittelteil, das ist egal. Hier wird jetzt mal 6 genommen. 6 ist also das Mittelteil, 5 ist die linke Seite und eine rechte Seite gibt es nicht. Und das ist dann wieder ein neuer Knoten: eine 6 und die 5 als linken Kindknoten.
Hier sind nochmal die einzelnen Schritte aufgelistet:
- Die Liste wird sortiert.
- Die Liste wird in Mittelteil, linke Seite und rechte Seite geteilt.
- Diese drei Teile werden in einen Knoten gepackt.
- Wenn nötig, werden die linke und die rechte Liste vom Knoten wie in Schritt 2-4 nochmal umgewandelt.
Benutzung
Wie man einen Baum überhaupt benutzt, also Elemente sucht und ausliest, wird hier erklärt. Rechts ist ein Beispiel eines binären Suchbaums mit Zahlen. Wenn man eine Zahl sucht, fängt man immer bei der Wurzel an. Zuerst prüft man, ob der Wert der Wurzel der Wert ist, den man sucht. Wenn nicht, prüft man, ob der Wert den man sucht, kleiner oder größer ist als der Wert in der Wurzel. Ist er kleiner, wiederholt man den Prozess mit dem linken Kindknoten der Wurzel, ist er größer mit dem rechten Kindknoten.
Wenn man in dem Baum rechts z.B. die 5 sucht, fängt man wie immer bei der Wurzel an. Die hat den Wert 8. Das passt nicht. Man prüft: Ist die 5 kleiner oder größer als 8? Sie ist natürlich kleiner. Also macht man mit dem linken Kindknoten weiter. Das ist die 4. Immer noch nicht richtig, allerdings ist jetzt der gesuchte Wert 5 größer als der Wert im Knoten, 4. Also macht man mit dem rechten Kindknoten der 4 weiter. Jetzt ist man bei der 6 angelangt. Die 5 ist kleiner als die 6, also macht man links weiter. Der Knoten beinhaltet 5, man sucht 5, und schon hat man das Ergebnis gefunden! 4 Durchgänge. Dasselbe kannst du ja auch mal ausprobieren.
Die Anzahl an Durchgängen die durchschnittlich benötigt werden, lässt sich mit dieser Formel berechnen (n ist die Anzahl der Ebenen, in dem Beispielbaum rechts gibt es z.B. 4 Ebenen):
Erweiterung
Wenn man neue Elemente zum Baum hinzufügen möchte, muss man durch den Baum durchgehen, und die richtige Position für das neue Element finden. Das Durchgehen ist oben schon erklärt. Man geht mit dem neuen Element einfach durch den Baum durch und wenn man an einer Stelle angelangt ist, an der kein Knoten mehr steht, fügt man dort das neue Element an. Ein Beispiel:
4 <--Wurzel
__2
____1
____3
__6
____5
____7
Wenn man an diesen Baum 8 anfügen will, geht man den Baum durch, erst über 4, dann kommt 6, dann 7, und dann kommt kein Knoten mehr. Also wird dort die 8 angehängt. Der Baum sieht dann so aus:
4
__2
____1
____3
__6
____5
____7
______8 <--neuer Knoten, rechtes Kind von 7
Balancierte Bäume
Ausgeglichenheit (Balance) ist noch eine Eigenschaft, die ein Baum haben kann. Ein Baum ist balanciert, wenn die Differenz der Tiefe von dem tiefsten Knoten und von dem höchsten Knoten höchstens 1 beträgt. Was bedeutet das jetzt? Erstmal, Tiefe ist, wie viele Ebenen ein Knoten von der Wurzel entfernt ist. Hier ist ein beschriftetes Beispiel:
5 <--Wurzel, deshalb Tiefe 0
__3 <-- Tiefe 1
____1 <-- Tiefe 2
______2 <-- Tiefe 3
____4 <-- Tiefe 2
__8 <-- Tiefe 1
____7 <-- Tiefe 2
______6 <-- Tiefe 3
____9 <-- Tiefe 2
______8 <-- Tiefe 3
Programmierung in Scratch
In Scratch gibt es keine Objektorientierte Programmierung, aber man kann Bäume mit Listen programmieren. Man benötigt 3 Listen, eine Liste für die Werte, eine für die linken Kindknoten und eine für die rechten Kindknoten. Dabei ist z.B. der 7. Eintrag in der Wert-Liste zu den beiden 7. Einträgen in den beiden Kindknoten-Listen zugehörig. Die Zahl, die in den Kindknoten-Listen steht, ist die Position des linken/rechten Kindknotens. So repräsentiert jeder Eintrag der 3 Listen einen Knoten. Hier ist ein Beispiel, wie die 3 Listen aussehen könnten:
Info: Bei dieser Methode gibt es einen kleinen Nachteil: keiner der Knoten weiß, wer sein Elternknoten ist. Das braucht man aber nicht immer zu wissen.
WERTLISTE: LINKSLISTE: RECHTSLISTE: 1. 4 1. 2 1. 3 <-- Wurzel 2. 2 2. 4 2. 5 3. 6 3. 6 3. 7 4. 1 4. 0 4. 0 5. 3 5. 0 5. 0 6. 5 6. 0 6. 0 7. 7 7. 0 7. 0
Wir gehen diese drei Listen einmal durch. Man muss wissen, dass in diesem Beispiel der erste Eintrag die Wurzel ist und dass eine 0 in der Links- oder der Rechtsliste bedeutet, dass es keinen linken/rechten Kindknoten gibt. Der 1. Eintrag ist also die Wurzel. Die Wurzel hat also den Wert 4. Der linke Kindknoten ist bei Eintrag 2 zu finden und der rechte Kindknoten bei Eintrag 3. Bei Eintrag 2 (linker Kindknoten der Wurzel) steht eine 2 als Wert. Bei Eintrag 3 (rechter Kindknoten) steht eine 6. Wenn man das System dann so durchgeht, kommt man am Ende auf diesen Baum:
4 __2 ____1 ____3 __6 ____5 ____7
Hier ist ein Scratch-Projekt, das zeigt, wie so eine Implementation mit Listen aussehen könnte:
Schau' dir dieses Projekt auf der Scratch-Webseite an...
weiterführende Seiten
- Englisches Scratch Wiki: en:Game Tree
- Wikipedia: Baum (Datenstruktur)
[wiki=de:Baumstruktur]Baumstruktur[/wiki]
