Olá pessoal!
Gostaria de tirar uma duvida sobre um problema que estou tendo, no caso de uma arvore AVL que tem como base apenas objetos do tipo String, quando chamo o método padrão do percurso em ordem tenho em media 80% dos meus objetos seguindo uma ordem alfabética e outros 20% se perdem e ficam desordenados mesmo que por pouco, isso poderia acontecer talvez devido aos balanceamentos da arvore na inserção?
Segue um exemplo do código:
public class AvlTree {
private AvlNode root = null;
public AvlNode getRoot() {
return root;
}
/** Retorna a altura da árvore */
private static int height(AvlNode t) {
return t == null ? 0 : t.height;
}
/** Retorna o maior valor ente lhs e rhs. */
private static int max(int lhs, int rhs) {
return lhs > rhs ? lhs : rhs;
}
/** Retorna o fator de balanceamento da árvore com raiz t */
private int getFactor(AvlNode t) {
return height(t.left) - height(t.right);
}
private static AvlNode doRightRotation(AvlNode k2) {
AvlNode k1 = k2.left;
k2.left = k1.right;
k1.right = k2;
k2.height = max(height(k2.left), height(k2.right)) + 1;
k1.height = max(height(k1.left), k2.height) + 1;
return k1;
}
private static AvlNode doLeftRotation(AvlNode k1) {
AvlNode k2 = k1.right;
k1.right = k2.left;
k2.left = k1;
k1.height = max(height(k1.left), height(k1.right)) + 1;
k2.height = max(height(k2.right), k1.height) + 1;
return k2;
}
private static AvlNode doDoubleRightRotation(AvlNode k3) {
k3.left = doLeftRotation(k3.left);
return doRightRotation(k3);
}
private static AvlNode doDoubleLeftRotation(AvlNode k1) {
k1.right = doRightRotation(k1.right);
return doLeftRotation(k1);
}
private AvlNode insert(String x, AvlNode t) {
if (t == null)
t = new AvlNode(x, null, null);
else if (t.comparaKey(x) == 0)
t.left = insert(x, t.left);
else if (t.comparaKey(x) == 1)
t.right = insert(x, t.right);
if (getFactor(t) == 2) {
if (getFactor(t.left) > 0)
t = doRightRotation(t);
else
t = doDoubleRightRotation(t);
} else if (getFactor(t) == -2) {
if (getFactor(t.right) < 0)
t = doLeftRotation(t);
else
t = doDoubleLeftRotation(t);
}
t.height = max(height(t.left), height(t.right)) + 1;
return t;
}
public boolean insert(String x) {
// se nó já existe, retorna false
root = insert(x, root);
return true;
}
public void inorder() {
inorder(root);
}
private void inorder (AvlNode p) {
if (p != null) {
inorder(p.left);
System.out.print(p.key + "\n\r");
inorder(p.right);
}
}
}