Rot Schwarz -Baum < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 20:25 Do 09.12.2010 | | Autor: | pyw |
| Aufgabe | | Sei [mm] K=[k_1, [/mm] ..., [mm] k_n] [/mm] eine Folge von n paarweise verchiedenen Schlüsseln. Sei [mm] inv(K)=card\{(i, j): 1\leq ik_j\}, [/mm] d. h. die Anzahl der Inversionen in K. Wie kann man mit einem Rot-Schwarz-Baum, in welchem zu jedem inneren Knoten x die Anzahl der inneren Knoten im Teilbaum mit Wurzel x verwaltet wird, die Größe inv(K) in [mm] O(n\log [/mm] n) bestimmen? |
Hi,
leider verstehe ich nicht ganz, was damit gemeint ist, dass zu jedem inneren Knoten x die Anzahl der inneren Knoten des Teilbaums mit Wurzel verwaltet werden soll. Sollen das Extrasatellitendaten sein? Sorry, falls ich gerade komplett in die falsche Richtung denke.
Kann mir bitte jemand helfen?
mfg pyw
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 21:20 Sa 11.12.2010 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
