Dateisystem als Baum darstellen und Diff berechnen

[Rafael]

Hallo

Ich habe zwei Dateisystem, welche jeweils Order und Dateien enthalten.
Ich möchte nun beide Dateisysteme als Bäume darstellen damit ich dann
die Differenz bilden kann und somit feststellen kann welche Dateien
und Ordner unterschiedlich sind bzw. im einen Dateisystem vorhanden
sind aber nicht im anderen. Ich habe das Dateisystem selber entworfen,
hier ist es nur von Bedeutung, dass wir eine hierarichsche Struktur
von Ordner und Dateien haben, welche jeweils einen Namen haben.

Was für einen Baum würdet ihr da verwenden? Einen normalen n-ary tree?

Wie kann solch ein Baum aufgebaut werden, so dass er dann die Ordner-
und Filestruktur widerspiegelt? Also wie das theoretisch bei einem n-
ary tree geht weiss ich, also die inneren Knoten sind Ordner, der
jeweilige Inhalt des Ordners sind dann Kinder etc., ich habe aber mit
der Implementation etwas Mühe.

Wenn ich nun beide Bäume habe dann könnte ich ja einen normalen tree
Diff Algorithmus anwenden. Ich habe bereits früher einmal einen Diff
Algorithmus für Bäume implementiert (Zhang & Shasha’s Algorithmus),
allerdings sind diese Algorithmen für grosse Bäume sehr langsam. Da
ein Dateisystem aber sehr viele Ordner und Dateien enthalten kann und
somit die Bäume sehr gross werden können und die Differenz allerdings
trotzdem schnell berechnet werden muss, wäre dies vielleicht nicht so
geeignet.

Was könnte man denn sonst noch anwenden um die Differenz zu bestimmen
oder sollte ich gar keinen Baum verwenden?

Ich werde es übrigens in C# implementieren, wenn da vielleicht jemand
direkt eine library oder code kennt, den ich verwenden oder als
Inspiration brauchen könnte, wäre mir sehr gehollfen.

Vielen Dank.