Herauszufinden, ob ein Baum ist ein Teilbaum von anderen
https://stackoverflow.com/questions/1017821
-
06-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Es gibt zwei binäre Bäume T1 und T2, die store character data, Duplikate erlaubt.
Wie kann ich feststellen, ob der T2 ist ein Teilbaum von T1 ?.
T1 hat Millionen von Knoten und T2 verfügt über Hunderte von Knoten.
Lösung
Traverse T1. Wenn der aktuelle Knoten zu dem Wurzelknoten T2 gleich ist, durchläuft sowohl die Bäume (T2 und den aktuellen Teilbaumes T1) zur gleichen Zeit. Vergleichen Sie den aktuellen Knoten. Wenn sie immer gleich sind, T2 ist eine Teilstruktur von T1.
Andere Tipps
ich einen Algorithmus vorschlagen, dass verwendet Vorverarbeitung:
1) Pre-Prozess der T1 Baum, die Liste aller möglichen Teilbaum Wurzeln zu halten (die Liste Cache wird eine Million Einträge) hat;
2) Sortieren Sie die im Cache gespeicherten Liste der Wurzeln von der absteigenden Reihenfolge von Daten, gehalten in root. Sie können elegantere Sortierfunktion wählen, zum Beispiel, ein Zeichen Baum in Zeichenfolge analysieren.
3) Verwenden Sie binäre Suche den notwendigen Unterbaum zu finden. Sie können schnell Teilbäume, mit der Anzahl der Knoten, nicht gleich die T2 Anzahl der Knoten (oder mit unterschiedlicher Tiefe) ablehnen.
Beachten Sie, dass die Schritte 1) und 2) müssen nur einmal durchgeführt werden, dann können Sie viele Unterbaum Kandidaten testen, die gleiche vorverarbeitet belegt wird.
Wenn Sie Ihre Bäume nicht sortiert sind, in keiner Weise, ich sehe keine andere Möglichkeit, als zu tun, ein brute-force Suche:Spaziergang durch Baum T1 und überprüfen Sie, wenn Sie erreichen einen Knoten, welcher mit den ersten Knoten des Baumes T2.Wenn nicht, gehen Sie zu durchqueren T1.Wenn ja, prüfen Sie, ob der nächste Knoten entsprechen, bis Sie das Ende der T2, in diesem Fall haben Sie einen Treffer:Ihr Baum T2 in der Tat ist ein Teilbaum von T1.
Wenn Sie wissen, die Tiefe eines jeden einzelnen Knoten T1 (von Blatt-Knoten), Sie könnte überspringen Sie die Knoten, die sind nicht so tief wie die Unterstruktur, die Sie suchen.Dies könnte sparen Sie eine Menge unnötiger Vergleiche.Sagen, dass T1 und T2 ausgewogen, dann Baum T1 insgesamt Tiefe von 20 (2**20 > 1,000,000) und Baum T2 haben eine Tiefe von 7 (2**7 > 100).Sie müssen nur zu Fuß die ersten 13 Schichten von T1 (8192 Knoten-oder 14 Ebenen und 16384 Knoten?) und wird in der Lage sein zu überspringen, über 90% der T1...
Jedoch, wenn durch Teilbaum meinst du, dass das Blatt Knoten T2 sind auch Blatt-Knoten T1, dann könnte man einen ersten Durchlauf von T1 und berechnen Sie die Tiefe jedes Knotens (Entfernung von Blatt-Knoten -) und dann nur noch überprüfen Sie die Teilbäume die gleiche Tiefe wie T2.
Wenn Sie Speicher sind / Speicher gebunden (dh nicht vorge manipulieren und speichern Sie die Bäume in alternativen Formen), werden Sie wahrscheinlich nicht in der Lage sein, etwas besser als die Brute-Force-Methode von einigen anderen Antworten vorgeschlagen zu tun (Traverse P1 der Suche nach passender Wurzel von P2, die beide durchlaufen, um zu bestimmen, ob der Knoten in-Tat ist die Wurzel eines passenden Unterbaums, weiterhin mit Original-Traversal wenn es keine Übereinstimmung vorhanden ist). Diese Suche ist in O (n * m), wobei n die Größe des P1 ist und m ist die Größe der P2. Mit der Tiefe überprüft und andere mögliche Optimierungen in Abhängigkeit von den Baumdatum Sie zur Verfügung haben, wird dieser Mann ein wenig optimiert, aber es ist immer noch im allgemeinen O (n * m). Je nach Ihren spezifischen Umständen kann dies der einzige vernünftige Ansatz sein.
Wenn Sie nicht Speicher / Speicher sind gebunden und nicht ein wenig Komplexität ausmachen, glaube ich, dies zu O verbessert werden könnte (n + m) durch die Reduzierung auf einen längste gemeinsame Teilzeichen Problem mit Hilfe eines verallgemeinert Suffixbaum . Einige Diskussion über dieses für ein ähnliches Problem kann hier . Vielleicht, wenn ich mehr Zeit habe, werde ich wieder kommen und mit mehr Einzelheiten auf einer Implementierung bearbeiten.
die Wurzel beiden Bäume Falls gegeben, und da die Knoten des gleichen Typs sind, warum dann nur festzustellen, dass die Wurzel von T2 in T1 ist nicht ausreichend?
Ich gehe davon aus, dass „einen Baum T gegeben“ bedeutet einen Zeiger auf die Wurzel von T und dem Datentyp des Knotens gegeben.
Viele Grüße.
Ich bin nicht sicher, ob meine Idee richtig ist. Trotzdem für Ihre persual.
- Führen Sie einen Postorder-Spaziergang im Baum 1 Baum 2, nennt es P1 und P2.
- Vergleichen P1 & P2. Wenn sie unterschiedlich sind. Der Baum ist nicht Teilbaum. Beenden.
- Wenn sie gleich sind, oder P1 in P2 enthalten. Sie können entscheiden, welche Unterbaum ist.
Ich denke, wir mit brutalen Gewalt gehen müssen, aber warum müssen Sie die Bäume entsprechen, nachdem Sie Ihre Wurzel T2 in T1 finden. Es ist nicht gleiche, wie wenn wir nicht angeblich zu finden, wenn der Baum identisch sind. (Nur dann brauchen wir den ganzen Baum vergleichen)
Sie sind gegeben Bäume T1 und T2, Zeiger, nicht die Werte an.
, wenn der Knoten T2 (das ist ein Zeiger), in T1 Baum vorhanden ist.
Dann ist der Baum T2 Teilbaum von T1.
Edit:
Nur wenn ihr gesagt, dass T2 tatsächlich ein anderer Baum ist von Objekt weise, und das müssen wir herausfinden, ob es eine Unterstruktur in T1, der T2 identisch ist.
Dann ist diese nicht funktionieren.
Und wir haben keine andere Wahl, als für die Lösungen zu gehen hier bereits diskutiert.
Lassen Sie uns sagen, wir haben T1 als Mutterbaum und T2 als Baum, der eine Teilstruktur von T1 sein könnte. Mach Folgendes. Annahme gemacht ist T1 und T2 sind Binärbaum ohne Ausgleichsfaktor.
1) Suche die Wurzel T2 in T1. Wenn nicht T2 gefunden ist kein Teilbaum. Suchen Sie das Element in BT nimmt O (n) Zeit.
2) Wenn das Element gefunden wird, tun vorbestellbarer Traversierung von T1 von dem Knoten Wurzelelement T2 gefunden wird. Dies dauert o (n) Zeit. Haben Pre-Order Traversal von T2 als auch. Dauert O (n) Zeit. Ergebnis der Pre-Order Traversal kann in einem Stapel gespeichert werden. Eingefügt in Stapel nehmen nur O (1).
3) Wenn eine Größe von zwei Stapeln nicht gleich ist, T2 ist kein Teilbaum.
4) Pop ein Element von jedem Stapel und prüft auf Gleichheit. Wenn Nichtübereinstimmung auftritt, T2 ist kein Teilbaum.
5) Wenn alle elments angepasst T2 ist eine Unterstruktur.
Ich gehe davon aus, dass Ihr Baum ist unveränderliche Bäume , so dass Sie nie eine Unterstruktur ändern (Sie das nicht tun set-car! in Schema parlance), aber nur bauen Sie neue Bäume aus Blättern oder aus vorhandenen Bäumen.
Dann würde ich auf raten halten in jedem Knoten (oder Teilbaum) ein Hash-Code dieses Knotens. In C parlance erklären den Baum-s sein
struct tree_st {
const unsigned hash;
const bool isleaf;
union {
const char*leafstring; // when isleaf is true
struct { // when isleaf is false
const struct tree_st* left;
const struct tree_st* right;
};
};
};
dann berechnen den Hash bei Bauzeiten und wenn Knoten für die Gleichstellung erste vergleichen ihre Hash für Gleichheit zu vergleichen; die meiste Zeit der Hash-Code würde unterschiedlich sein (und Sie werden sich nicht die Mühe zu vergleichen Inhalt).
Hier ist eine mögliche Blattkonstruktion Funktion:
struct tree_st* make_leaf (const char*string) {
assert (string != NULL);
struct tree_st* t = malloc(sizeof(struct tree_st));
if (!t) { perror("malloc"); exit(EXIT_FAILURE); };
t->hash = hash_of_string(string);
t->isleaf = true;
t->leafstring = string;
return t;
}
Die Funktion einen Hash-Code zu berechnen ist
unsigned tree_hash(const struct tree_st *t) {
return (t==NULL)?0:t->hash;
}
Die Funktion eines Knotens zu konstruieren, aus zwei Teilbäumen sleft & sright ist
struct tree_st*make_node (const struct tree_st* sleft,
const struct tree_st* sright) {
struct tree_st* t = malloc(sizeof(struct tree_st));
if (!t) { perror("malloc"); exit(EXIT_FAILURE); };
/// some hashing composition, e.g.
unsigned h = (tree_hash(sleft)*313) ^ (tree_hash(sright)*617);
t->hash = h;
t->left = sleft;
t->right = sright;
return t;
}
Die Vergleichsfunktion (von zwei Bäumen tx & ty) Vorteil nehmen, dass, wenn die Hashcodes unterschiedlich sind die Komparanden unterschiedlich sind
bool equal_tree (const struct tree_st* tx, const struct tree_st* ty) {
if (tx==ty) return true;
if (tree_hash(tx) != tree_hash(ty)) return false;
if (!tx || !ty) return false;
if (tx->isleaf != ty->isleaf) return false;
if (tx->isleaf) return !strcmp(tx->leafstring, ty->leafstring);
else return equal_tree(tx->left, ty->left)
&& equal_tree(tx->right, ty->right);
}
Die meiste Zeit der tree_hash(tx) != tree_hash(ty) Test erfolgreich sein würde und Sie werden nicht Rekursion müssen.
Lesen Sie mehr über Hash consing .
Sobald Sie haben so eine effiziente Hash-basierte equal_tree Funktion können Sie die Techniken in anderen Antworten nutzen könnten erwähnt (oder in Handbuch).
Eine der Ebene Art und Weise ist is_equal () -Methode für Baum zu schreiben und die folgenden tun,
bool contains_subtree(TNode*other) {
// optimization
if(nchildren < other->nchildren) return false;
if(height < other->height) return false;
// go for real check
return is_equal(other) || (left != NULL && left->contains_subtree(other)) || (right != NULL && right->contains_subtree(other));
}
Beachten Sie, dass is_equal () kann mit Hash-Code für den Baum optimiert werden. Es kann durch Einnahme Höhe des Baumes oder die Anzahl der Kinder oder Bereichs der Werte als Hash-Code auf einfache Art und Weise durchgeführt werden.
bool is_equal(TNode*other) {
if(x != other->x) return false;
if(height != other->height) return false;
if(nchildren != other->nchildren) return false;
if(hashcode() != other->hashcode()) return false;
// do other checking for example check if the children are equal ..
}
Wenn der Baum zu einer verknüpften Liste ähnlich ist, wird es O (n) Zeit in Anspruch nehmen. Wir können auch einige Heuristik verwenden, während die Kinder die Wahl zu vergleichen.
bool contains_subtree(TNode*other) {
// optimization
if(nchildren < other->nchildren) return false;
if(height < other->height) return false;
// go for real check
if(is_equal(other)) return true;
if(left == NULL || right == NULL) {
return (left != NULL && left->contains_subtree(other)) || (right != NULL && right->contains_subtree(other));
}
if(left->nchildren < right->nchildren) { // find in smaller child tree first
return (left->contains_subtree(other)) || right->contains_subtree(other);
} else {
return (right->contains_subtree(other)) || left->contains_subtree(other);
}
}
Eine weitere Möglichkeit ist es, sowohl Struktur als Zeichenfolge serialisieren und findet, wenn die zweite Zeichenfolge (aus T2 serialisiert) Unterkette der ersten Saite ist (von T1 serialisiert).
Der folgende Code serialisiert in vorbestellen.
void serialize(ostream&strm) {
strm << x << '(';
if(left)
left->serialize(strm);
strm << ',';
if(right)
right->serialize(strm);
strm << ')';
}
Und wir können einige optimierte Algorithmus verwenden, zum Beispiel, Knuth-Morris-Pratt-Algorithmus (möglicherweise in O (n) Zeit) die Existenz der Unterkette und schließlich finden zu finden, wenn ein Baum ein Teilbaum des andere ist.
Auch hier kann die Zeichenfolge effizient mit Burrows-Wheeler_transform komprimiert werden. Und es ist möglich, bzgrep Unterkette in den komprimierten Daten zu suchen.
Eine andere Möglichkeit ist es, die Unterbäume im Baum durch Höhe und Anzahl der Kinder zu sortieren.
bool compare(TNode*other) {
if(height != other->height)
return height < other->height;
return nchildren < other->nchildren;
}
Beachten Sie, dass es wird O (n ^ 2) Teilbäume. Um die Anzahl zu reduzieren können wir einige Bereich auf der Höhe basiert. Zum Beispiel können wir nur über die Unter Bäumen der Höhe von 1000 bis 1500.
interessiert seinWenn die sortierten Daten erzeugt werden, es möglich ist, in ihm binäre Suche zu tun und finden, wenn sie Teilmenge in O (lg n) Zeit (wenn man bedenkt, dass es keine doppelte in sortierten Daten ist) ist.
