SELECTION mit Rot-Schwarz Bäumen in O(logn)?

[Sephiroth]

Hier mal eine etwas andere Frage für das Prog-Forum. :wink:

Die SELECTION Operation sollte dem einen oder anderen Informatiker bekannt sein. Sie sucht bei Eingabe einer natürlichen Zahl k das k-t größte Element einer Menge von nat. Zahlen (n Elemente). Mit Rot-Schwarz Bäumen soll das jetzt in O(logn) realisiert werden, aber ohne dabei die worst-case Laufzeit von INSERT, DELETE und SEARCH (Ops der R-S Bäume; laufen in O(logn)) zu verschlechtern.

Die ersten paar Ideen, die ich hatte liefen immer wieder auf O(nlogn) hinaus. Mir fiel jetzt zwar noch eine ein, die in O(logn) ginge (hoff ich doch mal :rolleyes:), die mag ich aber noch nicht verraten. :tongue:

Wie würdet ihr das machen?

p.s.
Wenn ich log schreibe/meine, dann bedeutet das log zur Basis 2.

[Trap]

Mit wieviel zusätzlichem Speicher? Ist die Gesamtzahl der Elemente bekannt?

Die Basis des Logarithmus ist in O-Notation egal.

[Sephiroth]

Mit wieviel zusätzlichem Speicher? Ist die Gesamtzahl der Elemente bekannt?

Speicher? Einfache, rein theoretische Überlegung.
Sagen wir n ist beliebig und größer k.


Die Basis des Logarithmus ist in O-Notation egal.
Klar, wegen der Basistransformation, es war nur die Gewohnheit ...

[Xmas]

Mit Rot-Schwarz Bäumen soll das jetzt in O(logn) realisiert werden, aber ohne dabei die worst-case Laufzeit von INSERT, DELETE und SEARCH (Ops der R-S Bäume; laufen in O(logn)) zu verschlechtern.
Also soll der Baum selbst verändert werden, oder wie soll man das verstehen?
:confused:

Die ersten paar Ideen, die ich hatte liefen immer wieder auf O(nlogn) hinaus. Mir fiel jetzt zwar noch eine ein, die in O(logn) ginge (hoff ich doch mal :rolleyes:), die mag ich aber noch nicht verraten. :tongue:

Wie würdet ihr das machen?
Wie kommst du hier auf einen O(n log( n)) Algorithmus? Selbst mit Brute Force dürftest du maximal auf O( n) kommen.

Ich würde die Anzahl der Nodes in den Unterbäumen pro Node mitspeichern. Dann kannst du ganz schnell entscheiden welchen Pfad du zum k-ten Element nehmen musst. Und beim Einfügen und Löschen dürfte das Updaten dieser Information auch nichts an der log( n)-Laufzeit ändern.

[Sephiroth]

Wie kommst du hier auf einen O(n log( n)) Algorithmus? Selbst mit Brute Force dürftest du maximal auf O( n) kommen.
Ich bin irgendwie beim Sortieren gelandet X-(


Ich würde die Anzahl der Nodes in den Unterbäumen pro Node mitspeichern. Dann kannst du ganz schnell entscheiden welchen Pfad du zum k-ten Element nehmen musst. Und beim Einfügen und Löschen dürfte das Updaten dieser Information auch nichts an der log( n)-Laufzeit ändern.
Wie? :confused:

Könnte man nicht auch das Minimum im Baum bestimmen (geht in O(logn)) und dann entsprechend oft den Nachfolger davon bestimmen?

[Trap]

Minimum und Nachfolger suchen ist nicht besser als alle durchprobieren.

Ich würd intuitiv auch sagen dass man für jeden Knoten die Anzahl der Knoten im Unterbaum speichern muss. Oder zumindest den Unterschied der Höhe des linken und rechten Unterbaums wie beim AVL-Baum.

[Xmas]

Wie? :confused:

Nehmen wir mal diesen recht unbalancierten Baum:

B2
(1) (6)
B1 R6
(2) (3)
B4 B8
(1) (1) (1)
R5 R7 R9

B(lack)/R(ed) + Wert
Die Zahlen in Klammern sind jeweils die Anzahl aller Nodes in den Subtrees. Diese hättest du in einem Standard R/B-Tree nicht, du müsstest sie hinzufügen.

Dann könntest du folgendes rekursiv tun (Python):

def select(k, node):
if k <= node.leftSubtreeSize:
return select(k, node.leftChild)
elif k == node.leftSubtree + 1:
return node
else:
return select(k - node.leftSubtreeSize - 1, node.rightChild)


Interessanterweise braucht man hier nicht mal die Zahl der Nodes im rechten Subtree. Beim Einfügen/Löschen braucht man sie aber doch.