Rot-Schwarz Bäume vereinigen < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 20:17 Mi 15.12.2010 | | Autor: | pyw |
| Aufgabe | | Geben Sie einen Algorithmus an, um zwei Rot Schwarz Bäume [mm] T_1 [/mm] und [mm] T_2 [/mm] mit insgesamt n Schlüsseln in O(n) Zeit zu vereinigen, sodass T genau die Schlüssel aus [mm] T_1 [/mm] und [mm] T_2 [/mm] enthält. |
O(n) heißt ja, dass jedes der n Elemente einmal (oder konstant) oft betrachtet wird.
Ich hab versucht, mich an ![[]](/images/popup.gif) Link zu orientieren. Das ist genau die gleiche Aufgabe (nicht von mir gestellt), aber die unten angebene Lösung ist einfach zu knapp, ich versteh sie nicht ganz. Hier noch einmal das Wesentliche, was dort steht (Zitat)
- Bäume Preorder auslesen und Schlüssel in Vektor eintragen
- Merge
- Knoten einfach hintereinander dranhängen (sind durch auslesen ja sortiert)
- die unterste Ebene des Baums rot färben
Mich wundern ein paar Dinge:
1. Die Listen/ Vektoren, von denen dort die Rede ist, sind doch nur dann (aufsteigend) wg Suchbaumeigenschaft von RS-Bäumen sortiert, wenn die Bäume inorder ausgelesen werden. Der Aufwand O(n) für das Auslesen ist klar, für jede Kante gibt es einen Aufstieg und einen Abstieg. Oder wie soll es mit preorder gehen? ...
2. Über Merge lassen sich die beiden Listen in O(n) zu einer aufsteigend sortierten Liste zusammenschmelzen (man nimmt falls noch vorhanden das jeweils kleinste Element der beiden Listen, entfernt es aus der entsprechenden Liste und fügt es in die neue Liste ein). Das ist noch klar.
Aber was ist mit den letzten beiden Punkten? Das ist irgendwie sehr vage... Ich hoffe, dass jemand mehr Verständnis auf diesem Teilgebiet aufweist als ich und mir helfen kann diese Punkte näher zu erklären oder ggf. auch den Fehler in der zitierten Lösungsskizze zu finden. Danke im Voraus!
mfg,
pyw
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:12 Do 16.12.2010 | | Autor: | pyw |
Hallo,
hat jemand eine Lösungsidee?
mfg pyw
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:20 Sa 18.12.2010 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
