Der Algorithmus kommt wie gesagt ohne die Euler-Tour und damit ohne die RMQ_E, RMQ_L und RMQ_R-Arrays aus. Man benötigt dennoch für das Präprozessing ein Array zum Zwischenspeichern der Vorgänger-Werte (RMQ_P) sowie ein Pointer-Array namens RMQ_T. Beide benötigen aber nur noch eine Länge gemäß der Anzahl Knoten und nicht mehr 2*Knoten-1, man spart also bereits etwas Arbeitsspeicher ein.
Die Vorgehensweise für die Vorverarbeitung entspricht zunächst die Höhe eines Baumes in sqrt(H)-Blöcke zu unterteilen, wobei H die Höhe eines Baumes ist. Jedem Knoten in einem Block wird dabei der tiefste Vorfahre im vorangegangenen Block zugeordnet und im RMQ_P-Array zwischengespeichert. Man benutzt dazu eine Tiefensuche mit einer Preorder-Traversierung des Baumes; die Grafik auf topcoder.com veranschaulicht das Präprozessing.
Bei der LCA-Bestimmung wird dann zuerst der tiefste gemeinsame Vorfahren-Block zweier Knoten bestimmt, und innerhalb dessen dann der endgültige LCA.
- 1. In den Funktionsköpfen wird bereits die Länge der Arrays angegeben, das ist C++-spezifisch und kann in Java so nicht übernommen werden.
- 2. Das Ergebnis einer Modulo-Abfrage mit ! auf false abzufragen funktioniert natürlich auch nicht in Java, stattdessen muss man auf >0 oder !=0 abfragen.
- 3. Wenn nur Integer-Arrays übergeben werden kann auch nicht auf die Söhne eines Knotens zugegriffen werden, das ist wohl auch der Grund warum in der dfs-Funktion “for each son k of node” steht, das ist eher sinngemäß denn syntaktisch korrekt.
- 4. Das P-Array wird von der dfs-Routine gefüllt und das T-Array muss bereits fertig übergeben werden, aber es fehlt der Quellcode wie das T-Array gefüllt wird. Es steht lediglich weiter oben “T[i] is the father of node i in the tree.”, womit lediglich die Abhängigkeiten klar sind.
- 5. Die dfs-Routine von topcoder.com sieht als Startwert 1 vor, bei mir fangen die tag-Codes bei 0 an.
Meine Modifizierungen sahen dann in Bezug auf Punkt 4 so aus dass ich in der dfs-Routine nicht nur das P, sondern auch das T-Array fülle um die Korrelation zwischen den beiden Arrays zu erfüllen. Zusätzlich übergebe ich in der Präprozessing-Routine die Objekt-Instanz jedes Knotens, um die Söhne ermitteln zu können (Punkt 3) – und ein separates Level-Array übergebe ich gar nicht mehr sondern lese diese aus dem jeweiligen Knoten aus.
Das Ergebnis funktioniert nun tatsächlich korrekt. Die Laufzeitergebnisse auf meinem Turion 64x2 1,6 GHZ-Notebook sind:
- bei 100.000 Knoten und 100.000 RMQ-Abfragen 0,027 Sekunden für das Präprozessing und 0,249 Sekunden für die RMQ-Abfragen.
- bei 500.000 Knoten und 500.000 RMQ-Abfragen 0,150 Sekunden für das Präprozessing und 7,733 Sekunden für die RMQ-Abfragen.
- bei 1.000.000 Knoten und 1.000.000 RMQ-Abfragen 0,296 Sekunden für das Präprozessing und 37,541 Sekunden für die RMQ-Abfragen.
Der Algorithmus ist damit bereits schneller als die LCA/RMQ-Routinen mit Euler-Tour und linearer Minimums-Bestimmung, gegen den namenlosen Algorithmus und den unmodifizierten Sparse Table-Algorithmus kommt er bezüglich der Gesamtlaufzeit aber nicht heran. Er hat aber den Vorteil dass die Vorverarbeitungszeit geringer ist als bei dem unmodifizierten Sparse Table-Algorithmus (nur O(N) statt O(N log(N))), aber diesen Vorteil hat auch der namenlose Algorithmus der in der Gesamtlaufzeit deutlich schneller ist.
Die anderen RMQ-Routinen lassen sich außerdem auch bei anderen Problemen als der LCA-Bestimmung einsetzen, dieser Algorithmus hier ist auf LCA beschränkt.
Insgesamt gesehen hat die Benutzung der Euler-Tour und einer RMQ-Bestimmung über das Level-Array mehr Geschwindigkeitspotenzial. Trotzdem stellt dieser Algorithmus eine interessante Alternative dar, zeigt er doch dass es auch ohne Euler-Tour geht.
Bei dieser Implementierung habe ich endlich mal die Level-Ebene jedes Knotens bei 0 statt 1 anfangen lassen zu zählen, so wie es übereinstimmend in sämtlichen Ausarbeitungen zu dem Thema stattfindet. Das ist aber nicht weiter relevant und beeinflusst die Ergebnisse nicht, wie ich betonen möchte.
/************************************************************************************
Visualisierung eines binären Suchbaumes in Processing
mithilfe des Reingold-Tilford-Algorithmus
und Suche des LCA über den alternativen Algorithmus
von Thomas Kramer
Version 2.06 - 23.08.2012
************************************************************************************/
/* Konfiguration */
int Baumelemente = 500000;
/* wenn Zentrierung aktiviert wird, werden die Mausabfragen deaktiviert */
boolean Zentrierung = true;
/* RMQ-Abfragen einschalten? */
boolean RMQ_Praeprocessing = true;
boolean RMQ_Abfragen = true;
/* debugging-Ausgabe */
boolean debug = false;
/* für Laufzeittests kann es sinnvoll sein das Zeichnen generell zu unterdrücken */
boolean zeichnen = false;
/* Zufallszahlen-Unter-/Oberwert festlegen */
int unten = 1;
int oben = 10000000;
int AbstandOben = 50;
int AbstandLinks = 10;
int ZwischenAbstandOben = 25;
int ZwischenAbstandLinks = 5;
int Breite = 160;
int Hoehe = 50;
/* Farben festlegen (Schwarz, Weiss, Hintergrund-Farbe) */
color c1 = color(0, 0, 0);
color c2 = color(255, 255, 255);
color c3 = color(193, 185, 185);
color c4 = color(245, 7, 7);
/* Konfiguration-Ende */
/* weitere globale Variablen */
int Ebene = 0;
int EbenenInsgesamt = 0;
tBaum Wurzel = null;
tBaum kleinster_Versatz = null;
tBaum groesster_Versatz = null;
tBaum letzter_Knoten = null;
int RMQ_P[] = new int [Baumelemente];
tBaum RMQ_T[] = new tBaum [Baumelemente];
HashSet<Integer> Zufallszahlen = new HashSet<Integer>();
ArrayList<tBaum> ZList = new ArrayList<tBaum>();
long completeTimeBefore = 0;
long completeTimeAfter = 0;
long completeTimeDiff = 0;
/* Variablen für das Zeichnen */
int MaxElemente = 0;
int MaxElementePlatz = 0;
int Breite_2 = Breite / 2;
int Hoehe_2 = Hoehe / 2;
int GesamtVersatz = 0;
boolean ausgegeben = false;
import java.util.concurrent.TimeUnit;
public class tBaum
{
/* in Inhalt wird der Zufallszahlen-Wert gespeichert */
int Inhalt = 0;
/* gibt die Ebene für jeden Knoten an */
int Ebene = 0;
/* Art gibt die Position des Knotens im Verhältnis zur Wurzel an
-1 = linker Teilbaum, +1 = rechter Teilbaum */
int Art = 0;
int Versatz = 0;
/* fürs Einreihen der Knoten brauche ich Zufallszahlen für zufällige
Bäume, aber für den RMQ-Algorithmus ist das unpraktisch weil für das
R-Array Knoteninhalt und Index vertauscht werden, daher Tagging-Variable */
int tag = 0;
/* Pointer für das Traversieren */
tBaum Vater = null;
tBaum links = null;
tBaum rechts = null;
/* speichert die jeweilige Tiefe des linken und des rechten Unterbaumes */
Integer linksEbenen = 0;
Integer rechtsEbenen = 0;
public int getTag()
{
return this.tag;
}
};
void setup() {
if (Baumelemente > abs(oben - unten))
throw new IllegalArgumentException("Fehler! Es werden einmalige Zufallszahlen benötigt und die Anzahl Knoten ist größer als das Zufallszahlen-Intervall!");
if ((Baumelemente * 1.2) > abs(oben - unten))
println("Achtung, die Anzahl Baumknoten ist nicht mindestens 20% größer als das Zufallszahlen-Intervall, das kann die Geschwindigkeit deutlich herabsetzen!");
/* Größe des Screens setzen */
size(screen.width, screen.height);
/* Bildschirm löschen */
background(c3);
/* Garbage Collector gezielt aufrufen damit es nicht automatisch während der Zeitmessungen geschieht */
System.gc();
/*-----------------------------------------------------------------------------
* einmalige Zufallszahlen erzeugen
*-----------------------------------------------------------------------------*/
Zufallszahlen = new HashSet<Integer>();
while (Zufallszahlen.size() < Baumelemente)
Zufallszahlen.add((int) random(unten, oben));
/*-----------------------------------------------------------------------------
* Startzeit messen für RT-Algorithmus
*-----------------------------------------------------------------------------*/
completeTimeBefore = System.currentTimeMillis();
/*-----------------------------------------------------------------------------
* Knoten erzeugen
*-----------------------------------------------------------------------------*/
int i = 0;
Iterator<Integer> it = Zufallszahlen.iterator();
ZList = new ArrayList<tBaum>();
while (it.hasNext())
{
if (i == 0)
{
Wurzel = Einfuegen(null, null, it.next(), 0, i);
/* Initialisierungswerte setzen */
kleinster_Versatz=Wurzel;
groesster_Versatz=Wurzel;
}
else {
Einfuegen(Wurzel, null, it.next(), 0, i);
ZList.add(letzter_Knoten);
}
i++;
}
println("Ebenen: " + EbenenInsgesamt);
/*-----------------------------------------------------------------------------
* Versatz berechnen
*-----------------------------------------------------------------------------*/
berechne_Versatz(Wurzel);
/* kleinsten Versatz im Baum allen Knoten aufaddieren, danach hat man
die konkrete Spaltenzahl (x-Koordinate) für jeden Knoten - beginnend mit 1 */
GesamtVersatz=abs((kleinster_Versatz).Versatz)+1;
/* das Aufaddieren geschieht jetzt direkt in der Zeichnen-Routine,
dadurch wird aber ein Teil des RT-Algorithmus nicht mehr mitgemessen! */
// setze_Wert(Wurzel, GesamtVersatz);
/*-----------------------------------------------------------------------------
* Endzeit messen für RT-Algorithmus
*-----------------------------------------------------------------------------*/
nimmZeit("RT-Algorithmus");
/*-----------------------------------------------------------------------------
* Variablen für das Zeichnen einmalig setzen
*-----------------------------------------------------------------------------*/
MaxElemente = (groesster_Versatz).Versatz + GesamtVersatz;
MaxElementePlatz = (MaxElemente * Breite)+((MaxElemente - 1) * ZwischenAbstandLinks);
/*-----------------------------------------------------------------------------
* Euler-Tour-Arrays erstellen
*-----------------------------------------------------------------------------*/
if (RMQ_Praeprocessing)
{
/* Startzeit nehmen */
completeTimeBefore = System.currentTimeMillis();
/* das eigentliche Präprozessing */
dfs(Wurzel, Wurzel.tag, Baumelemente, RMQ_P, RMQ_T, (int) sqrt(EbenenInsgesamt));
/* Endzeit nehmen und Ausgabe */
nimmZeit("Erstellung der RMQ-Arrays");
/*-----------------------------------------------------------------------------
* Debug-Ausgabe der RMQ-Arrays
*-----------------------------------------------------------------------------*/
if (debug)
{
String DebugString1;
String DebugString2;
DebugString1="Index ";
DebugString2="RMQ_P: ";
for (int r=0; r<Baumelemente; r+=1)
{
DebugString1+=r + ", ";
DebugString2+=RMQ_P[r] + ", ";
}
println(DebugString1);
println(DebugString2);
}
/*-----------------------------------------------------------------------------
* RMQ-Abfragen beantworten
*-----------------------------------------------------------------------------*/
if (RMQ_Abfragen)
{
/* Zuerst Liste mit Knoten shufflen */
Collections.shuffle(ZList);
/* Startzeit nehmen */
completeTimeBefore = System.currentTimeMillis();
int tag1 = 0;
int tag2 = 0;
int result = 0;
i = 0;
/* Wurzelknoten wurde ja nicht einbezogen, also Obergrenze = Anzahl -2 */
int x = Baumelemente -2;
/* soviele Abfragen beantworten wie Knoten-1 da sind */
while (x >= 0)
{
tag1 = ZList.get(i).tag;
tag2 = ZList.get(x).tag;
result = LCA1(RMQ_P, RMQ_T, tag1, tag2).tag;
i++;
x--;
}
/* Endzeit nehmen und Ausgabe */
nimmZeit("RMQ-Abfragen");
}
}
/*-----------------------------------------------------------------------------
* Maus auf Mittelposition setzen (innerhalb des Fensters)
*-----------------------------------------------------------------------------*/
mouseX=(screen.width/2);
mouseY=(screen.height/2);
/*-----------------------------------------------------------------------------
* erneute Aufrufe des Events draw() verhindern
*-----------------------------------------------------------------------------*/
if (Zentrierung)
noLoop();
}
void draw()
{
/*-----------------------------------------------------------------------------
* Hintergrundfarbe setzen, dabei wird auch der gesamte Bildschirm gelöscht
*-----------------------------------------------------------------------------*/
background(c3);
/*-----------------------------------------------------------------------------
* Überschriften setzen
*-----------------------------------------------------------------------------*/
fill(c2);
textSize(20);
text("Visualisierung eines binären Suchbaumes (Reingold-Tilford-Algorithmus) in Processing", ((screen.width)/2)-400, 50);
textSize(15);
text("von Thomas Kramer", ((screen.width)/2)-70, 80);
text("(ESC zum Abbrechen)", ((screen.width)/2)-75, 110);
textSize(13);
/*-----------------------------------------------------------------------------
* Baum grafisch ausgeben
*-----------------------------------------------------------------------------*/
if (zeichnen)
{
/* Startzeit nehmen */
completeTimeBefore = System.currentTimeMillis();
ZeigeBaum(Wurzel, 0, 0);
ausgegeben = true;
/* Endzeit nehmen und Ausgabe */
nimmZeit("Baumzeichnen");
}
/*-----------------------------------------------------------------------------
* RMQ-Abfragen beantworten und einzeichnen
*-----------------------------------------------------------------------------*/
if (RMQ_Abfragen)
{
text("Ermittlung des Lowest Common Ancestors anhand der Tags und des RMQ-Algorithmus", ((screen.width)/2)-240, (screen.height)-170);
text("LCA(7,8) = " + LCA1(RMQ_P, RMQ_T, 7, 8).tag, ((screen.width)/2)-20, (screen.height)-150);
text("LCA(4,6) = " + LCA1(RMQ_P, RMQ_T, 4, 6).tag, ((screen.width)/2)-20, (screen.height)-130);
text("LCA(3,4) = " + LCA1(RMQ_P, RMQ_T, 3, 4).tag, ((screen.width)/2)-20, (screen.height)-110);
text("LCA(5,8) = " + LCA1(RMQ_P, RMQ_T, 5, 8).tag, ((screen.width)/2)-20, (screen.height)-90);
text("LCA(7,9) = " + LCA1(RMQ_P, RMQ_T, 7, 9).tag, ((screen.width)/2)-20, (screen.height)-70);
}
/*-----------------------------------------------------------------------------
* aktuelle Mauskoordinaten ausgeben
*-----------------------------------------------------------------------------*/
if (!Zentrierung)
{
fill(c3);
rect(1, 0, 80, 60);
fill(c2);
text("x: " + mouseX, 20, 20);
text("y: " + mouseY, 20, 40);
}
}
void berechne_Versatz(tBaum Knoten)
{
/* PostOrder-Druchlauf -> linker Teilbaum, rechter Teilbaum, Wurzel */
if (Knoten!=null)
{
berechne_Versatz(Knoten.links);
berechne_Versatz(Knoten.rechts);
berechne_Konturen(Knoten);
}
}
void berechne_Konturen(tBaum Knoten)
{
/* berechne Konturen, nur notwendig wenn aktueller Knoten zwei Söhne hat */
if (Knoten.links!=null && Knoten.rechts!=null)
{
int linke_Kontur=0;
int rechte_Kontur=0;
/* finde die maximalen Ebenen für die Unterbäume links und rechts, separat */
/* übernimm davon den niedrigeren Wert */
int minLevelinsgesamt=min(Knoten.linksEbenen, Knoten.rechtsEbenen);
/* bestimme den maximalen und minimalen Versatz jeder Kontur bis zu der bestimmten Ebene (einschließlich) */
linke_Kontur = finde_Versatz(Knoten.links, +1, minLevelinsgesamt, (Knoten.links).Versatz);
rechte_Kontur = finde_Versatz(Knoten.rechts, -1, minLevelinsgesamt, (Knoten.rechts).Versatz);
/* Korrigierungs-Versatz berechnen */
int Versatz=((linke_Kontur-rechte_Kontur))+2;
/* Ergebnis ist ungerade? */
if ((Versatz & 1)!=0)
Versatz+=1;
/* Integer-Division */
Versatz=(Versatz>>1);
/* Test-Ausgabe */
if (Versatz <0)
println("abs()-Funktion sollte doch verwendet werden!");
/* diesen Versatz dem linken Teilbaum als negativen Wert aufaddieren, dem rechten Teilbaum
als positiven Wert */
setze_Wert(Knoten.links,-Versatz);
setze_Wert(Knoten.rechts,Versatz);
}
}
/* berechne die Tiefe der jeweiligen Kontur des Knotens */
int finde_Max_Ebene(tBaum Knoten)
{
if (Knoten == null)
return 0;
return max(finde_Max_Ebene(Knoten.links), finde_Max_Ebene(Knoten.rechts)) + 1;
}
/* finde den minimalen/maximalen Versatz für den jeweilig angegebenen
Unterbaum (Kontur) heraus - bis zu einer bestimmten Ebene (einschließlich) */
int finde_Versatz(tBaum Knoten, int Richtung, int biszuEbene, int Versatz)
{
int result=Versatz;
if (Knoten!=null)
{
/* Richtung: -1=suche Minimum, +1=suche Maximum */
if (Richtung==-1)
{
result=min(Knoten.Versatz,result);
} else
{
result=max(Knoten.Versatz,result);
}
/* noch nicht in der letzten zu berücksichtigenden Ebene? */
if (Knoten.Ebene<biszuEbene)
{
result=finde_Versatz(Knoten.links, Richtung, biszuEbene, result);
result=finde_Versatz(Knoten.rechts, Richtung, biszuEbene, result);
}
}
return result;
}
/* addiere den nach der Formel korrigierten Versatz jedem einzelnen
Knoten der angegebenen Kontur auf */
void setze_Wert(tBaum Knoten, int Wert)
{
if (Knoten!=null)
{
Knoten.Versatz+=Wert;
setze_Wert(Knoten.links,Wert);
setze_Wert(Knoten.rechts,Wert);
}
}
/* Einfügen der Knoten, Position wird in der Routine selbst bestimmt */
tBaum Einfuegen(tBaum Knoten, tBaum Vater, int Inhalt, int Versatz, int tag)
{
if (Knoten == null)
{
/* angegebener Knoten existiert noch nicht (Position noch nicht belegt)
--> neuen Knoten erzeugen */
Knoten = new tBaum();
Knoten.Vater = Vater;
Knoten.links = null;
Knoten.rechts = null;
Knoten.Inhalt = Inhalt;
Knoten.Ebene = Ebene;
Knoten.tag = tag;
/* Versatz mit Initialisierungswerten versehen */
Knoten.Versatz = Versatz;
EbenenInsgesamt = max(Ebene + 1, EbenenInsgesamt);
if (Wurzel != null)
{
/* kleinsten/größten Versatz bestimmen */
if (Knoten.Versatz < (kleinster_Versatz).Versatz)
kleinster_Versatz = Knoten;
if (Knoten.Versatz > (groesster_Versatz).Versatz)
groesster_Versatz = Knoten;
}
letzter_Knoten = Knoten;
} else
{
Ebene++;
if (Inhalt < Knoten.Inhalt)
{ /* kleineren Wert als den des aktuellen Knotens immer als linken Sohn einfügen */
Knoten.links = Einfuegen(Knoten.links, Knoten, Inhalt, Versatz-1, tag);
Knoten.linksEbenen = max(Knoten.linksEbenen, letzter_Knoten.Ebene);
}
else if (Inhalt > Knoten.Inhalt)
{ /* größeren Wert als den des aktuellen Knotens immer als rechten Sohn einfügen */
Knoten.rechts = Einfuegen(Knoten.rechts, Knoten, Inhalt, Versatz+1, tag);
Knoten.rechtsEbenen = max(Knoten.rechtsEbenen, letzter_Knoten.Ebene);
}
Ebene--;
}
return Knoten;
}
/* Baum visuell ausgeben */
void ZeigeBaum(tBaum Knoten, int StartPosKanteLinks, int StartPosKanteOben)
{
if (Knoten == null)
return;
if (!ausgegeben)
{
Knoten.Versatz += GesamtVersatz;
}
int GesamtPositionLinks = 0;
int GesamtPositionLinks_2 = 0;
int GesamtPositionOben = 0;
int GesamtPositionOben_2 = 0;
int Zentri_Space = 0;
int BenutzteFelder = (Knoten.Versatz - 1) * (Breite + ZwischenAbstandLinks);
boolean Fehler = false;
if (Zentrierung)
{
Zentri_Space = (screen.width - AbstandLinks - MaxElementePlatz) / 2;
GesamtPositionLinks = Zentri_Space + AbstandLinks + BenutzteFelder;
GesamtPositionOben=AbstandOben + ((Knoten.Ebene+1) * Hoehe) + ((Knoten.Ebene+1) * ZwischenAbstandOben);
}
else {
GesamtPositionLinks=((screen.width / 2) - mouseX) - AbstandLinks + BenutzteFelder;
GesamtPositionOben=((screen.height / 2) - mouseY) - AbstandOben + ((Knoten.Ebene+1) * Hoehe) + ((Knoten.Ebene+1) * ZwischenAbstandOben);
}
GesamtPositionLinks_2 = GesamtPositionLinks + Breite_2;
GesamtPositionOben_2 = GesamtPositionOben + Hoehe_2;
/* Erkennen, ob schon ein Knoten an die Stelle gezeichnet wurde */
color cp = get(GesamtPositionLinks + 1, GesamtPositionOben + 1);
if (cp == c2)
{
println("Fehler! Es wurde schon ein Knoten an diese Stelle gezeichnet!");
println("betreffend Knoten: " + Knoten.Inhalt);
Fehler = true;
}
/* Rahmen zeichnen */
if (Fehler)
fill(c4);
else
fill(c2);
rect(GesamtPositionLinks,
GesamtPositionOben,
Breite,
Hoehe);
/* Inhalte einzeichnen */
fill(c1);
text(Knoten.Ebene+". Ebene=" +Knoten.Inhalt + ", tag " + Knoten.tag,
GesamtPositionLinks + 5,
GesamtPositionOben + 15);
line(GesamtPositionLinks,
GesamtPositionOben_2,
GesamtPositionLinks + Breite,
GesamtPositionOben_2);
line(GesamtPositionLinks_2,
GesamtPositionOben_2,
GesamtPositionLinks_2,
GesamtPositionOben + Hoehe);
if (Knoten.links != null)
text((Knoten.links).Inhalt,
GesamtPositionLinks + 5,
GesamtPositionOben_2 + 15);
if (Knoten.rechts!=null)
text((Knoten.rechts).Inhalt,
GesamtPositionLinks_2 + 5,
GesamtPositionOben_2 + 15);
if (Knoten.Ebene != 0)
line(StartPosKanteLinks, StartPosKanteOben, GesamtPositionLinks_2, GesamtPositionOben);
/* Rekursionsaufrufe */
if (Knoten.links != null)
ZeigeBaum(Knoten.links, GesamtPositionLinks_2, GesamtPositionOben + Hoehe);
if (Knoten.rechts != null)
ZeigeBaum(Knoten.rechts, GesamtPositionLinks_2, GesamtPositionOben + Hoehe);
}
/* Präprozessing für den LCA-Algorithmus */
// dfs(Wurzel, Wurzel.tag, Baumelemente, RMQ_P, RMQ_T, (int) sqrt(EbenenInsgesamt));
void dfs(tBaum Knoten, int tag, int N, int[] P, tBaum[] T, int nr)
{
if (Knoten.Ebene < nr)
{
P[tag] = 0;
} else {
if ((Knoten.Ebene % nr) != 0)
{
P[tag] = Knoten.Vater.tag;
} else {
P[tag] = P[Knoten.Vater.tag];
}
}
T[tag] = Knoten;
if (Knoten.links != null)
dfs(Knoten.links, (Knoten.links).getTag(), N, P, T, nr);
if (Knoten.rechts != null)
dfs(Knoten.rechts, (Knoten.rechts).getTag(), N, P, T, nr);
}
/* mittels RMQ-Algorithmus den Lowest Common Ancestor ermitteln, gibt Objekt zurück */
tBaum LCA1(int P[], tBaum[] T, int x, int y)
{
tBaum result = null;
int x2 = x;
int y2 = y;
while (P[x2] != P[y2])
{
if (T[x2].Ebene > T[y2].Ebene)
{
x2 = P[x2];
} else {
y2 = P[y2];
}
}
while (x2 != y2)
{
if (T[x2].Ebene > T[y2].Ebene)
{
x2 = T[x2].Vater.tag;
} else {
y2 = T[y2].Vater.tag;
}
}
/* Default-Rückgabewert setzen gemäß Algorithmus */
result = T[x2];
/* wenn Knoten B ein Sohn von A ist wird A gemäß Algorithmus zurückgeliefert,
dann greift Ausnahmeregelung */
if ((result.tag == x) || (result.tag == y))
if (result.Vater != null)
result = result.Vater;
return result;
}
/* mittels RMQ-Algorithmus den Lowest Common Ancestor ermitteln, gibt Wert zurück,
ohne obige Ausnahmeregelung */
int LCA2(int P[], tBaum tempT[], int x2, int y2)
{
while (P[x2] != P[y2])
{
if (tempT[x2].Ebene > tempT[y2].Ebene)
{
x2 = P[x2];
} else {
y2 = P[y2];
}
}
while (x2 != y2)
{
if (tempT[x2].Ebene > tempT[y2].Ebene)
{
x2 = tempT[x2].Vater.tag;
} else {
y2 = tempT[y2].Vater.tag;
}
}
return x2;
}
/* Zeitmessung ausgeben, completeTimeBefore muss vorher separat genommen werden */
void nimmZeit(String AusgabeString)
{
completeTimeAfter = System.currentTimeMillis();
completeTimeDiff = completeTimeAfter - completeTimeBefore;
/* Ausgabe für Gesamtdurchlauf formatieren */
String timeString = String.format("\n\nZeit benötigt für %s: %02d min, %02d sec, %03d milliseconds",
AusgabeString,
TimeUnit.MILLISECONDS.toMinutes(completeTimeDiff),
TimeUnit.MILLISECONDS.toSeconds(completeTimeDiff) -
TimeUnit.MINUTES.toSeconds(TimeUnit.MILLISECONDS.toMinutes(completeTimeDiff)),
completeTimeDiff % 1000);
println(timeString);
}
