Prüfen, ob 2 Baumknoten beziehen (Vorfahre/Abkömmling) in O (1) mit Vorverarbeitungseinheit

Question

Prüfen, ob 2-Baum-Knoten (dh Vorfahr-Abkömmling)

• es in O lösen verwandt sind (1) Zeit, mit O (N) -Raum (N = Anzahl der Knoten)
• Vorverarbeitung wird
erlaubt

Fertig. Ich werde zu meiner Lösung (Ansatz) gehen. Bitte hör auf, wenn du dich zuerst selbst denken willst.

---

Für eine Vorbearbeitung habe ich beschlossen, eine Pre-Order (zuerst durch die Wurzel gehen rekursiv, dann Kinder) zu tun und ein Etikett zu jedem Knoten zu geben.

Lassen Sie mich die Etiketten im Detail erklären. Jedes Etikett besteht aus durch Komma getrennten natürlichen Zahlen wie "1,2,1,4,5" - die Länge dieser Sequenz ist gleich (die Tiefe des Knotens + 1). Z.B. das Label der Wurzel ist "1", die Kinder der Wurzel haben die Beschriftungen "1,1", "1,2", "1,3" usw .. Die Knoten der nächsten Ebene haben die Bezeichnungen "1,1,1" , "1,1,2", ..., "1,2,1", "1,2,2", ...

Angenommen, "die Bestellnummer" eines Knotens ist der "1-basierten Index dieses Knotens" in der Kinderliste der Eltern.

Allgemeine Regel: Das Label des Knotens besteht aus dem übergeordneten Label gefolgt von einem Komma und "die Bestellnummer" des Knotens.

Um zu beantworten, ob zwei Knoten verwandt sind (d. H. Vorfahre-Nachkommen) in O (1), werde ich überprüfen, ob die Beschriftung eines der beiden "ein Präfix" des anderen Labels ist. Obwohl ich nicht sicher bin, ob solche Etiketten als O (N) -Raum angesehen werden können.

Alle Kritiker mit Fixes oder einem alternativen Ansatz erwartet.

Answer 1

Sie können es in O tun (n) Vorverarbeitung Zeit und O (n) Raum, mit O (1) Abfragezeit, wenn Sie speichern die Preorder Nummer und Postorder-Nummer für jede Ecke und benutzen Sie diese Tatsache:

Für zwei gegebene Knoten x und y eines Baum T, x ist ein Vorfahre von y, wenn und nur dann, wenn x bevor y erfolgt im Vorordnungsdurchquerung von T und nach y in dem Post-Order-Traversal.

(Von dieser Seite: http://www.cs.arizona.edu/xiss/numbering.htm)

Was Sie im schlimmsten Fall tat, ist Theta (d), wobei d die Tiefe des höheren Knoten ist, und ist so nicht O (1). Raum ist auch nicht O (n).

Answer 2

Es gibt lineare Zeit niedrigste gemeinsame Vorfahren Algorithmen (zumindest offline). Zum Beispiel werfen Sie einen Blick here. Sie können auch tarjan's offline LCA algorithm ansehen. Bitte beachten Sie, dass diese Artikel erfordern, dass Sie die Paare kennen, für die Sie die Ökobilanz im Voraus durchführen werden. Ich denke, es gibt auch online lineare Zeitvorberechnung Zeit Algorithmen, aber sie sind sehr komplex. Zum Beispiel gibt es einen linearen Vorberechnungszeitalgorithmus für das Abfrageproblem des Bereichsminimums. Soweit ich mich erinnere, hat diese Lösung das LCA-Problem zweimal durchlaufen.Das Problem mit dem Algorithmus ist, dass er eine so große Konstante hat, dass er eine enorme Eingabe benötigt, um tatsächlich schneller zu sein als der O (n * log (n)) Algorithmus.

Es gibt viel einfacheren Ansatz, der O (n * log (n)) zusätzlichen Speicher benötigt und erneut in konstanter Zeit antwortet.

Hoffe, das hilft.

Answer 3

Wenn Sie einen Baum betrachten, in dem ein Knoten in der Baumstruktur n/2 Kinder (sagen wir) hat, ist die Laufzeit der Beschriftungen so hoch wie O (n * n). Also wird dieses Labeling-Schema nicht funktionieren ....