title: AVL tree in java
body: <p>The program that I am writing simulates a road charging system which reads several lines of inputs, each one representing a different command until I reach the EOF (\n). 
  This commands simulate a road charging system, where the input reads as follows:
  PASS 44AB55 I -> where the first word is the command the program receives, the second word is the number plate of the car (44AB55) and the second is the status of the car (Regular or Irregular).
  There are three types of commands:
  “PASS 00AA00 R” – Increments the number of times that the car has passed in the system and marks its status has Regular or Irreguar. If the car isnt still in the database, it inserts the car as Regular and starts the counter with one passage.
  “UNFLAG 00AA00” – Flags the car as Regular if it exists in the database. If the car doesnt exist in the database ignores the command.
  “STATUS 00AA00” – Retrieves the status of the car (Regular or Irregular) and the number of passages of the car in the system. If it the car doesnt exist in the database, prints a "NO RECORD" message. </p>
  
  <p>To solve this problem, I am using AVL trees and using the following code:</p>
  
  <pre><code>import java.util.ArrayList;
  import java.util.Scanner;
  
  public class TP2_probB {
  
      static No raiz = null;
      static double numRotacoes = 0;
      static double numAtravessos = 0;
      public static class No {
  
          private String matricula;
          private int porticos;
          private boolean estadoRegular;
          private No pai;
          private No filhoEsq;
          private No filhoDir;
          private int balanco;
  
          public No(String matricula, int porticos, boolean estadoRegular) {
              this.matricula = matricula;
              this.porticos = porticos;
              this.estadoRegular = estadoRegular;
              this.pai = null;
              this.filhoDir = null;
              this.filhoEsq = null;
              this.balanco = 0;
          }
  
          public void setEstadoRegular(boolean estadoRegular) {
              this.estadoRegular = estadoRegular;
          }
  
          public void setPai(No pai) {
              this.pai = pai;
          }
  
          public void setFilhoEsq(No filhoEsq) {
              this.filhoEsq = filhoEsq;
          }
  
          public void setFilhoDir(No filhoDir) {
              this.filhoDir = filhoDir;
          }
  
          public void atribuiNoEsq(No noEsq) {
              this.filhoEsq = noEsq;
          }
  
          public void atribuiNoDir(No noDir) {
              this.filhoDir = noDir;
          }
  
          public void atribuiPai(No noPai) {
              this.pai = noPai;
          }
  
          public void aumentaPortico() {
              porticos++;
          }
  
          public String getMatricula() {
              return matricula;
          }
  
          public boolean isEstadoRegular() {
              return estadoRegular;
          }
  
          public No getPai() {
              return pai;
          }
  
          public No getFilhoEsq() {
              return filhoEsq;
          }
  
          public No getFilhoDir() {
              return filhoDir;
          }
  
          @Override
          public String toString() {
              String estado;
              if (estadoRegular == true) {
                  estado = "R";
              } else {
                  estado = "I";
              }
              return matricula + " " + porticos + " " + estado;
          }
      }
  
      public static  No duplaRotacaoFilhoEsq(No k3)
      {
          k3.filhoEsq = rotacaoFilhoDir(k3);
          return rotacaoFilhoEsq(k3);
      }
  
      public static No duplaRotacaoFilhoDir(No k3)
      {
          k3.filhoDir = rotacaoFilhoEsq(k3);
          return rotacaoFilhoDir(k3);
      }
  
      public static No rotacaoFilhoDir(No k1) {
              No k2 = k1.filhoDir;
              k2.pai=k1.pai;
              k1.filhoDir = k2.filhoEsq;
              if(k1.filhoDir!=null)
              {
                  k1.filhoDir.pai=k1;
              }
              k2.filhoEsq = k1;
              k1.pai=k2;
              if(k2.pai!=null) 
              {
                  if(k2.pai.filhoDir==k1)
                  {
                      k2.pai.filhoDir = k2;
                  }
                  else if(k2.pai.filhoEsq==k1)
                  {
                      k2.pai.filhoEsq = k2;
                  }
              }
              balanco(k2);
              balanco(k1);
              return k2;
          }
  
      public static No rotacaoFilhoEsq(No k1) {
              No k2 = k1.filhoEsq;
              k2.pai=k1.pai;
              k1.filhoEsq = k2.filhoDir;
              if(k1.filhoEsq!=null)
              {
                  k1.filhoEsq.pai=k1;
              }
              k2.filhoDir = k1;
              k1.pai=k2;
              if(k2.pai!=null)
              {
                  if(k2.pai.filhoDir==k1)
                  {
                      k2.pai.filhoDir = k2;
                  }
                  else if(k2.pai.filhoEsq==k1)
                  {
                      k2.pai.filhoEsq = k2;
                  }
              }
              balanco(k2);
              balanco(k1);
              return k2;
          }
  
      public static int pesagem(No aux)
      {
          if(aux==null)
          {
              return -1;
          }
          if(aux.filhoEsq == null &amp;&amp; aux.filhoDir == null)
          {
              return 0;
          }
          else if ((aux.filhoEsq == null))
          {
              return (pesagem(aux.filhoDir) + 1);
          }
          else if ((aux.filhoDir == null))
          {
              return (pesagem(aux.filhoEsq) + 1);
          }
          else
              return (Math.max(pesagem(aux.filhoEsq), pesagem(aux.filhoDir)) + 1);
      }
  
      public static void balanco(No tmp)
      {
          tmp.balanco = pesagem(tmp.filhoDir)-pesagem(tmp.filhoEsq);
      }
  
      public static void main(String args[]) {
          Scanner input = new Scanner(System.in);
          String linha;
          String[] aux;
          ArrayList&lt;String&gt; output = new ArrayList&lt;String&gt;();
          int x = 0;
          while (true) {
              linha = input.nextLine();
              if (linha.isEmpty())
              {
                  break;
              }
              else
              {
                  aux = linha.split(" ");
                  if (aux[0].compareTo("PASS") == 0) {
                      No novo;
                      if (aux[2].compareTo("R") == 0) {
                          novo = new No(aux[1], 1, true);
                      } else {
                          novo = new No(aux[1], 1, false);
                      }
                      if (raiz == null) {
                          raiz = novo;
                          balanco(raiz);
                      } else {
                          procuraNo(novo);
                      }
                  } else if (aux[0].compareTo("UNFLAG") == 0) {
                      if (raiz != null) {
                          No no = new No(aux[1], 0, false);
                          mudaEstado(no);
                      }
                  } else if (aux[0].compareTo("STATUS") == 0) {
                      if (raiz == null) {
                          output.add(aux[1] + " NO RECORD");
                      } else {
                          No no = new No(aux[1], 0, false);
                          output.add(procuraRegisto(no));
                      }
                  }
              }
          }
          for (int i = 0; i &lt; output.size(); i++) {
              System.out.println(output.get(i));
          }
          System.out.println("Número de Rotações: "+numRotacoes+"\nNúmero de atravessias: "+numAtravessos);
      }
  
      public static void procuraNo(No novo) {
          No aux = raiz;
          while (true) {
              if (aux.getMatricula().compareTo(novo.getMatricula()) == 0) {
                  aux.aumentaPortico();
                  aux.setEstadoRegular(novo.isEstadoRegular());
                  equilibra(aux);
                  break;
              } else if (aux.getMatricula().compareTo(novo.getMatricula()) &lt; 0) {
                  if (aux.getFilhoDir() == null) {
                      novo.setPai(aux);
                      aux.setFilhoDir(novo);
                      aux=aux.filhoDir;
                      equilibra(aux);
                      break;
                  } else {
                      aux = aux.getFilhoDir();
                      numAtravessos++;
                  }
              } else if (aux.getMatricula().compareTo(novo.getMatricula()) &gt; 0) {
                  if (aux.getFilhoEsq() == null) {
                      novo.setPai(aux);
                      aux.setFilhoEsq(novo);
                      aux=aux.filhoEsq;
                      equilibra(aux);
                      break;
                  } else {
                      aux = aux.getFilhoEsq();
                      numAtravessos++;
                  }
              }
          }
      }
  
      public static void equilibra(No tmp) {
          balanco(tmp);
          int balanco = tmp.balanco;
          System.out.println(balanco);
          if(balanco==-2)
          {
              if(pesagem(tmp.filhoEsq.filhoEsq)&gt;=pesagem(tmp.filhoEsq.filhoDir))
              {
                  tmp = rotacaoFilhoEsq(tmp);
                  numRotacoes++;
                  System.out.println("Rodou");
              }
              else
              {
                  tmp = duplaRotacaoFilhoDir(tmp);
                  numRotacoes++;
                  System.out.println("Rodou");
              }
          }
          else if(balanco==2)
          {
              if(pesagem(tmp.filhoDir.filhoDir)&gt;=pesagem(tmp.filhoDir.filhoEsq))
              {
                  tmp = rotacaoFilhoDir(tmp);
                  numRotacoes++;
                  System.out.println("Rodou");
              }
              else
              {
                  tmp = duplaRotacaoFilhoEsq(tmp);
                  numRotacoes++;
                  System.out.println("Rodou");
              }
          }
          if(tmp.pai!=null)
          {
              equilibra(tmp.pai);
          }
          else
          {
              raiz = tmp;
          }
   }
  
      public static void mudaEstado(No novo) {
          No aux = raiz;
          while (true) {
              if (aux.getMatricula().compareTo(novo.getMatricula()) == 0) {
                  aux.setEstadoRegular(true);
                  break;
              } else if (aux.getMatricula().compareTo(novo.getMatricula()) &lt; 0) {
                  if (aux.getFilhoDir() == null) {
                      break;
                  } else {
                      aux = aux.getFilhoDir();
                      numAtravessos++;
                  }
              } else if (aux.getMatricula().compareTo(novo.getMatricula()) &gt; 0) {
                  if (aux.getFilhoEsq() == null) {
                      break;
                  } else {
                      aux = aux.getFilhoEsq();
                      numAtravessos++;
                  }
              }
          }
      }
  
      public static String procuraRegisto(No novo) {
          No aux = raiz;
          while (true) {
              if (aux.getMatricula().compareTo(novo.getMatricula()) == 0) {
                  return aux.toString();
              } else if (aux.getMatricula().compareTo(novo.getMatricula()) &lt; 0) {
                  if (aux.getFilhoDir() == null) {
                      return (novo.getMatricula() + " NO RECORD");
                  } else {
                      aux = aux.getFilhoDir();
                      numAtravessos++;
                  }
              } else if (aux.getMatricula().compareTo(novo.getMatricula()) &gt; 0) {
                  if (aux.getFilhoEsq() == null) {
                      return (novo.getMatricula() + " NO RECORD");
                  } else {
                      aux = aux.getFilhoEsq();
                      numAtravessos++;
                  }
              }
          }
      }
  }
  </code></pre>
  
  <p>The problem is that I am getting a stack overflow error:</p>
  
  <pre><code>Exception in thread "main" java.lang.StackOverflowError
      at TP2_probB.pesagem(TP2_probB.java:174)
      at TP2_probB.pesagem(TP2_probB.java:177)
      at TP2_probB.pesagem(TP2_probB.java:177)
      at TP2_probB.pesagem(TP2_probB.java:177)
      (...)
      at TP2_probB.pesagem(TP2_probB.java:177)
  </code></pre>
  
  <p>Here is a link with two files with inputs used to test the program:
  <a href="https://drive.google.com/folderview?id=0B3OUu_zQ9xlGfjZHRlp6QkRkREc3dU82QmpSSWNMRlBuTUJmWTN5Ny1LaDhDN3M2WkVjYVk&amp;usp=sharing" rel="nofollow">https://drive.google.com/folderview?id=0B3OUu_zQ9xlGfjZHRlp6QkRkREc3dU82QmpSSWNMRlBuTUJmWTN5Ny1LaDhDN3M2WkVjYVk&amp;usp=sharing</a></p>