Im Oberland gibt es inzwischen viele Baumcaches. Da wollte ich nicht nachstehen und auch mal einen legen. Weil ich aber von solchen Verstecken gerne herunterfalle, konnte ich das bisher nicht realisieren. Nun stieß ich auf einen Baum, dessen Wurzeln oben und dessen Blätter unten sind. Da fällt das Verstecken leicht!
Diese Spezies wurde erstmals schon 1962 von den sowjetischen Botanikern G.M. Adelson-Velskii und E. M. Landis beschrieben und "Suchbaum" genannt (Georgy Maximovic Adelson-Velskii, Evgenii Mikhailovich Landis, Доклады Академии Наук СССР 146 (1962), 263-266). Später entdeckte man zahlreiche Vorkommen, darunter ein großes am Fibonacci-Heap, das sich "Wald" nennt (Quelle: Wikipedia). Aber der Fibonacci-Heap liegt mir geistig zu weit entfernt, als dass ich da einen Cache verstecken möchte. Ich bleibe lieber bei einem einzelnen Suchbaum.
Wikipedia sagt dazu: "Die charakteristische Operation des Suchbaums ist das Suchen."
Das klingt in Geocachers Ohren ja schon mal vielversprechend.
Wiki weiter: "Der maximale Aufwand für das Suchen ist proportional zur Baumhöhe. Bei einem balancierten Baum ist die Höhe logarithmisch in der Anzahl n der Elemente, während sie bei einem zu einer linearen Liste degenerierten Baum proportional zu n ist."
Na klar, wir nehmen lieber ein balancierten Baum und nicht einen degenerierten, da fällt das Suchen leichter!
Wiki: "Insbesondere bei den binären Suchbäumen, bei denen ein Knoten maximal zwei Kindknoten besitzt, sind viele Varianten entwickelt worden, die der Degeneration entgegenwirken sollen."
"Binär" klingt so als hätte man nur zwei Möglichkeiten. Sehr gut!
Wiki: "Ein binärer Suchbaum ist ein binärer Baum, bei dem die Knoten „Schlüssel“ tragen, und die Schlüssel des linken Teilbaums eines Knotens nur kleiner und die des rechten Teilbaums nur größer als der Schlüssel des Knotens selbst sind."
Aha!
Ein Binärbaum b heißt geordnet, wenn folgendes für alle nichtleeren Teilbäume t von b gilt:
- Der Schlüssel von t ist größer als alle Schlüssel des linken Teilbaums von t und
- kleiner als alle Schlüssel des rechten Teilbaums von t
Toll! Leer ist für einen Geocacher ein Baum ja nur, wenn kein Cache drauf liegt oder wenn jemand den cache entwendet hat. Unser gesuchter Baum ist also hoffentlich nicht leer. Aber schön ordentlich soll das Versteck ja schon sein: Luftig, damit das Logbuch nicht schimmelt, für Geocacher leicht und für Muggels schwer zu finden.
Ein geordneter binärer Suchbaum ist zum Beispiel das hier:
Ihr findet den invertierten geordneten binären Suchbaum bei:
N 47° 39.DBB
E 011° 16.CAB
Eigentlich wollte ich das Mystery "Ein invertierter geordneter binärer Suchbaum" nennen. Aber dann hätten einige das listing garnicht angeschaut. Jetzt ist es zu spät!
Prüfe Deine Lösung