Aus der Einführung in Algorithmen von Thomas Cormen:
" Um die Dinge einfach zu halten, nehmen wir an, wie wir es für binäre Suchbäume und rot-schwarz haben Bäume, dass jede "Satelliteninformation", die einem Schlüssel zugeordnet ist, in demselben gespeichert wird Knoten als Schlüssel. In der Praxis könnte man eigentlich mit jedem Schlüssel nur einen Zeiger auf speichern eine weitere Seite mit den Satelliteninformationen für diesen Schlüssel. Der Pseudocode In diesem Kapitel wird implizit davon ausgegangen, dass die mit a Schlüssel oder der Zeiger zu solchen Satelliteninformationen, fährt immer dann mit dem Schlüssel Schlüssel wird von Knoten zu Knoten verschoben. "
Ich habe also versucht, die Bedeutung des Begriffs Satelliteninformationen zu googeln, aber ich kann keine finden (von Dingen über NASA abgedeckt). Mein Verständnis basierend auf dem Text allein ist, dass "Satelliteninformationen" eine Adresse zu der Position des tatsächlichen Schlüsselwerts wie ein Zeiger ist? Habe ich Recht oder habe ich es falsch verstanden?
EDIT: Was unterscheidet es von einem Schlüssel?
Satellitendaten beziehen sich auf alle "Nutzlast" -Daten, die Sie in Ihrer Datenstruktur speichern möchten und die nicht nicht Teil der Struktur der Datenstruktur sind. Es kann alles sein, was du willst. Es kann ein einzelner Wert, eine große Sammlung von Werten oder ein Zeiger auf eine andere Stelle sein, die den Wert enthält.
Hier ist zum Beispiel ein Listenknoten für eine einfach verknüpfte Liste, deren Satellitendaten eine einzelne ganze Zahl sind:
%Vor% Mit anderen Worten, der gesamte Wert einer gegebenen Datenstruktur liegt in den Daten, die sie enthält, nämlich den Satellitendaten in der Terminologie Ihres Buches. Die Datenstruktur wird zusätzlich strukturelle Daten konsumieren (wie der next -Zeiger im Beispiel), um die Algorithmen auszuführen, die sie definieren, aber diese sind im Wesentlichen "Overhead" aus der Sicht des Benutzers.
Bei assoziativen Containern übernimmt der Wert "Schlüssel" eine doppelte Rolle: Zum einen handelt es sich um Benutzerdaten, zum anderen ist er auch Teil der Struktur des Containers. Ein Baum kann jedoch mit zusätzlichen Satellitendaten ausgestattet werden, in diesem Fall wird er zu einer "Karte" von Schlüsseldaten zu Satellitendaten.
In einem Extremfall haben Sie ein Array fester Größe mit no Overhead und nur Nutzdaten, und auf der anderen Seite haben Sie komplizierte Strukturen wie Multiindexe, Tries, Judy-Arrays oder lockfreie Container, die eine vergleichsweise große Menge an Strukturdaten pflegen.
Tags und Links algorithm pointers data-structures b-tree