boolean Zweierpotenz = (Differenz & (Differenz – 1) == 0);

/************************************************************************************
             Visualisierung eines binären Suchbaumes in Processing
                 mithilfe des Reingold-Tilford-Algorithmus
              und Suche des LCA über den Sparse-Table-Algorithmus
                             von Thomas Kramer
                          Version 4.2 - 28.08.2012
************************************************************************************/

/* Konfiguration */
   int Baumelemente = 1000000;
   /* wenn Zentrierung aktiviert wird, werden die Mausabfragen deaktiviert */
   boolean Zentrierung = true;
   /* RMQ-Abfragen einschalten? */
   boolean RMQ_Praeprocessing = true;
   boolean RMQ_Abfragen = true;
   /* beide LCA-Routinen ausführen und somit auf Übereinstimmung checken? */
   boolean RMQ_Check = false;
   /* 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 = 100000000;
   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 */

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

/* weitere globale Variablen */
int Ebene = 0;
int EbenenInsgesamt = 0;
tBaum Wurzel = null;
tBaum kleinster_Versatz = null;
tBaum groesster_Versatz = null;
tBaum letzter_Knoten = null;
tBaum[] RMQ_E       = new tBaum[2*Baumelemente-1];
int[]   RMQ_L       = new int  [2*Baumelemente-1];
int[][] RMQ_M       = new int  [2*Baumelemente-1][(int) Math.ceil(Math.log(2*Baumelemente-1)/Math.log(2.0))];
int[]   RMQ_R       = new int  [Baumelemente];

Hashtable<Integer, Integer> elementsProcessed = new Hashtable<Integer, Integer>();
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.HashMap;
import java.util.concurrent.TimeUnit;

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++;
  }
  /*-----------------------------------------------------------------------------
   *  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();                        
    elementsProcessed.clear();
    Euler_Tour(Wurzel, -1);
    fillRMQ_R_Array();
    praeprocessM(RMQ_M, RMQ_L, 2*Baumelemente-1);   
    /* Endzeit nehmen und Ausgabe */
    nimmZeit("Erstellung der RMQ-Arrays");
    /*-----------------------------------------------------------------------------
     *  Debug-Ausgabe der RMQ-Arrays
     *-----------------------------------------------------------------------------*/         
     if (debug)
     {  
       String DebugString1;
       String DebugString2;
       String DebugString3;
       String DebugString4;   
       String DebugString5;          
       DebugString1="Index  ";
       DebugString2="RMQ_E: ";
       DebugString3="RMQ_L: ";
       DebugString5="RMQ_M: ";          
       DebugString4="RMQ_R: ";   
       for (int r=0; r<(Baumelemente*2-1); r+=1)
       {
         DebugString1+=r + ", ";
         DebugString2+=RMQ_E[r].tag + ", ";
         DebugString3+=RMQ_L[r] + ", ";  
       }
       for (int r=0; r<(Baumelemente*2-1); r++)      
       {
         for (int s=0; s<=4; s++)
         {
           DebugString5 += r + "-" + ((int) (pow(2,s))+r-1);          
           DebugString5 += "=" + RMQ_M[r][s] + ", ";         
         }
       }
       for (int r=0; r<Baumelemente; r+=1)
       {
         DebugString4+=RMQ_R[r] + ", ";
       }

       println(DebugString1);
       println(DebugString2);
       println(DebugString3);
       println(DebugString5);       
       println(DebugString4);     
     } 
    /*-----------------------------------------------------------------------------
     *  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 temp1 = 0;
      int temp2 = 0;
      boolean resultCheck = true;
      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;

        temp1 = LCA1(tag1, tag2).tag;
        if (RMQ_Check)
        {
          temp2 = LCA2(tag1, tag2).tag;       
          if (temp1 != temp2)
          {
            println("Fehler! Keine Übereinstimmung bei " + tag1 + ", " + tag2 +
                    " (LCA1-Ergebnis = " + temp1 + ", LCA2-Ergebnis = " + temp2 + ")");
            resultCheck = false;
          }
        }
        i++;
        x--;    
      }
      if (RMQ_Check && resultCheck)
      {
        println("RMQ-Check ohne Fehler ausgeführt!");
      }
      /* 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(7,8).tag, ((screen.width)/2)-20, (screen.height)-150);
    text("LCA(4,6) = " + LCA1(4,6).tag, ((screen.width)/2)-20, (screen.height)-130);
    text("LCA(3,4) = " + LCA1(3,4).tag, ((screen.width)/2)-20, (screen.height)-110);
    text("LCA(5,8) = " + LCA1(5,8).tag, ((screen.width)/2)-20, (screen.height)-90);
    text("LCA(7,9) = " + LCA1(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+1;
    Knoten.tag = tag;
    /* Versatz mit Initialisierungswerten versehen */
    Knoten.Versatz = Versatz;
    if ((Ebene + 1) > EbenenInsgesamt)
      EbenenInsgesamt = (Ebene + 1);
    /* Position im Baum abhängig zur Wurzel bestimmen */
    Knoten.Art=0;
    if (Wurzel != null)
    {
      Knoten.Art = (Inhalt < Wurzel.Inhalt) ? -1 : +1;                                 
      /* 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 += 1;
    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 -= 1;
  }
  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 * Hoehe) + (Knoten.Ebene * ZwischenAbstandOben);
  }
  else {
    GesamtPositionLinks=((screen.width / 2) - mouseX) - AbstandLinks + BenutzteFelder;
    GesamtPositionOben=((screen.height / 2) - mouseY) - AbstandOben + (Knoten.Ebene * Hoehe) + (Knoten.Ebene * 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 != 1)
    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);           
}

/* Startwert sollte bei -1 liegen */
int Euler_Tour(tBaum Knoten, int Zaehler)
{
  if (Knoten!=null)
  {
    Zaehler += 1;
    RMQ_E[Zaehler] = Knoten;
    RMQ_L[Zaehler] = Knoten.Ebene-1;  
    elementsProcessed.put(Knoten.tag, Zaehler);
    if (Knoten.links!=null)
    {
      Zaehler=Euler_Tour(Knoten.links, Zaehler)+1;
      RMQ_E[Zaehler]=Knoten;
      RMQ_L[Zaehler]=Knoten.Ebene-1;        
    }

    if (Knoten.rechts!=null)
    {
      Zaehler=Euler_Tour(Knoten.rechts, Zaehler)+1;
      RMQ_E[Zaehler]=Knoten;
      RMQ_L[Zaehler]=Knoten.Ebene-1;   
    } 
  }
  return Zaehler;
}

void praeprocessM(int[][] M, int A[], int N)
{ 
  int i, j;
  for (i = 0; i < N; i++)
  {
     M[i][0] = i;
  }

  for (j = 1; (1 << j) <= N; j++)
  {
    for (i = 0; i + (1 << j) - 1 < N; i++)
    {
      if (A[M[i][j - 1]] < A[M[i + (1 << (j - 1))][j - 1]])
      {
        M[i][j] = M[i][j - 1];
      } else {
        M[i][j] = M[i + (1 << (j - 1))][j - 1];
      }
    }
  }
}

/* fülle Repräsentanten-Array, welche das erste Vorkommen jedes Knotens enthält */
void fillRMQ_R_Array()
{
  for (int r = 0; r < Baumelemente; r += 1)
  {
    RMQ_R[r] = elementsProcessed.get(r);
  }
}

/* mittels Sparse Table-Algorithmus den Lowest Common Ancestor ermitteln */
tBaum LCA1(int tag1, int tag2)
{
  /* Suche im RMQ_R-Array zunächst die Entsprechung für tag1 und tag2 der beiden
     ausgewählten Knoten aus, suche dann innerhalb dieser Grenzen im RMQ_L-Array
     den niedrigsten Wert heraus.
     Anschließend wird im RMQ_E-Array der Wert aus dieser Indexposition zurückgegeben */
  tBaum result;
  /* Start- und Endwert für Schleife setzen */
  int start;
  int ende;
  int temp1 = RMQ_R[tag1];
  int temp2 = RMQ_R[tag2];
  if (temp1 < temp2)
  {
    start = temp1;
    ende = temp2;
  } else {
    start = temp2;
    ende = temp1;
  } 
  int r = 0; 
  int s = start;
  int lowest = Baumelemente; 
  int lowest_index = 0; 

  /* testen ob Zahl eine Zweierpotenz ist, wenn ja sparen wir das
     Schleifenkonstrukt ein */
  temp2 = ende - s; 
  if ((temp2 & (temp2 - 1)) == 0)
  {
    /* Differenz ist Zweierpotenz */
    /* Logarithmus-Bestimmung */  
    r = 0;
    while ((temp2 >>= 1) > 0)
    {
      r++;
      if ((temp2 >>= 1) > 0)
      {
        r++;
      }
      if ((temp2 >>= 1) > 0)
      {
        r++;
      }
      if ((temp2 >>= 1) > 0)
      {
        r++;
      }
    }       
    temp2 = RMQ_M[s][r];  
    temp1 = RMQ_L[temp2];
    lowest = temp1;
    lowest_index = temp2;
  } else {  
    /* Differenz ist keine Zweierpotenz */
    do
    {
      /* Logarithmus-Bestimmung */     
      r = 0;
      while ((temp2 >>= 1) > 0)
      {
        r++;
        if ((temp2 >>= 1) > 0)
        {
          r++;
        }
        if ((temp2 >>= 1) > 0)
        {
          r++;
        }
        if ((temp2 >>= 1) > 0)
        {
          r++;
        }
      }   

      temp2 = RMQ_M[s][r];  
      temp1 = RMQ_L[temp2];
      if (temp1 < lowest)
      {
        lowest = temp1;
        lowest_index = temp2;
      }     
      /* für den nächsten Schleifendurchlauf */
      s += 1 << r;
      temp2 = ende - s;     
    }
    while (s <= ende);
  }
  /* Default-Rückgabewert setzen gemäß Algorithmus */
  result = RMQ_E[lowest_index];  
  /* wenn Knoten B ein Sohn von A ist wird A gemäß Algorithmus zurückgeliefert,
     dann greift Ausnahmeregelung */ 
  if ((result.tag == tag1) || (result.tag == tag2))
    if (result.Vater != null )
       result = result.Vater;
  return result;
}

/* mittels RMQ-Algorithmus den Lowest Common Ancestor ermitteln */
tBaum LCA2(int tag1, int tag2)
{
  /* Suche im RMQ_R-Array zunächst die Entsprechung für tag1 und tag2 der beiden
     ausgewählten Knoten aus, suche dann innerhalb dieser Grenzen im RMQ_L-Array
     den niedrigsten Wert heraus.
     Anschließend wird im RMQ_E-Array der Wert aus dieser Indexposition zurückgegeben */
  int lowest=Baumelemente;
  int lowest_index=0;
  tBaum result=null;
  int start=min(RMQ_R[tag1], RMQ_R[tag2]);
  int ende=max(RMQ_R[tag1], RMQ_R[tag2]);
  int rest = (ende - start + 1) & 3;
  int endSchleife = ende - rest + 1;

  for (int i = start; i<=endSchleife - 4; i += 4)
  {
    if (RMQ_L[i]<lowest)
    {
      lowest=RMQ_L[i];
      lowest_index=i;
    }
    if (RMQ_L[i+1]<lowest)
    {
      lowest=RMQ_L[i+1];
      lowest_index=i+1;
    }   

    if (RMQ_L[i+2]<lowest)
    {
      lowest=RMQ_L[i+2];
      lowest_index=i+2;
    }

    if (RMQ_L[i+3]<lowest)
    {
      lowest=RMQ_L[i+3];
      lowest_index=i+3;
    }
  }
  // Rest abarbeiten
  if (rest > 0)
  {
    for (int i=endSchleife; i<=ende; i+=1)
    {
      if (RMQ_L[i]<lowest)
      {
        lowest=RMQ_L[i];
        lowest_index=i;
      }     
    }
  }
  /* Default-Rückgabewert setzen gemäß Algorithmus */
  result = RMQ_E[lowest_index];   
  /* wenn Knoten B ein Sohn von A ist wird A gemäß Algorithmus zurückgeliefert,
     dann greift Ausnahmeregelung */  
  if ((RMQ_E[lowest_index].tag == tag1) || (RMQ_E[lowest_index].tag == tag2))
    if (RMQ_E[lowest_index].Vater != null )
       result = RMQ_E[lowest_index].Vater;
  return result;
}

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