Construct BST von vorgegebenen Preorder Traversal?

Question

Diese Frage ist von http://www.geeksforgeeks.org/construct-bst-from-given-preorder-traversa/

ich von unten einfachen Algorithmus (eine Art gleichen, dass Java für TreeMap folgt intern) denken kann

1. Wir beginnen den Knoten eins nach dem anderen hinzufügen. Beim Hinzufügen beginnen jeden Knoten mit Root-Knoten zu vergleichen und dann mit der rechten/linken Position
2. es

rekursiv entscheiden tun, aber ich erwähnt es nicht überall auf Google oder gleiche link.Per Mine sehen zu verstehen ist es Zeit, Komplexität wird sei nlog (n). Ich verstehe, es ist nicht besser als zweiter Ansatz, der O (n) ist, aber besser als der erste, der O (n^2) ist, nicht wahr?

Answer 1

Sie haben Recht, dass es besser ist als der erste Ansatz, aber der zweite Ansatz ist noch besser, da die Zeitkomplexität O (n) ist.

Der von Ihnen vorgeschlagene Ansatz wird besser, wenn Sie nicht im Voraus vollständige Eingaben haben, aber wenn Sie die vollständigen Eingaben fertig haben, müssen Sie sie nicht nacheinander hinzufügen, um den Speicherort jedes Knotens (logn) zu ermitteln. Also für n Knoten wird es sein nlog (n)