GC4QDFJ Bäume biegen (Unknown Cache) in Nordrhein-Westfalen, Germany created by Ede-Wolf

This cache has been archived.

Ede-Wolf: Nachdem diese Dose direkt nach dem Neuauslegen wieder verschwunden ist, gehe ich davon aus, dass irgendemand etwas dagegen hat, hier eine Dose zu verstecken.

Ich gebe deshalb den Weg frei für ein neues Döschen.

Vielen Dank für alle, die sich mit dem Rätsel beschäftigt haben und den Weg zum Döschen auf sich genommen haben. Die letzten haben dabei leider keine Dose mehr vorgefunden. Ich hatte viele positive Rückmeldung, vielen Dank dafür.

Vielleicht bis demnächst, ich muss mir wieder mal etwas ausdenken für Euch,

Ede-Wolf

GC4QDFJ ▼

A cache by Ede-Wolf Message this owner

Hidden : 11/5/2013

Difficulty:

Terrain:

Size: Size: small (small)

Join now to view geocache location details. It's free!

Watch

How Geocaching Works

Please note Use of geocaching.com services is subject to the terms and conditions in our disclaimer.

Geocache Description:

Die angegebenen Koordinaten sind wie immer ohne Bedeutung. Ihr werdet dort nichts vorfinden!!!

Liebe Cacherkollegen: Ich möchte euch ein sehr interessantes Konstrukt vorstellen: Einen seltsam aussehenden Baum! Begrüßt den neuen Kollegen ehrfurchtsvoll, auf dass er euch nicht in den Wahnsinn treibt.

Wenn man ihn sich genauer ansieht, dann erkennt man schon die erste Besonderheit: Der Volksmund behauptet, dass Bäume nicht in den Himmel wachsen. Dieser tut das ganz sicher nicht, denn er wächst von oben nach unten. Die Wurzel ist also oben und die Äste gehen nach unten. Die Elemente des Baumes sollen im folgenden Knoten genannt werden. Jeder Knoten hat zwei, einen oder gar kein Kind. Er hat niemals mehr als zwei Kinder. Wenn er gar kein Kind hat, wird dieser Knoten sinnigerweise als Blatt bezeichnet. Schauen wir uns diesen Baum doch jetzt einmal genau an: Ein Geheimnis besteht darin, dass die Baumstruktur die Werte der Knoten sortiert wiedergibt. Eure erste Aufgabe besteht jetzt darin, diese Sortierung zu verstehen. Ich bin ganz sicher, die Werte der Knoten könnt ihr im Kopf sortieren. Aber warum macht dieser Baum das gleiche?

Eine weitere wichtige Eigenschaft dieses Baumes möchte ich nicht unerwähnt lassen. Dieser Baum wirkt ziemlich ausgeglichen. Das soll heißen, dass sich die Ebenen des Baumes nahezu in Balance befinden. Das ist kein Zufall. Für jeden Knoten des Baumes differieren die Höhen der Unterbäume höchstens um 1. Wir werden gleich gemeinsam einen solchen Baum, mit dem ersten Element beginnend, aufbauen. Also keine Panik, wenn ihr jetzt noch nicht alles verstehen solltet.

Wozu braucht man so einen Baum? Wir stellen uns einmal ein Telefonbuch vor. Auch dort sind die Namen sortiert abgelegt. Der Sinn ist klar: Jeder möchte ja so schnell wie möglich einen gesuchten Namen finden. Wenn auch inzwischen diese Arbeit meist ein Computer übernimmt, waren früher die Menschen wirklich noch auf ein Telefonbuch angewiesen. Möchte man beispielsweise den Namen "Wolf" in so einem Telefonbuch finden, dann würde vermutlich niemand auf die Idee kommen, diesen Namen vorne im Buch zu suchen. Wenn aber nicht klar ist, wie die Namen im Buch verteilt sind, würde man wahrscheinlich folgende Strategie anwenden: Zunächst würde die Mitte des Telefonbuches aufgeschlagen und der dort befindliche Name kontrolliert. Steht der Wolf im Alphabet dahinter, wird die hintere Hälfte des Telefonbuches wieder halbiert, andernfalls die vordere. Durch diese Suchstrategie kommt man schneller zum Ergebnis, als man das vorher gedacht hätte. Wenn es 1000 Einträge im Telefonbuch gäbe, wäre man mit nur zehn Vergleichen beim richtigen Namen angekommen. Dieser ausbalancierte Baum arbeitet ähnlich. Dadurch, dass er in der Breite von Ebene zu Ebene anwächst, werden die Vergleiche bei der Suche nach einer bestimmten Zahl optimiert. Solange der Baum so schön ausbalanciert ist, werden die Suchzugriffe minimiert.

Bleibt die Frage zu klären, wie man so einen Baum so schön ausgeglichen aufbauen kann. Genau das werden wir jetzt machen. Wir fügen jetzt nach und nach Elemente in einen Baum ein und sorgen dafür, dass sie sortiert abgelegt werden. Ich behaupte jetzt einfach mal etwas: Jedes neue Element lässt sich als Blatt in einen bestehenden Baum einfügen, ohne dass die Sortierung dabei verloren geht. Ich habe die erste richtig gute Nachricht für euch. Wir werden auf einen Beweis dieser kühnen Behauptung verzichten und nehmen einfach an, dass sie korrekt ist. Trotzdem gibt es eine Schwierigkeit dabei: Wenn auch der Baum sortiert bleibt, ist nicht unbedingt gesagt, dass er nach einer Einfügeoperation immer noch ausbalanciert ist. Aber genau zu dieser Problematik werden wir eine Lösung erarbeiten.

Vergesst jetzt erst einmal den Baum oben aus dem Listing. Wir bauen jetzt einen neuen auf. Wir machen dazu alle notwendigen Schritte gemeinsam, ihr sollt nicht im Regen stehen.

Wir fügen jetzt nach und nach die Elemente 33-13-5-116-99-54-8-40-102-108-133 in einen zunächst leeren Baum ein. Wir achten auf das Einfügen an der richtigen Stelle, damit die Baumelemente sortiert sind und sorgen zudem dafür, dass der Baum ausbalanciert bleibt. Damit ihr alles versteht, werde ich an einigen Stellen fragen, warum etwas so ist, wie ich es behaupte. Die Fragen sollen nicht nerven, können es aber vermutlich. Wenn ihr es nicht wisst oder einfach auch nicht darüber nachdenken wollt, dann könnt ihr als Antwort auf eine warum Frage auch die berühmte Floskel mit den gebogenen Südfrüchten anbringen. Es kann aber wirklich helfen, wenn ihr wenigstens kurz nachdenkt. Am Ende müsst ihr nämlich eigenständig das machen, was wir jetzt zusammen durchführen. Da kann es hilfreich sein, wenn man möglichst viel weiß.

Die ersten zwei Elemente fügen wir jetzt ein und erhalten den Baum aus Abbildung 02. Die 13 wird links unterhalb der 33 eingefügt. Zum ersten mal dazu die ganz ganz wichtige Frage: Warum?

Der Baum ist der Definition nach immer noch ausgeglichen. Linker Unterbaum der 33 hat Höhe 1, der rechte ist nicht vorhanden und hat daher Höhe 0. Differenz der Höhen ist 1 und das ist noch ok. Übrigens: Die Höhe wird berechnet indem man vom Knoten zur untersten Ebene geht und jede Ebene zählt. Es werden also nicht die Gesamtzahl aller Knoten eines Unterbaumes gezählt, sondern nur die Ebenen, eben die Höhe des Unterbaumes.

Der Zufall will es nun so, dass das nächste Element erneut kleiner ist Abbildung 03a. Ihr seht, ich habe die neu eingefügten Elemente gelb hinterlegt. Der Baum ist sortiert, aber er ist nicht mehr ausgeglichen. Die Höhe des linken Unterbaumes der 33 ist 2, die des rechten ist 0. Differenz ist 2. Ich stelle euch jetzt eine erstaunliche Baumoperation vor: die Rotation. Die Pfeile deuten bereits an, was wir vorhaben. Die 13 soll links über die 33 gelangen, die 33 selbst rechts unter die 13 Wir klappen also die 13 nach rechts oben und dadurch die 33 nach rechts unten Abbildung 03b. Wir nennen diese Operation eine Rechtsrotation. Das Schöne daran: Der Baum bleibt sortiert: Warum?

Die nächsten zwei Elemente können wir nun einfügen. Nach der 116 ist der Baum noch ausgeglichen Abbildung 04, nach der 99 nicht mehr Abbildung 05a. Nun wird es schwierig. Wir haben jetzt eine Situation, die über die der letzten Rechtsrotation hinausgeht und damit meine ich nicht nur, dass es jetzt eine Linksrotation wäre. Zunächst einmal ist es ganz wichtig zu definieren, dass wir ein Ungleichgewicht immer von unten nach oben suchen. Deshalb ist die 33 im Ungleichgewicht. Die 13 wäre es auch, aber wir korrigieren das Ungleichgewicht an der 33. Dadurch wird automatisch auch das Ungleichgewicht an der 13 korrigiert (ja okay, ich frage mal ganz leise warum und weiß, dass es schwierig, aber auch nicht entscheidend für die Lösung des Rätsels ist. Nehmt es hin). Wenn wir die Linksrotation gemäß der blauen Pfeile so durchführen wie eben die Rechtsrotation, stellt sich die Frage, wie mit dem linken Unterbaum der 116 zu verfahren ist, dem Knoten 99. Dieses Problem hatten wir eben nicht, da die 13 bei der letzten Rotation keinen rechten Unterbaum hatte. Wenn hier die 99 z.B. eine 120 wäre, dann wäre sie rechts unterhalb der 116 (warum?) und die Situation wäre vergleichbar mit der von eben. Nun aber gibt es die 99. Durch das Hochklappen der 116 nach oben, erhält die 116 automatisch einen linken Unterknoten, nämlich die 33. Platz für einen weiteren linken Unterknoten (die 99) ist nicht da. Die 99 wird in diesem Fall umgehängt und bekommt ihren neuen Platz rechts unterhalb der 33. Dort gehört sie hin und dort ist immer Platz. Warum?

Aber damit nicht genug. Wenn wir das so machen erhalten wir Abbildung 05_einfach, mit der enttäuschenden Feststellung, dass dieser Baum immer noch unausgeglichen ist.

Hätte man das vorher schon erkennen können? Ja man hätte. Wir kehren zurück zur Abbildung 5a. Immer dann, wenn es zu einem Balancewechsel der beteiligten Knoten kommt, reicht die einfache Rotation nicht aus. Im konkreten Beispiel: die 33 war der Knoten, bei dem das Ungleichgewicht festgestellt wurde. Er ist rechtslastig (wenn ich das mal so formulieren darf). Er will mit der 116 rotieren. Die 116 hat aber eine Linkslastigkeit. Wenn die 116 ebenfalls eine Rechtslastigkeit hätte, würden wir keine Probleme haben. So hingegen müssen wir eine erweiterte Rotation vornehmen. Wir machen jetzt eine Doppelrotation, die Graphik deutet es schon an. Erst rechts (rote Pfeile), dann links (blaue Pfeile). Durch die erste Rotation (Rechtsrotation) gelangt die 99 eine Ebene nach oben und wird Vater der 116, die nach rechts unten klappt. Dann setzt die 99 ihren Weg nach oben fort und wird auch noch Vater der 33, die nach links unten klappt. Abbildung 05b. Wir haben jetzt wieder den schönen Anblick eines sortierten und ausgeglichenen Baumes.

Der Zufall will es so, dass wir das gleich noch einmal üben können. Nun wird das Element 54 eingefügt Abbildung 06a. Gleiche Situation wie gerade: Die 13 hat das Ungleichgewicht mit einer Rechtslastigkeit. Der darunter liegende Knoten 99 hat aber eine Linkslastigkeit. Wir haben eben gelernt: Hier muss eine Doppelrotation herhalten, erneut erst rechts, dann links. Mit einer Neuerung. Wir müssen uns dabei noch um den rechten Unterbaum der 33 kümmern. Wie eben schon mal gelernt, bekommt die 33 durch ihre Rechtsrotation automatisch einen rechten Unterknoten, nämlich die 99. Die 54 wird umgehängt und erhält links unterhalb der 99 ihren Platz. Um die Doppelrotation abzuschließen klappt die 33 dann ganz in die Baumspitze, die 13 klappt nach links unten. Der Baum ist wieder ausgeglichen Abbildung 06b.

Einen Einschub noch an dieser Stelle: Folgender Fall kommt in allen Beispielen nicht vor, ich möchte ihn aber trotzdem erwähnen. Wenn in Abbildung 6a die 33 auch noch einen linken Unterknoten gehabt hätte, wäre das eigentlich ein unrealistischer Fall, denn das Ungleichgewicht an der 13 ist ja erst durch Einfügen der 54 entstanden. Wenn es beispielsweise eine 30 links unter der 33 gegeben hätte, dann wäre da schon das Ungleichgewicht aufgetreten. Ich will trotzdem diesen Fall erwähnen, dass der untere Knoten, der in eine Doppelrotation verwickelt ist (hier die 33) einen linken und rechten Unterbaum haben kann. Das kann in einem komplexeren Baum passieren und deshalb stellen wir uns der Einfachheit halber vor, die 30 wäre auch noch da. Mir geht es darum, wo sie hinkäme, wenn doppelt rotiert würde. Die 54 erhält links unter der 99 ihren Platz, eine 30 würde rechts unter der 13 ihren Platz finden. Schaut euch Abbildung 6b noch einmal an, da wird es deutlich, dass eine 30 nur dort hinkommen kann, was ja auch logisch ist. In so einem Fall würden also zwei Unterbäume umgehängt. Ende Einschub.

Weiter geht es, die 8 wird eingefügt Abbildung 07a. Hier ist erneut eine Doppelrotation durchzuführen, diesmal aber erst links und dann rechts. Ungleichgewicht besteht an der 13, die eine Linkslastigkeit hat. Die 5 hingegen ist rechtslastig. Die LR Rotation ist hier einfach, da nichts umzuhängen ist Abbildung 07b. Wir erhalten sogar einen absolut symetrischen Baum.

Die nächsten beiden Elemente kommen daher auch ohne Rotation aus: Abbildung 08 und Abbildung 09. Dann wird die 108 eingefügt Abbildung 10a. Aber diese LR Doppelrotation stellt uns vor keine große Herausforderung, das kennen wir inzwischen Abbildung 10b.

Aber eine letzte Rotation machen wir noch. Die 133 wird eingefügt Abbildung 11a. Das ist wieder ein bisschen interessanter. Hier reichen wir die einzige Rotation nach, die wir bisher nicht hatten, die einfache Linksrotation. Beachtet das Ungleichgewicht am Wurzelelement 33. Aber diesmal ist auch bei der 99 eine Rechtslastigkeit vorhanden. Nur bei einer Linkslastigkeit an der 99 müsste doppelt rotiert werden. Hier reicht die einfache Rotation. Beachtet, dass der ganze Unterbaum, der links unterhalb der 99 hängt, umgehängt wird. Er erhält seinen neuen Platz rechts von der 33 Abbildung 11b.

Nun wisst ihr alles über diese Bäume, die von oben nach unten wachsen. Es gibt keinen Grund mehr, es nicht auch allein zu versuchen ein paar Elemente einzufügen. Daher jetzt zur Aufgabe: Fügt nacheinander die Elemente 110-125-37-6-48-60-35-51 in den gerade aufgebauten Baum ein (ihr steigt also direkt nach Abbildung 11b ein). Fügt sie dabei sortiert ein und überprüft nach jeder Einfügung, ob der Baum noch ausgeglichen ist. Wenn das nicht der Fall ist, führt eine Rotation durch, entweder eine einfache oder eine Doppelrotation, je nachdem welcher Art das Ungleichgewicht ist. Wenn ihr alles richtig gemacht habt, sollten wir die gleichen Bäume haben. Nun geht es darum die Koordinaten für die Dose zu errechnen. Das geht folgendermaßen:

Die Blätter des Baumes werden von links nach rechts mit A, B, C ... usw. belegt. Die Wurzel des Baumes folgt dem letzten Blatt. Zwei Beispiele dazu: Nehmen wir zunächst den Baum, den wir zusammen aufgebaut haben (natürlich nach der letzten gemeinsamen Rotation, also Abbildung 11b). Dieser Baum hätte folgende Lösung:

A=5, B=13, C=40, D=102, E=133, F=99

Ein zweites Beispiel ist der Baum am Anfang dieses Listings:

A=5, B=12, C=17, D=22, E=63, F=92 G=18

Was fällt auf? Die Blätter von links nach rechts sind sortiert. Ihr wisst was jetzt kommt: Warum? Wenn ihr nun die Lösungsbuchstaben für euren Endbaum berechnet, sollten zumindest die Buchstaben A-I bezeichnet werden können, denn diese Buchstaben stehen in der Formel zur Berechnung der Koordinaten.

Dieser Cache ist der erste in einer Reihe von Alliterations-Caches (das Wort habe ich mir gerade ausgedacht). Ich habe schon zwei weitere Ideen im Kopf, die Frage ist dabei nur, wann ich dazu komme, diese zu verwirklichen. Jedenfalls habe ich mir fest vorgenommen, auch die anderen Caches noch zu veröffentlichen. Am Ende soll es eine Bonusdose geben für diejenigen, die alle Caches besucht haben. Die erste Bonuszahl ist im Logbuch dieses Caches hinterlassen. Notiert sie euch, wenn ihr den Bonus irgendwann einmal finden möchtet.

Nun aber zurück zu diesem Rätsel: Sucht die Dose bei

(A-3)x² - (H + D -1 + 0,479)x + (B + C + E + 4*F + 5*G + i + 0,2285194825) = 0

Das i hinter 5*G ist bewusst klein geschrieben, um keine Verwechslungen mit einer 1 zuzulassen. Es gibt keinen größeren GAU als Zeichen, die nicht lesbar sind.

Beachtet beim Lösen dieser Formel unbedingt auch die Note vom 07.11.2013

Eure Lösung könnt ihr hier überprüfen:

Es liegen Urkunden für die ersten drei Finder in der Dose. Außerdem eine FTF Coin für den Erstfinder.

Viel Spaß und viel Erfolg bei der Rätselei,

Gruß Ede-Wolf

Hall of Fame