2 binäre Bäume sind gleich oder nicht [duplizieren]

Ich denke nicht, dass dies eine unvernünftige Frage ist. Eine einfache rekursive Lösung ist

Dies kann sehr teuer sein, zum Beispiel in dem Fall, wenn wir zwei große Bäume ähnlicher Form haben, bei denen alle Nicht-Blatt-Knoten den gleichen zugeordneten Wert haben und die Blattknoten von einem eine Permutation der Blattknoten eines anderen sind .

Um darüber hinaus zu kommen, könnten Sie zuerst nach links und rechts wechseln, so dass links & lt; richtig, für eine rekursive Definition von & lt ;. Dies könnte auch teuer sein, aber viel weniger als jede Permutation zu überprüfen, und ich denke, eine Wahl der Definition von & lt; würde helfen. Dies würde Ihnen dann erlauben, mit einer gewöhnlichen Definition auf Gleichheit zu prüfen.

Dieser Begriff von Ссылка gefolgt von gewöhnlicher Gleichheit löst auch Fragen darüber, ob Sie wirklich eine Äquivalenzbeziehung haben. Eine Äquivalenzrelation entspricht einer Partition. Gewöhnliche Gleichheit ist offensichtlich eine Teilung. Wenn Sie x und y vergleichen, indem Sie f (x) und f (y), gefolgt von einer Äquivalenzrelation, vergleichen, haben Sie eine Partition von x und y und damit eine Äquivalenzrelation.

Wenn Sie mehr darüber nachdenken, denke ich, dass die Kanonisierung oder Gleichwertigkeitsprüfung effizient von unten nach oben funktioniert und jeden Knoten mit einem Token annotiert, dessen Wert das Ergebnis von Vergleichen mit anderen Knoten widerspiegelt, so dass Sie kann Knoten vergleichen, und die Unterbäume unter ihnen, nur Vergleichstoken.

Der erste Schritt für die Gleichheit ist z.B. Verwenden Sie eine Hashtabelle, um jedes Blatt mit Token zu kommentieren, die nur dann gleich sind, wenn die Werte an den Blättern gleich sind. Für Knoten, deren einzige Kinder Blätter sind, verwenden Sie z.B. eine Hash-Tabelle, um weitere Token zuzuweisen, so dass die Token in diesen Knoten nur dann gleich sind, wenn die Blätter, falls vorhanden, unter diesen Knoten übereinstimmen. Dann können Sie noch einen Schritt weitergehen, und dieses Mal können Sie Token an untergeordneten Knoten vergleichen, anstatt den Baum dort wieder zu durchlaufen. Die Kosten für die Zuweisung von Tokens auf diese Weise sollten linear in der Größe der beteiligten Bäume sein. Ganz oben können Sie Bäume vergleichen, indem Sie einfach die Token an der Wurzel vergleichen.

Gleichheitsoperatoren sind transitiv: Wenn A = B und B = C, dann ist A = B = C, also A = C.

Gleichheitsoperatoren sind reflexiv: A = A, B = B und C = C, unabhängig von ihren Werten.

Gleichheitsoperatoren sind symmetrisch. Wenn A = B, dann ist B = A. (Es spielt keine Rolle, in welcher Reihenfolge sie sind.)

Sehen Sie sich nun die Definition an, die sie Ihnen gegeben haben:

Ein Baum ist gleich einem anderen Baum, wenn die Kinder gleich sind. Mal schauen. Wir können davon ausgehen, dass die Knoten unten verglichen werden, sonst ist die Definition ziemlich nutzlos. Aber sie machen sich nicht die Mühe, Ihnen zu sagen, wie Sie diesen Vergleich auflösen sollen, und die ganze Definition, die sie Ihnen gegeben haben, hängt davon ab.

Kurz gesagt, es ist eine beschissene Frage.

Lassen Sie uns sehen, was passiert, wenn wir uns entscheiden, dass wir versuchen wollen, die Frage zu lösen, though.

Aber warten Sie, sie sagen Ihnen auch, dass die zwei Kinder von jedem Baum getauscht werden können. Dies fügt die Einschränkung hinzu, dass der beliebige Baum, der einem anderen Element (einschließlich sich selbst) entspricht, seinem Spiegelbild entsprechen muss. Und alle Variationen der Kinder seiner Unterbäume werden getauscht.

Und denken Sie daran, dass dies ein Suchbaum sein soll. Daher können wir wahrscheinlich davon ausgehen, dass zwei verschiedene Suchbäume, die von demselben Algorithmus verarbeitet werden müssen dasselbe Ergebnis liefern, wenn sie gleich sind. Wenn wir also die Elemente eines Baumes umschalten, wird die Suchzeit beeinflusst. Bäume, in denen nicht alle Knoten vorhanden sind, sind nicht gleich.

Wenn wir das mit der "austauschbaren" Eigenschaft dieser Gleichheit verbinden, können wir sehen, dass es keine gültige Definition von Gleichheit ist. (Wenn wir versuchen, es anzuwenden, dann stellt sich heraus, dass nur Bäume, die für jeden Knoten auf einer bestimmten Ebene den gleichen Knoten haben, gleich sind und nur für sich selbst, was den Reflexivitätsteil eines Gleichheitsoperators durchbricht.)

Vergleiche Bäume mithilfe des Kanonisierungsansatzes, der von @mcdowella . Der Unterschied ist, dass mein Ansatz keine zusätzliche Anzahl von Knoten im Baum benötigt:

O(N) erfordert canonwalk() steps und O(N*M) memory, um alle Knoten in einem Baum zu liefern, wobei O(log(N)*M) die Gesamtzahl der Knoten, N die Anzahl der untergeordneten Knoten jedes Knotens ist (bei binären Bäumen 2 ).

M könnte leicht für jede Knotendarstellung und jede Anzahl von Kindern verallgemeinert werden. canonorder() erfordert nur, dass eine Struktur auf ihre unmittelbaren Kinder als Sequenz zugreifen kann.

Die Vergleichsfunktion, die canonwalk() aufruft:

Beispiel

Ausgabe

Ich lese die Fragen wie folgt: Geben Sie zwei Binärbäume für jede Tiefe des Baumes ein, um herauszufinden, ob ihre Kinder sich gegenseitig überdecken.

Dies kann relativ einfach codiert werden.

Lösung ohne Rekursion in Ruby

Ruby Syntax Tipps:

• (1) Element in Array einfügen: arr << elem ; In diesem Fall ist for_check ein Array von Arrays
• (2) parallele Zuweisung: t1,t2 = [item1, item2] . Wie arr = [item1, item2]; t1 = arr[0]; t2 = arr[1]
• (3) t1_children == t2_children hat das entsprechende Verhalten von == für diese Art von Objekten angenommen. Ausführlicher ist t1_children.map { |el| el.val } == t2_children.map { |el| el.val } - hier erzeugt map ein Array von Vals.