Finden Sie einen Algorithmus in Rbtree in O (logn)

Question

Ich muss eine Datenstruktur finden, die ich mit den folgenden Aktionen durchführen kann:

• Build (s, k) - o (nlogn)
• Suche (s, k) - o (logn)
• Einfügen (s, k) - o (logn)
• Löschen (s, k) - o (logn)
• Abnahme -UPO (S, K, D) - O (logn) - Diese Methode sollte D (d> 0) jeden Knoten subtrahieren, der <= k ist

Die offensichtliche erste Wahl war RedBlacktree.

Ich kann jedoch nicht zu einer Lösung bezüglich der Abnahme von UPO in O (logn) kommen. Was passiert, wenn k größer ist, dann die maximale Schlüssel im Baum - in diesem Fall muss ich den gesamten Baum aktualisieren.

Kann jemand etwas anderes vorschlagen? Vielleicht ein paar Tipps?

Answer 1

Sie können einen zusätzlichen Wert in jedem Knoten des Baumes speichern, nennen wir es Delta. Sie fügen Delta eines Knotens zu Schlüssel hinzu, die in all seinem Nachkommen gespeichert sind, um die tatsächlichen Schlüssel zu erhalten. Um den tatsächlichen Wert eines Schlüssels in einem bestimmten Knoten zu erhalten, summieren Sie alle Deltas vom Root zu diesem Knoten und fügen diese Summe dem gespeicherten Schlüssel hinzu.

Machen Decrease-Upto, Sie ändern nur die Deltas von O (log n) Knoten auf einem Pfad von der Root.

Sie müssen die Struktur des Baumes nach dieser Operation nicht ändern, da sich die Bestellung der Schlüssel nicht ändert.