Algorithmus: Berechnung eines "Key"'s einer Datenstruktur (AVL Tree) - wie?

[Fabeltier]

Hallo,
wegen einem eigenem Projekt denke ich gerade ueber einen Algorithmus bzw eine Moeglichkeit nach zwei AVL Trees A und B zu vergleichen.

Gegeben:
Zwei AVL trees, jedes Element in den Trees enthaelt versch. Attributsvariablen und ein Attribut nach dem die Elemente eingeordnet wuerden.

Problem:
Wenn ich nun beide Trees vergleiche, moechte ich wissen welche der Elemente sich auf Grund der Attributsvariablen unterscheiden (zB Element xy in A wurde 2 mal modifiziert, element xy in B nur 1 mal - reicht voellig!!!), aber auch in der Anzahl der Elemente in A oder B. Ich wuerde dazu gerne soetwas wie einen "Gesamtkey" berechnen, also nur eine Zahl. Dabei ist B eine "synchronisierte" Kopie von A, d.h. sobald ich in A was aendere, sollte B synchronisiert werden. Als Bestaetigung der Synchronisation sollte der Key gesendet werden. Faellt somit eine synchronisation irgendwie flach - sollte an Hand des Keys moeglich sein, zu ermitteln welches Leaf nachgesendet werden muss.

Ich habe ueberlegt, die Elemente irgendwie durchzunummerieren (zB mit Primzahlen, oder den Zahlen irgendeiner math. Reihe) und dann, bspw wie bei den Datei Rechten unter Linux, diese "Indizes" aufzuaddieren, zu multiplizieren oder sonstwie zu verrechnen - das Ergebnis sollte Aufschluss geben ueber:
a) welches Element sich unterscheidet auf Grund der Anzahl der daran durchgefuehrten Modifikationen.
b) welches Element fehlt in A, aber nicht in B
c) welches Element fehlt in B, aber nicht in A
d) welches Element aus A stimmt nicht mit B ueberein

Frage:
Ist so ein Algorithmus ueberhaupt moeglich und falls ja, wie berechne ich eine Zahl die mir darueber Aufschluss gibt, bzw wie gehe ich bei sowas vor?

Bin auch offen fuer Stichworte und Links im Netz fuer weitere Info - in welchen Bereich geht so eine Frage eig, is das was mathematisches?

TIA

[Blue-Tiger]

Evtl. nicht sehr "sauber", aber relativ leicht machbar: die Trees fuehren ein Logbuch mit, in welchem jeder Event (Loeschen, Einfuegen, Updaten) mit einem Timestamp eingetragen wird. Alles was du dann machen musst, ist die Timestamps auf Identitaet zu ueberpruefen.
Ein trivialer Algorithmus dazu waere dann: vergleiche periodisch den Hash des Logbuches. Wenn die Logbuecher unterschiedlich sind, finde den Unterschied und korrigiere ihn.

[Fabeltier]

An Timestamps habe ich auch schon gedacht, das Problem was ich dabei hatte, war erstens ist die Aenderung in A natuerlich frueher als in B, gut, aber ich koennte den Timestamp von A nach B mitsenden. Das groessere Problem liegt eher in "finde den Unterschied" ohne die Trees durchlaufen zu muessen und ohne jedes Element aus A mit einem aus B zu vergleichen.

Der Wert muesste idealerweise gleich Aufschluss darueber geben, welches Element geaendert wurde.

[Blue-Tiger]

Fabeltier schrieb:

An Timestamps habe ich auch schon gedacht, das Problem was ich dabei hatte, war erstens ist die Aenderung in A natuerlich frueher als in B, gut, aber ich koennte den Timestamp von A nach B mitsenden. Das groessere Problem liegt eher in "finde den Unterschied" ohne die Trees durchlaufen zu muessen und ohne jedes Element aus A mit einem aus B zu vergleichen.

Der Wert muesste idealerweise gleich Aufschluss darueber geben, welches Element geaendert wurde.

Deswegen speicherst du ja nicht nur den Timestamp, sondern auch die Aktion, die an dem Zeitpunkt ausgefuehrt wurde.