Ich versuche, den Nachfolger eines Schlüssels in einem binären Suchbaum in der Zeit zu finden O (1)

Question

ja ich muss sagen, das ist eine Art Hausaufgabe und ich erwarte nicht, die Antwort zu bekommen, aber ich habe keine Ahnung, wie hier fortfahren.

Ich weiß, wie man den Nachfolger und den Vorgänger auf verschiedene Arten findet, aber keiner von ihnen arbeitet in der Zeit komplex O (1).

Die Übung sagt, dass wir mehr Informationen an jedem Knoten speichern können. Die Einfüge- und Löschfunktionalität sollte jedoch zu einer komplexen Zeit von O (h) konstant sein, wobei h die Höhe des Baumes ist.

Meine erste und einfach zu implementierende Idee war, in jedem Knoten zu speichern, wie viele linke und rechte Knoten dieser Knoten haben. Also muss ich nur die Einfüge- und Löschmethode jedes Mal ändern, wenn ein Knoten übergeben wird, um diese Variablen für jeden Knoten zu erhöhen oder zu verringern. Aber ich habe keine Ahnung, wie diese Information die Zeitkomplexität von O (1) übertreffen kann.

Answer 1

Das scheint mir eine fehlerhafte Übung. Das Verfolgen des erforderlichen Schlüssels von der Wurzel aus dauert O (h) Zeit, so dass die Lösung, um den Nachfolger eines Schlüssels zu finden, O (h) + Zeit benötigen würde, um den Nachfolger zu finden.

Wenn Sie diese Tatsache ignorieren, sagen Sie, wenn Sie auf magische Weise am erforderlichen Schlüsselknoten sein sollten, können Sie nur den Vorgänger und den Vorgänger für alle Knoten speichern, um O (1) zu erreichen. Der Einfüge- und Löschhinweis ist dafür, d. H. Jedes Mal, wenn Sie einen Knoten einfügen oder aus dem Baum löschen, müssen Sie Nachfolger und Vorgänger für alle Knoten neu berechnen.

Update: Wie Yves in Kommentar darauf hingewiesen, Nachfolger wird nur für bestimmte Knoten

Answer 2

aktualisiert Wenn Sie die Vorgänger und Nachfolger in O (1) Zeit in der Lage sein zu finden, dann können Sie die Knoten verbinden in eine doppelt verknüpfte Liste zusätzlich zu verknüpfen sie in eine BST.

Dies ändert nichts an der Komplexität der Einfügeoperation, da Sie während der normalen Einfügeprozedur den Nachfolger und Vorgänger eines neuen Knotens finden. Sie müssen sich nur daran erinnern, damit Sie sie verwenden können, wenn Sie alles miteinander verbinden.

Beachten Sie, dass auch ohne die zusätzlichen Verbindungen (vorausgesetzt, Sie übergeordnete Links haben), dann den Nachfolger oder Vorgänger eines Knotens finden konstante Zeit in Anspruch nimmt im Durchschnitt, auch wenn es O (log N) Zeit im schlimmsten Fall nimmt . Aus diesem Grund werden zusätzliche Links zu Nachfolgern und Vorgängern in der Praxis nicht häufig verwendet.

Answer 3

Ja! Kann gemacht werden. Aber nutze O ​​(n) extra Platz.

Durchqueren Sie den Baum und speichern Sie die Nachfolgerinformationen in einem map (or hashmap). Dabei wird key der aktuelle Wert des Knotens und value der Wert des Folgeknotens sein. Dies verwendet O(n) Speicherplatz, aber die Zeit Komplexität zur Beantwortung Ihrer Abfrage wird immer O(1) sein.