Der binäre Baum mit Threads ist effektiv, da keine Rekursion oder ein Stack zum Durchlaufen erforderlich ist. Mein Zweifel ist, es macht jede Einfügung O (n) (wobei n die Anzahl der Knoten im Baum ist), da für jeden Knoten, den wir einfügen, es wieder eingefädelt werden muss, nicht wahr? Wenn ich recht habe, sind binäre Threads mit Threads praktisch unwirksam, oder?Insertion in Threaded Binäre Leads führt zu O (n) Zeit Komplexität?
Als Wikipedia article sagt:
„Ein binärer Baum, indem sie alle rechte Kind Zeiger einem Gewinde versehen ist, dass normalerweise Nullpunkt auf den Inorder Nachfolger des Knotens sein würde (wenn vorhanden) und alle linke Kindzeiger, die normalerweise null sind zeigen auf den Inorder-Vorgänger des Knotens. "
Der Schlüssel hier ist "das wäre normalerweise Null."
In der Regel fügen Sie entweder zusätzliche Felder für die Threadverknüpfungen ein oder Sie verwenden ein Bitflag, um zu bestimmen, ob der linke und der rechte Knoten untergeordnete Elemente sind oder den Vorgänger/Vorgänger inkorrekt sind.
Da die internen Knotenzeiger immer noch die traditionellen Links/Rechts-Binärknotenverweise sind, können Sie die rekursive Standardsuche verwenden, um einen Einfügepunkt in O (log n) -Zeit zu finden.
Danke @ jim-mischel –
@shivaR: Wenn das Ihre Frage beantwortet, bitte markieren Sie es als akzeptiert. –
Wie akzeptiere ich? :( –
Nein. Sie können den Baum immer noch rekursiv durchsuchen, um den Einfügepunkt zu finden. Die Einfügung bleibt also O (log n), vorausgesetzt, Ihr Baum wird im Gleichgewicht gehalten. –
Als eine Randnotiz vermeiden viele Bibliotheken Bäume, wenn sie Nebenläufigkeit anbieten. Das offensichtliche Beispiel ist Java [ConcurrentSkipListSet] (https://docs.oracle.com/javase/7/docs/api/java/util/concurrent/ConcurrentSkipListSet.html). – amit