Thomas Kramer

IT-COW | All posts tagged 'alternativer-LCA-Algorithmus'

Eine alternative Möglichkeit zur Bestimmung des Lowest Common Ancestors

By Administrator at August 28, 2012 18:27
Filed Under: Algorithmen, Java, Projekte

Der Artikel bei topcoder.com listet eine interessante Alternative zur Bestimmung des LCA auf, ohne die Benutzung der Euler-Tour eines Baumes. Der Algorithmus ist ähnlich zu dem anderen bestimmten RMQ-Verfahren.

 

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.

 

Den Quellcode habe ich im wesentlichen von topcoder.com übernommen, wobei das Prinzip auch nicht allzu schwer ist. Bei der Adaptierung auf mein Programm traten dennoch einige kleinere Probleme auf, nachfolgend zunächst der ursprüngliche Quellcode:

 

void dfs(int node, int T[MAXN], int N, int P[MAXN], int L[MAXN], int nr) {
      int k;
   
/* if node is situated in the first 
    section then P[node] = 1 
    if node is situated at the beginning 
    of some section then P[node] = T[node] 
    if none of those two cases occurs, then 
    P[node] = P[T[node]] */

    if (L[node] < nr) 
        P[node] = 1; 
    else 
        if(!(L[node] % nr)) 
            P[node] = T[node]; 
        else 
            P[node] = P[T[node]]; 
    
   for each son k of node 
       dfs(k, T, N, P, L, nr);

}

 

int LCA(int T[MAXN], int P[MAXN], int L[MAXN], int x, int y)
{
/* as long as the node in the next section of 
   x and y is not one common ancestor
   we get the node situated on the smaller 
   lever closer */
 
while (P[x] != P[y])        
  if (L[x] > L[y])
    x = P[x];
  else   y = P[y];           
 /* now they are in the same section, so we trivially compute the LCA */
while (x != y)          
  if (L[x] > L[y])           
    x = T[x];          
  else           
    y = T[y];    
return x; 
}

 

Die Probleme waren dann wie folgt:

 

- 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);    
}

 

Tag-Wolke

Monats-Liste