0
The program I am running, intends to simulate a system that counts the passage of cars through gantries, for this the program receives several types of commands and does not end until receiving an empty line.
There are three types of commands, which are: PASS 00AA00 I, indicates that the vehicle registration number 00AA00 has passed through a gantry and that the payment situation when passing through the gantry is irregular.
If it is PASS 00AA00 R, in this case the car has passed through the portico as well, but its handling payment situation is regular.
the UNFLAG 00AA00, only changes the situation of ticket payment to regulate, that is, if the vehicle with that registration is in an irregular situation, passes it to regulate, if it is regular, keeps; finally we have the STATUS 00AA00, this command performs an output, by checking the number of tickets of a vehicle with registration number 00AA00 and its ticket payment status, if it does not exist, performs an output NO RECORD.
To solve this problem, I was asked to use the AVL trees and my code is as follows::
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 balanceamento;
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.balanceamento = 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;
}
public int getBalanceamento() {
return balanceamento;
}
public void setBalanceamento(int balanceamento) {
this.balanceamento = balanceamento;
}
@Override
public String toString() {
String estado;
if (estadoRegular == true) {
estado = "R";
} else {
estado = "I";
}
return matricula + " " + porticos + " " + estado;
}
}
private static No duplaRotacaoFilhoEsq(No k3)
{
k3.setFilhoEsq(rotacaoFilhoDir(k3));
return rotacaoFilhoEsq(k3);
}
private static No duplaRotacaoFilhoDir(No k3)
{
k3.setFilhoDir(rotacaoFilhoEsq(k3));
return rotacaoFilhoDir(k3);
}
private static No rotacaoFilhoDir(No k1) {
No k2 = k1.getFilhoDir();
k2.setPai(k1.getPai());
k1.setFilhoDir(k2.getFilhoEsq());
if(k1.getFilhoDir()!=null)
{
k1.getFilhoDir().setPai(k1);
}
k2.setFilhoEsq(k1);
k1.setPai(k2);
if(k2.getPai()!=null)
{
if(k2.getPai().getFilhoDir()==k1)
{
k2.getPai().setFilhoDir(k2);
}
else if(k2.getPai().getFilhoEsq()==k1)
{
k2.getPai().setFilhoEsq(k2);
}
}
balanco(k2);
balanco(k1);
return k2;
}
private static No rotacaoFilhoEsq(No k1) {
No k2 = k1.getFilhoEsq();
k2.setPai(k1.getPai());
k1.setFilhoEsq(k2.getFilhoDir());
if(k1.getFilhoEsq()!=null)
{
k1.getFilhoEsq().setPai(k1);
}
k2.setFilhoDir(k1);
k1.setPai(k2);
if(k2.getPai()!=null)
{
if(k2.getPai().getFilhoDir()==k1)
{
k2.getPai().setFilhoDir(k2);
}
else if(k2.getPai().getFilhoEsq()==k1)
{
k2.getPai().setFilhoEsq(k2);
}
}
balanco(k2);
balanco(k1);
return k2;
}
private static int altura(No aux)
{
if(aux == null)
{
return -1;
}
if(aux.getFilhoEsq() == null && aux.getFilhoDir() == null)
{
return 0;
}
else if (aux.getFilhoEsq() == null)
{
return 1 + altura(aux.getFilhoDir());
}
else if (aux.getFilhoDir() == null)
{
return 1 + altura(aux.getFilhoEsq());
}
else
return 1 + Math.max(altura(aux.getFilhoEsq()), altura(aux.getFilhoDir()));
}
private static void balanco(No tmp)
{
tmp.setBalanceamento(altura(tmp.getFilhoDir())-altura(tmp.getFilhoEsq()));
}
public static void main(String args[]) {
Scanner input = new Scanner(System.in);
String linha;
String[] aux;
ArrayList<String> output = new ArrayList<String>();
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 < 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()) < 0) {
if (aux.getFilhoDir() == null) {
novo.setPai(aux);
aux.setFilhoDir(novo);
aux=aux.getFilhoDir();
equilibra(aux);
break;
} else {
aux = aux.getFilhoDir();
numAtravessos++;
}
} else if (aux.getMatricula().compareTo(novo.getMatricula()) > 0) {
if (aux.getFilhoEsq() == null) {
novo.setPai(aux);
aux.setFilhoEsq(novo);
aux=aux.getFilhoEsq();
equilibra(aux);
break;
} else {
aux = aux.getFilhoEsq();
numAtravessos++;
}
}
}
}
public static void equilibra(No tmp) {
balanco(tmp);
int balanco = tmp.getBalanceamento();
if(balanco==-2)
{
if(altura(tmp.getFilhoEsq().getFilhoEsq())>=altura(tmp.getFilhoEsq().getFilhoDir()))
{
tmp = rotacaoFilhoEsq(tmp);
numRotacoes++;
}
else
{
tmp = duplaRotacaoFilhoDir(tmp);
numRotacoes++;
}
}
else if(balanco==2)
{
if(altura(tmp.getFilhoDir().getFilhoDir())>=altura(tmp.getFilhoDir().getFilhoEsq()))
{
tmp = rotacaoFilhoDir(tmp);
numRotacoes++;
}
else
{
tmp = duplaRotacaoFilhoEsq(tmp);
numRotacoes++;
}
}
if(tmp.getPai()!=null)
{
equilibra(tmp.getPai());
}
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()) < 0) {
if (aux.getFilhoDir() == null) {
break;
} else {
aux = aux.getFilhoDir();
numAtravessos++;
}
} else if (aux.getMatricula().compareTo(novo.getMatricula()) > 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()) < 0) {
if (aux.getFilhoDir() == null) {
return (novo.getMatricula() + " NO RECORD");
} else {
aux = aux.getFilhoDir();
numAtravessos++;
}
} else if (aux.getMatricula().compareTo(novo.getMatricula()) > 0) {
if (aux.getFilhoEsq() == null) {
return (novo.getMatricula() + " NO RECORD");
} else {
aux = aux.getFilhoEsq();
numAtravessos++;
}
}
}
}
}
The mistake I’m making is Stackoverflowerror:
Exception in thread "main" java.lang.StackOverflowError
at TP2_probB.altura(TP2_probB.java:179)
at TP2_probB.altura(TP2_probB.java:186)
at TP2_probB.altura(TP2_probB.java:186)
at TP2_probB.altura(TP2_probB.java:186)
at TP2_probB.altura(TP2_probB.java:186)
at TP2_probB.altura(TP2_probB.java:186)
at TP2_probB.altura(TP2_probB.java:186)
at TP2_probB.altura(TP2_probB.java:186)
at TP2_probB.altura(TP2_probB.java:186)
at TP2_probB.altura(TP2_probB.java:186)
at TP2_probB.altura(TP2_probB.java:186)
at TP2_probB.altura(TP2_probB.java:186)
at TP2_probB.altura(TP2_probB.java:186)
at TP2_probB.altura(TP2_probB.java:186)
at TP2_probB.altura(TP2_probB.java:186)
I have some test files available at this link https://drive.google.com/folderview?id=0B3OUu_zQ9xlGfjZHRlp6QkRkREc3dU82QmpSSWNMRlBuTUJmWTN5Ny1LaDhDN3M2WkVjYVk&usp=sharing
I hope you can help me because I have already tried to solve the problem and without any success, hence I am here asking for help from the community. Thank you.
Hello Miguel, all right? Maybe it’s better to break the problem into smaller pieces. Your stacktrace indicates that the stack is bursting in the height method. This can happen for several reasons... Looping nodes (i.e., their AVL "tree" eventually became a graph), problems with halting conditions, or even very large trees (we can increase the size of the stack with the switch
-Xss, but this is hardly a problem). I suggest you try to isolate only the height method, debug and better understand the source of the problem.– Anthony Accioly
The @Anthonyaccioly has already provided you with a precious tip. But I would also suggest that you don’t dynamically calculate the height. You can create a property for this in the node, and add 1 to the height of the parent node when adding a child node. Of course, you will also need to remember to adjust them when the tree is balanced.
– Luiz Vieira
Thank you @Anthonyaccioly for your reply I tried to increase the size of the stack, but as you say, it wouldn’t solve my problem and it didn’t. So I’m going to focus on the height method.
– Miguel Freitas
@Luizvieira thanks for your suggestion, I will do exactly that, I never remembered to have used that solution!
– Miguel Freitas