Trees package
Publicado: 22 Nov 2015, 14:51
por sanko
Implementación de: Arboles binarios de búsqueda y árboles AVL, clases documentadas y debidamente probadas.
BST:
-BSTNode
-BSTree
-BSTreeTest, BSTreeExhaustiveTest
BSTNode:
BSTree
BSTreeTest:
BSTreeExhaustiveTest:
Arboles AVL:
- AVLNode
- AVLTree
- AVLTreeTest
- AVLExhaustiveTreeTest
AVLNode:
BST:
-BSTNode
-BSTree
-BSTreeTest, BSTreeExhaustiveTest
BSTNode:
package arboles;
/**
* @author Esteban Montes
* @version 2015-16
*/
public class BSTNode <T extends Comparable<T>>{
private T info;
private BSTNode<T> left;
private BSTNode<T> right;
/**
* @param info Un objeto comparable
*/
public BSTNode (T info) {
setInfo(info);
setLeft(null);
setRight(null);
}
/**
* @param info La información que se quiere meter en el nodo
* Se utiliza sólo en algún caso de borrado
*/
protected void setInfo(T info) {
this.info = info;
}
/**
* @return La información que almacena el nodo
*/
public T getInfo() {
return info;
}
/**
* @param x El nodo que se quiere enlazar en el subárbol izquierdo
*/
public void setLeft(BSTNode<T> x){
this.left = x;
}
/**
* @param x El nodo que se quiere enlazar en el subárbol derecho
*/
public void setRight(BSTNode<T> x){
this.right = x;
}
/**
* @return El subárbol izquierdo
*/
public BSTNode<T> getLeft () {
return left;
}
/**
* @return El subárbol derecho
*/
public BSTNode<T> getRight () {
return right;
}
/* (non-Javadoc)
* @see java.lang.Object#toString()
*/
public String toString() {
return info.toString();
}
}package arboles;
/**
* @Author: Esteban Montes Morales
* @version 2015
*/
public class BSTree <T extends Comparable<T>>
{
private BSTNode<T> raiz;
public static void main(String args[]){
BSTree t = new BSTree();
for (int i=5;i>-5;i-=2)
t.add(i);
System.out.println(t.toString());
}
/**
* Constructor de la clase BSTree
* Por defecto es un árbol vacío
*/
public BSTree(){
raiz = null;
}
/**
* Método de acceso al valor del atributo raiz de la clase BSTree
* @return Nodo raíz del árbol
*/
public BSTNode<T> getRaiz(){
return raiz;
}
/**
* Método de modificación del valor del atributo raiz de la clase BSTree
* @param raiz Nodo raiz del árbol
*/
public void setRaiz(BSTNode<T> raiz){
this.raiz = raiz;
}
/**
* Método que inserta un nodo
* Caso base: La raíz es null y asi que asignamos al atributo raiz el nodo que queremos añadir
* Caso general: Como la raíz no es null, llama al método <<addRec()>>
* No se permite añadir el nodo si el nodo ya existe en el árbol o si se pasa información null
* @param x El objeto comparable que tiene que insertar
* @return verdadero cuando lo inserta, falso cuando no lo hace (ya existía u otra causa)
*/
public boolean add(T x){
if(x == null) return false;
if(raiz == null) raiz = new BSTNode<T>(x);
else{
try{
addRec(x, raiz);
}catch (Exception e){
return false;
}
}
return true;
}
/**
* Método envoltorio que añade un nodo de forma recursiva
* Caso de parada (1): Si el nodo es null, crea un nuevo nodo con la clave pasada por parámetro
* Caso de parada (2): Si el nodo está repetido, lanza una excepción
* Caso general: En función de que la clave sea mayor o menor, llama recursivamente a addRec con uno de los dos hijos
* @throws Exception Lanza una excepción si el nodo que intentamos añadir ya existe
*
*/
private BSTNode<T> addRec(T element, BSTNode<T> root){
if(root == null) return (new BSTNode<T>(element));
else if(element.compareTo(root.getInfo()) < 0){
root.setLeft(addRec(element, root.getLeft()));
return root;
}
else if(element.compareTo(root.getInfo()) > 0){
root.setRight(addRec(element, root.getRight()));
return root;
}
else{
root.setInfo(root.getInfo());
return root;
}
}
/**
* Método que busca un nodo
* @param x El objeto comparable que se busca
* @return El objeto que se busca (completo) si lo encuentra. (null) si no lo encuentra
*/
public T search(T x)
{
if(x == null) return null;
else return searchRec(raiz, x);
}
/**
* Método envoltorio de find() que lo convierte en recursivo
* Caso Base: El nodo al que llegamos es null
* Caso General: Comparar la clave que buscamos con el nodo al que llegamos
* @param x El objeto comparable que se busca
* @param root El nodo con el que comparamos
* @return El objeto que se busca si lo encuentra. (null) si no lo encuentra
*/
private T searchRec(BSTNode<T> root, T element)
{
if(root == null) return null;
else{
if(root.getInfo().compareTo(element) < 0) return searchRec(root.getRight(), element);
else if(root.getInfo().compareTo(element) > 0) return searchRec(root.getLeft(), element);
else return root.getInfo();
}
}
/**
* Método que borra un nodo
* Si la información que se pasa por parámetro es null, devuelve false
* @param x El objeto que se quiere borrar
* @return true si lo ha borrado, false en caso contrario (no existía)
*/
public boolean remove (T x)
{
if(x == null) return false;
else{
try {
raiz = removeRec(raiz, x);
}catch (Exception e){
return false;
}
}
return true;
}
/**
* Método envoltorio que convierte a remove() en un método recursivo
* Caso base (1): La clave del nodo al que llegamos es igual a la clave que buscamos
* Caso base (2): Encontrar null
* Caso general: Comparar el la información que queremos buscar con la clave del nodo que se nos ha pasado por parámetro
*/
private BSTNode<T> removeRec(BSTNode<T> root, T element) throws Exception
{
//El próximo día trataré de quitar las excepciones para hacerlo por paso por referencia
if(root == null) throw new Exception("El nodo no existe");
else
{
if(root.getInfo().compareTo(element) < 0) root.setRight(removeRec(root.getRight(), element));
else if (root.getInfo().compareTo(element) > 0) root.setLeft(removeRec(root.getLeft(), element));
else{
if(root.getLeft() == null && root.getRight() == null) return null;
else if(root.getLeft() != null && root.getRight() == null) return root.getLeft();
else if(root.getLeft() == null && root.getRight() != null) return root.getRight();
else{
root.setInfo(getMax(root.getLeft()));
root.setLeft(removeRec(root.getLeft(), root.getInfo()));
}
}
}
return root;
}
/**
* Método que devuelve la clave mayor de todos los nodos del árbol
* @param root Nodo raíz del árbol
* @return Clave del nodo de mayor valor
*/
protected T getMax(BSTNode<T> root){
if(root == null) return null;
else{
if(root.getRight() == null) return root.getInfo();
else return getMax(root.getRight());
}
}
/**
* Muestra por pantalla el recorrido en pre-orden (izquierda-derecha) y lo devuelve en un String (separados por tabuladores)
*/
public String preOrder()
{
return preOrderRec(raiz);
}
/**
* Método envoltorio recursivo de preOrder()
* Caso Base: No hay nodo, y por tanto devolvemos ""
* Caso General: Añadimos la clave del nodo, y llamamos recursivamente a preOrderRec con el hijo izquierdo y el derecho (si los tiene)
* @param root Nodo raíz del árbol que queremos obtener el String
* @return String con la información de todos los nodos a partir del pasado por parámetro
*/
private String preOrderRec(BSTNode<T> root)
{
if(root == null) return "";
else {
String nodeKey = root.toString();
nodeKey += "\t";
nodeKey += preOrderRec(root.getLeft());
nodeKey += preOrderRec(root.getRight());
return nodeKey;
}
}
/**
* Muestra por pantalla el recorrido en post-orden (izquierda-derecha) y lo devuelve en un String (separados por tabuladores)
*/
public String postOrder()
{
return postOrderRec(raiz);
}
/**
* Método envoltorio recursivo de postOrder()
* Caso Base: No hay nodo, y por tanto devolvemos ""
* Caso General: Llamamos recursivamente a postOrderRec con el hijo izquierdo de node (si lo tiene), añadimos la clave del nodo, y llamamos recursivamente con hijo derecho (si lo tiene)
* @param root Nodo raíz del árbol que queremos obtener el String
* @return String con la información de todos los nodos a partir del pasado por parámetro
*/
private String postOrderRec(BSTNode<T> root)
{
if(root == null) return "";
else{
String nodeKey = postOrderRec(root.getLeft());
nodeKey += postOrderRec(root.getRight());
nodeKey += root;
nodeKey += "\t";
return nodeKey;
}
}
/**
* Muestra por pantalla el recorrido en in-orden (izquierda-derecha) y lo devuelve en un String (separados por tabuladores)
*/
public String inOrder()
{
return inOrderRec(raiz);
}
/**
* Método envoltorio recursivo de inOrder()
* Caso Base: No hay nodo, y por tanto devolvemos ""
* Caso General: Llamamos recursivamente a preOrderRec con el hijo izquierdo y el derecho (si los tiene) y añadimos la clave del nodo
* @param root Nodo raíz del árbol que queremos obtener el String
* @return String con la información de todos los nodos a partir del pasado por parámetro
*/
private String inOrderRec(BSTNode<T> root)
{
if(root == null) return "";
else{
String nodeKey = inOrderRec(root.getLeft());
nodeKey += root;
nodeKey += "\t";
nodeKey += inOrderRec(root.getRight());
return nodeKey;
}
}
/**
* Genera un String con el árbol "tumbado" InOrden-derecha-izquierda y tabulando
* para mostrar los distintos niveles; utiliza el toString de la información almacenada
* @param p La raíz del árbol a generar
* @param esp El espaciado en número de tabulaciones para indicar la profundidad
* @return El String generado
*/
protected String tumbarArbol(BSTNode<T> p, int esp) {
String cadena = "";
if (p != null)
{
cadena += tumbarArbol(p.getRight(), esp + 1);
for (int i = 0; i < esp; i++)
{
cadena += "\t";
}
cadena += p + "\n";
cadena += tumbarArbol(p.getLeft(), esp + 1);
}
return cadena;
}
@Override
public String toString() {
return tumbarArbol(raiz, 0);
}
}package arboles;
/**
* @Author: Esteban Montes Morales
* @version 2015
*/
import static org.junit.Assert.*;
import org.junit.Test;
public class BSTreeTest {
@Test
/**
* Método test que comprueba el correcto funcionamiento del método add(...)
*/
public void addTest()
{
BSTree<Integer> tree = new BSTree<>();
//Pruebas Positivas
//Caso 1: Se añade un elemento al arbol de forma correcta
for(int i=0; i<5; i++){
assertTrue(tree.add(i));
//Pruebas Negativa
//Caso 1: No se pudo añadir correctamente el elemento al arbol porque ya existe
assertEquals(true, tree.add(i));
}
//Caso 2: Se intenta añadir un nulo
assertFalse(tree.add(null));
}
@Test
/**
* Método test que comprueba el correcto funcionamiento del método preOrder(...) de la clase BSTree
*/
public void preOrderTest()
{
BSTree<Integer> tree = new BSTree<Integer>();
//Pruebas positivas:
//Caso 1: Árbol vacío
assertEquals("", tree.preOrder());
//Caso 2: Sin hijos
tree.add(5);
assertEquals("5\t", tree.preOrder());
//Caso 3: Con hijos
tree.add(4);
tree.add(6);
assertEquals("5\t4\t6\t", tree.preOrder());
//Caso 3: Probamos con un arbol más complejo
BSTree<Integer> tree2 = new BSTree<Integer>();
int[] aux = {6, 4, 12, 3, 5, 9, 15, 8, 11};
for(int i: aux)
tree2.add(i);
assertEquals("6\t4\t3\t5\t12\t9\t8\t11\t15\t", tree2.preOrder());
}
@Test
/**
* Método test que comprueba el correcto funcionamiento del método inOrder(...) de la clase BSTree
*/
public void inOrderTest()
{
BSTree<Integer> tree = new BSTree<Integer>();
//Pruebas positivas:
//Caso 1: Árbol vacío
assertEquals("", tree.inOrder());
//Caso 2: raiz sin hijos
tree.add(5);
assertEquals("5\t", tree.inOrder());
//Caso 3: raíz con hijos
tree.add(4);
tree.add(6);
assertEquals("4\t5\t6\t", tree.inOrder());
//Caso 3: Probamos con un arbol más complejo
BSTree<Integer> tree2 = new BSTree<Integer>();
int[] aux = {6, 4, 12, 3, 5, 9, 15, 8, 11};
for(int i: aux)
tree2.add(i);
assertEquals("3\t4\t5\t6\t8\t9\t11\t12\t15\t", tree2.inOrder());
}
@Test
/**
* Método test que comprueba el correcto funcionamiento del método postOrder(...) de la clase BSTree
*/
public void postOrderTest()
{
BSTree<Integer> tree = new BSTree<Integer>();
//Pruebas positivas
//Caso 1: Árbol vacío
assertEquals("", tree.postOrder());
//Caso 2: sin hijos
tree.add(5);
assertEquals("5\t", tree.postOrder());
//Caso 3: con hijos
tree.add(4);
tree.add(6);
assertEquals("4\t6\t5\t", tree.postOrder());
//Caso 3: Árbol complejo
BSTree<Integer> tree2 = new BSTree<Integer>();
int[] aux = {6, 4, 12, 3, 5, 9, 15, 8, 11};
for(int i: aux)
tree2.add(i);
assertEquals("3\t5\t4\t8\t11\t9\t15\t12\t6\t", tree2.postOrder());
}
@Test
/**
* Método test que comprueba el correcto funcionamiento del método getMax(...) de la clase BSTree
*/
public void getMaxTest()
{
BSTree<Integer> tree = new BSTree<Integer>();
int[] aux = {6, 4, 12, 3, 5, 9, 15, 8, 11};
for(int i: aux)
tree.add(i);
assertEquals(new Integer(15), tree.getMax(tree.getRaiz()));
}
@Test
/**
*
*/
public void searchTest()
{
BSTree<Integer> tree2 = new BSTree<Integer>();
int[] aux = {6, 4, 12, 3, 5, 9, 15, 8, 11};
for(int i: aux){
tree2.add(i);
assertEquals(new Integer(i), tree2.search(i));
}
//Pruebas Negativas:
//Caso 1: Intentamos buscar un null
assertEquals(null, tree2.search(null));
//Caso 2: Intentamos buscar un inexistente
assertEquals(null, tree2.search(30));
}
@Test
/**
* Método test que comprueba el correcto funcionamiento del método <<remove()>>
*/
public void removeTest()
{
BSTree<Integer> tree = new BSTree<Integer>();
//Pruebas negativas
//Intentamos eliminar un nodo que no esta en el árbol
assertFalse(tree.remove(10));
//Pruebas positivas:
//Caso 1: El elemento se borra de forma correcta
tree.add(10);
tree.add(5);
tree.add(14);
tree.add(3);
tree.add(9);
tree.add(12);
tree.add(16);
assertTrue(tree.remove(5));
assertEquals("3\t9\t10\t12\t14\t16\t", tree.inOrder());
//Caso 2: Borramos el único elemento del árbol
BSTree<Integer> tree2 = new BSTree<Integer>();
tree2.add(4);
assertTrue(tree2.remove(4));
assertEquals("", tree2.inOrder());
}
}package arboles;
import static org.junit.Assert.*;
import java.io.ByteArrayOutputStream;
import java.io.PrintStream;
import java.security.InvalidParameterException;
import org.junit.After;
import org.junit.Before;
import org.junit.Test;
public class BSTreeExhaustiveTest {
boolean testsearch=true,
testRemove=true,
testRecorridos=true,
testAddNotBasic=true,
testPrint=true,
testInformacion=false,
testString=true;
static float nota=0;
static boolean enteros, estrines, informaciones;
private class Informacion implements Comparable<Informacion> {
private int clave;
private String nombre;
/**
* Constructor con 2 parámetros
*
* @param c Clave para el nodo
* @param n Elemento de información en el nodo
*/
public Informacion(int c, String n){
clave=c;
nombre=n;
}
/**
* Constructor sólo con la clave
* @param c Clave para el nodo
*
* Se utiliza cuando se quiere pasar sólo la clave para borrar o buscar
*/
public Informacion(int c) {
clave = c;
}
public int getClave() {
return clave;
}
public String getNombre() {
return nombre;
}
/* (non-Javadoc)
* @see java.lang.Comparable#compareTo(java.lang.Object)
*/
public int compareTo (Informacion elemento) {
if (elemento==null || !(elemento instanceof Informacion))
throw new InvalidParameterException("Parámetro inválido: "+elemento);
if (clave< (elemento.clave))
return -1;
else if (clave > (elemento.clave))
return 1;
else
return 0;
}
/* (non-Javadoc)
* @see java.lang.Object#equals(java.lang.Object)
*/
public boolean equals(Object n) {
if (n==null)
return false;
if (n instanceof Informacion)
return ((Informacion) n).getClave()==clave;
return false;
}
/* (non-Javadoc)
* @see java.lang.Object#toString()
*/
public String toString() {
return "["+clave+":"+nombre+"]";
}
}
BSTree<Integer> bE1;
BSTree<String> bS1;
BSTree<Informacion> bI1;
private void sumaNota(float x){
nota+=x;
}
@Test
@Before
public void testAddEnteros1() {
BSTree<Integer> bE = new BSTree<Integer>();
for (int i=5;i>-5;i-=2) {
assertTrue("add("+i+") ",bE.add(i));
assertTrue("add("+(-(i-1))+") ",bE.add(-(i-1)));
}
ByteArrayOutputStream outContent = new ByteArrayOutputStream();
PrintStream current = System.out;
System.setOut(new PrintStream(outContent));
// System.err.println(bE);
System.out.print(bE);
if (testPrint)
assertEquals(
"5\n"+
"\t\t\t4\n"+
"\t\t3\n"+
"\t\t\t\t\t2\n"+
"\t\t\t\t1\n"+
"\t\t\t\t\t0\n"+
"\t\t\t\t\t\t-1\n"+
"\t\t\t-2\n"+
"\t\t\t\t-3\n"+
"\t-4\n"
, outContent.toString());
outContent.reset();
System.setOut(current);
bE1=bE;
if (!enteros){
sumaNota(0.5f);
enteros=true;
}
}
@Test
@Before
public void testAddString1() {
BSTree<String> bS = new BSTree<String>();
String[] cad=new String[]{"40","60","20","10","90","30","50","80","70"};
if (!testString)
return;
for (int i=0;i<cad.length;i++) {
assertTrue("add("+i+") ",bS.add(cad[i]));
}
ByteArrayOutputStream outContent = new ByteArrayOutputStream();
PrintStream current = System.out;
System.setOut(new PrintStream(outContent));
System.out.print(bS);
// System.err.println(bS);
if (testPrint)
assertEquals("\t\t90\n"+
"\t\t\t80\n"+
"\t\t\t\t70\n"+
"\t60\n"+
"\t\t50\n"+
"40\n"+
"\t\t30\n"+
"\t20\n"+
"\t\t10\n"
, outContent.toString());
outContent.reset();
System.setOut(current);
bS1=bS;
if (!estrines){
sumaNota(0.5f);
estrines=true;
}
}
@Test
@Before
public void testAddInformacion1() {
BSTree<Informacion> bI = new BSTree<Informacion>();
Integer[] num=new Integer[]{1,2,0,9,7,3,5,8,6,4};
String[] cad=new String[]{"1-Uno","2-dos","0-cero","9-nueve","7-siete","3-tres","5-cinco","8-ocho","6-seis","4-cuatro"};
ByteArrayOutputStream outContent = new ByteArrayOutputStream();
PrintStream current = System.out;
System.setOut(new PrintStream(outContent));
if (!testInformacion)
return;
for (int i=0;i<cad.length;i++) { // Inserta bien solo clave
assertTrue(bI.add(new Informacion(num[i])));
}
System.out.print(bI);
// System.err.println(bI);
if (testPrint)
assertEquals("\t\t[9:null]\n"+
"\t\t\t\t[8:null]\n"+
"\t\t\t[7:null]\n"+
"\t\t\t\t\t\t[6:null]\n"+
"\t\t\t\t\t[5:null]\n"+
"\t\t\t\t\t\t[4:null]\n"+
"\t\t\t\t[3:null]\n"+
"\t[2:null]\n"+
"[1:null]\n"+
"\t[0:null]\n"
, outContent.toString());
outContent.reset();
if (testsearch)
for (int i=0;i<cad.length;i++) { //
assertNull("search["+cad[i]+"]: ",(bI.search(new Informacion(num[i])).getNombre()));
}
for (int i=0;i<cad.length;i++) { // Inserta bien clave y nombre
assertTrue(bI.add(new Informacion(num[i],cad[i])));
}
System.out.print(bI);
// System.err.println(bI);
if (testPrint)
assertEquals("\t\t[9:9-nueve]\n" +
"\t\t\t\t[8:8-ocho]\n"+
"\t\t\t[7:7-siete]\n"+
"\t\t\t\t\t\t[6:6-seis]\n"+
"\t\t\t\t\t[5:5-cinco]\n"+
"\t\t\t\t\t\t[4:4-cuatro]\n"+
"\t\t\t\t[3:3-tres]\n"+
"\t[2:2-dos]\n"+
"[1:1-Uno]\n"+
"\t[0:0-cero]\n"
, outContent.toString());
outContent.reset();
System.setOut(current);
if (testsearch)
for (int i=0;i<cad.length;i++) { //
assertEquals("search["+cad[i]+"]: ",cad[i],(bI.search(new Informacion(num[i])).getNombre()));
}
bI1=bI;
if (!informaciones){
sumaNota(0.5f);
informaciones=true;
}
}
@Test
public void testRecorridosE1() {
BSTree<Integer> bE =bE1;
String res;
if (!testRecorridos)
fail();
// System.err.println(bE);
res=bE.inOrder();
assertEquals("-4\t-3\t-2\t-1\t0\t1\t2\t3\t4\t5\t",res);
res=bE.preOrder();
assertEquals("5\t-4\t3\t-2\t-3\t1\t0\t-1\t2\t4\t",res);
res=bE.postOrder();
assertEquals("-3\t-1\t0\t2\t1\t-2\t4\t3\t-4\t5\t",res);
sumaNota(0.5f);
}
@Test
public void testRecorridosS1() {
BSTree<String> bS = bS1;
String res;
if (!testString || !testRecorridos)
fail();
// System.err.println(bS);
res=bS.inOrder();
assertEquals("10\t20\t30\t40\t50\t60\t70\t80\t90\t",res);
res=bS.preOrder();
assertEquals("40\t20\t10\t30\t60\t50\t90\t80\t70\t",res);
res=bS.postOrder();
assertEquals("10\t30\t20\t50\t70\t80\t90\t60\t40\t",res);
sumaNota(0.5f);
}
@Test
public void testRecorridosInf1() {
BSTree<Informacion> bI = bI1;
String res;
if (!testInformacion || !testRecorridos)
fail();
System.err.println(bI);
res=bI.inOrder();
assertEquals("[0:0-cero]\t[1:1-Uno]\t[2:2-dos]\t[3:3-tres]\t[4:4-cuatro]\t[5:5-cinco]\t[6:6-seis]\t[7:7-siete]\t[8:8-ocho]\t[9:9-nueve]\t",res);
res=bI.preOrder();
assertEquals("[1:1-Uno]\t[0:0-cero]\t[2:2-dos]\t[9:9-nueve]\t[7:7-siete]\t[3:3-tres]\t[5:5-cinco]\t[4:4-cuatro]\t[6:6-seis]\t[8:8-ocho]\t",res);
res=bI.postOrder();
assertEquals("[0:0-cero]\t[4:4-cuatro]\t[6:6-seis]\t[5:5-cinco]\t[3:3-tres]\t[8:8-ocho]\t[7:7-siete]\t[9:9-nueve]\t[2:2-dos]\t[1:1-Uno]\t",res);
sumaNota(0.5f);
}
@Test
public void testVariados() {
BSTree<Integer> b = new BSTree<Integer>();
String res;
if (testAddNotBasic) assertFalse(b.add(null));
if (testRemove) {
assertFalse(b.remove(null));
assertFalse(b.remove(0));
}
for (int i=1;i<10;i++) {
if (testsearch) assertEquals("search("+i+")",null,b.search(i));
if (testRemove) assertFalse("remove("+i+") ",b.remove(i));
assertTrue("add("+i+") ",b.add(i));
assertTrue("add("+(-i)+") ",b.add(-20-i));
if (testAddNotBasic) {
assertTrue("add("+i+") ",b.add(i));
assertTrue("add("+(-i)+") ",b.add(-20-i));
}
}
if (testRecorridos){
// System.err.println(b);
res=b.inOrder();
assertEquals("-29\t-28\t-27\t-26\t-25\t-24\t-23\t-22\t-21\t1\t2\t3\t4\t5\t6\t7\t8\t9\t",res);
res=b.preOrder();
assertEquals("1\t-21\t-22\t-23\t-24\t-25\t-26\t-27\t-28\t-29\t2\t3\t4\t5\t6\t7\t8\t9\t",res);
res=b.postOrder();
assertEquals("-29\t-28\t-27\t-26\t-25\t-24\t-23\t-22\t-21\t9\t8\t7\t6\t5\t4\t3\t2\t1\t",res);
}
for (int i=10;i<20;i++) {
if (testsearch) assertEquals("search("+i+")",null,b.search(i));
if (testRemove) assertFalse("remove("+i+") ",b.remove(i));
assertTrue("add("+i+") ",b.add(-i));
assertTrue("add("+(-i)+") ",b.add(10-i));
if (testAddNotBasic) {
assertTrue("add("+i+") ",b.add(-i));
assertTrue("add("+(-i)+") ",b.add(10-i));
}
}
if (testRecorridos){
// System.err.println(b);
res=b.inOrder();
assertEquals("-29\t-28\t-27\t-26\t-25\t-24\t-23\t-22\t-21\t-19\t-18\t-17\t-16\t-15\t-14\t-13\t-12\t-11\t-10\t-9\t-8\t-7\t-6\t-5\t-4\t-3\t-2\t-1\t0\t1\t2\t3\t4\t5\t6\t7\t8\t9\t",res);
res=b.preOrder();
assertEquals("1\t-21\t-22\t-23\t-24\t-25\t-26\t-27\t-28\t-29\t-10\t-11\t-12\t-13\t-14\t-15\t-16\t-17\t-18\t-19\t0\t-1\t-2\t-3\t-4\t-5\t-6\t-7\t-8\t-9\t2\t3\t4\t5\t6\t7\t8\t9\t",res);
res=b.postOrder();
assertEquals("-29\t-28\t-27\t-26\t-25\t-24\t-23\t-22\t-19\t-18\t-17\t-16\t-15\t-14\t-13\t-12\t-11\t-9\t-8\t-7\t-6\t-5\t-4\t-3\t-2\t-1\t0\t-10\t-21\t9\t8\t7\t6\t5\t4\t3\t2\t1\t",res);
}
if (testRemove) {
assertFalse(b.remove(null));
assertTrue(b.remove(0));
assertFalse(b.remove(0));
// System.err.println(b);
if (testRecorridos){
res=b.inOrder();
assertEquals("-29\t-28\t-27\t-26\t-25\t-24\t-23\t-22\t-21\t-19\t-18\t-17\t-16\t-15\t-14\t-13\t-12\t-11\t-10\t-9\t-8\t-7\t-6\t-5\t-4\t-3\t-2\t-1\t1\t2\t3\t4\t5\t6\t7\t8\t9\t",res);
res=b.preOrder();
assertEquals("1\t-21\t-22\t-23\t-24\t-25\t-26\t-27\t-28\t-29\t-10\t-11\t-12\t-13\t-14\t-15\t-16\t-17\t-18\t-19\t-1\t-2\t-3\t-4\t-5\t-6\t-7\t-8\t-9\t2\t3\t4\t5\t6\t7\t8\t9\t",res);
res=b.postOrder();
assertEquals("-29\t-28\t-27\t-26\t-25\t-24\t-23\t-22\t-19\t-18\t-17\t-16\t-15\t-14\t-13\t-12\t-11\t-9\t-8\t-7\t-6\t-5\t-4\t-3\t-2\t-1\t-10\t-21\t9\t8\t7\t6\t5\t4\t3\t2\t1\t",res);
}
assertTrue(b.remove(-19));
assertFalse(b.remove(-19));
assertTrue(b.remove(-10));
assertFalse(b.remove(-10));
assertTrue(b.remove(5));
assertFalse(b.remove(5));
if (testRecorridos){
// System.err.println(b);
res=b.inOrder();
assertEquals("-29\t-28\t-27\t-26\t-25\t-24\t-23\t-22\t-21\t-18\t-17\t-16\t-15\t-14\t-13\t-12\t-11\t-9\t-8\t-7\t-6\t-5\t-4\t-3\t-2\t-1\t1\t2\t3\t4\t6\t7\t8\t9\t",res);
res=b.preOrder();
assertEquals("1\t-21\t-22\t-23\t-24\t-25\t-26\t-27\t-28\t-29\t-11\t-12\t-13\t-14\t-15\t-16\t-17\t-18\t-1\t-2\t-3\t-4\t-5\t-6\t-7\t-8\t-9\t2\t3\t4\t6\t7\t8\t9\t",res);
res=b.postOrder();
assertEquals("-29\t-28\t-27\t-26\t-25\t-24\t-23\t-22\t-18\t-17\t-16\t-15\t-14\t-13\t-12\t-9\t-8\t-7\t-6\t-5\t-4\t-3\t-2\t-1\t-11\t-21\t9\t8\t7\t6\t4\t3\t2\t1\t",res);
}
for (int i=-30;i<30;i++){
if (testsearch)
if (b.search(i)==null)
assertFalse("remove("+i+") ",b.remove(i));
else
assertTrue("remove("+i+") ",b.remove(i));
else
if (b.remove(i))
System.err.println("remove("+i+") es TRUE");
else
System.err.println("remove("+i+") es FALSE");
if (i==0)
if (testRecorridos){
res=b.inOrder();
assertEquals("1\t2\t3\t4\t6\t7\t8\t9\t",res);
res=b.preOrder();
assertEquals("1\t2\t3\t4\t6\t7\t8\t9\t",res);
res=b.postOrder();
assertEquals("9\t8\t7\t6\t4\t3\t2\t1\t",res);
}
else
System.err.println(b);
}
if (testRecorridos){
res=b.inOrder();
assertEquals("",res);
res=b.preOrder();
assertEquals("",res);
res=b.postOrder();
assertEquals("",res);
}
}
sumaNota(1);
}
@Test
public void testRemoveE1() {
BSTree<Integer> b = bE1;
String res;
if ( !testRemove)
fail();
ByteArrayOutputStream outContent = new ByteArrayOutputStream();
PrintStream current = System.out;
System.setOut(new PrintStream(outContent));
assertTrue("remove(5) ",b.remove(5));
for (int i=4;i!=3;i--) {
assertTrue("remove("+i+") ",b.remove(i));
assertTrue("remove("+(-i)+") ",b.remove(-i));
}
// System.err.println(b);
System.out.print(b);
if (testPrint)
assertEquals(
"3\n"+
"\t\t\t2\n"+
"\t\t1\n"+
"\t\t\t0\n"+
"\t\t\t\t-1\n"+
"\t-2\n"+
"\t\t-3\n"
, outContent.toString());
outContent.reset();
if (testRecorridos) {
res=b.inOrder();
assertEquals("-3\t-2\t-1\t0\t1\t2\t3\t",res);
res=b.preOrder();
assertEquals("3\t-2\t-3\t1\t0\t-1\t2\t",res);
res=b.postOrder();
assertEquals("-3\t-1\t0\t2\t1\t-2\t3\t",res);
}
assertTrue("remove("+1+") ",b.remove(1));
assertTrue("remove("+(-1)+") ",b.remove(-1));
// System.err.println(b);
System.out.print(b);
if (testPrint)
assertEquals(
"3\n"+
"\t\t\t2\n"+
"\t\t0\n"+
"\t-2\n"+
"\t\t-3\n"
, outContent.toString());
outContent.reset();
if (testRecorridos) {
res=b.inOrder();
assertEquals("-3\t-2\t0\t2\t3\t",res);
res=b.preOrder();
assertEquals("3\t-2\t-3\t0\t2\t",res);
res=b.postOrder();
assertEquals("-3\t2\t0\t-2\t3\t",res);
}
for (int i=2;i<=3;i++) {
assertTrue("remove("+i+") ",b.remove(i));
assertTrue("remove("+(-i)+") ",b.remove(-i));
}
// System.err.println(b);
System.out.print(b);
if (testPrint)
assertEquals(
"0\n"
, outContent.toString());
outContent.reset();
if (testRecorridos) {
res=b.inOrder();
assertEquals("0\t",res);
res=b.preOrder();
assertEquals("0\t",res);
res=b.postOrder();
assertEquals("0\t",res);
}
System.setOut(current);
sumaNota(1);
}
@Test
public void testRemoveS1() {
BSTree<String> b = bS1;
String res;
int sig=0;
String[] cad=new String[]{"40","60","20","10","90","30","50","80","70"};
int [] orden=new int[]{0,1,6,8,5,4,7,2,3};
if (!testString || !testRemove)
fail();
ByteArrayOutputStream outContent = new ByteArrayOutputStream();
PrintStream current = System.out;
System.setOut(new PrintStream(outContent));
// System.err.println(b);
for (;sig<=2;sig++) {
assertTrue("remove("+cad[orden[sig]]+") ",b.remove(cad[orden[sig]]));
}
// System.err.println(b);
System.out.print(b);
if (testPrint)
assertEquals(
"\t90\n"+
"\t\t80\n"+
"\t\t\t70\n"+
"30\n"+
"\t20\n"+
"\t\t10\n"
, outContent.toString());
outContent.reset();
if (testRecorridos) {
res=b.inOrder();
assertEquals("10\t20\t30\t70\t80\t90\t",res);
res=b.preOrder();
assertEquals("30\t20\t10\t90\t80\t70\t",res);
res=b.postOrder();
assertEquals("10\t20\t70\t80\t90\t30\t",res);
}
assertTrue("remove("+cad[orden[sig]]+") ",b.remove(cad[orden[sig]]));
sig++;
// System.err.println(b);fail();
System.out.print(b);
if (testPrint)
assertEquals(
"\t90\n"+
"\t\t80\n"+
"30\n"+
"\t20\n"+
"\t\t10\n"
, outContent.toString());
outContent.reset();
if (testRecorridos) {
res=b.inOrder();
assertEquals("10\t20\t30\t80\t90\t",res);
res=b.preOrder();
assertEquals("30\t20\t10\t90\t80\t",res);
res=b.postOrder();
assertEquals("10\t20\t80\t90\t30\t",res);
}
// System.err.println(b);fail();
for (;sig<=7;sig++) {
assertTrue("remove("+cad[orden[sig]]+") ",b.remove(cad[orden[sig]]));
}
// System.err.println(b);fail();
System.out.print(b);
if (testPrint)
assertEquals(
"10\n"
, outContent.toString());
outContent.reset();
if (testRecorridos) {
res=b.inOrder();
assertEquals("10\t",res);
res=b.preOrder();
assertEquals("10\t",res);
res=b.postOrder();
assertEquals("10\t",res);
}
assertTrue("remove("+cad[orden[sig]]+") ",b.remove(cad[orden[sig]]));sig++;
if (testPrint)
assertEquals(
""
, outContent.toString());
outContent.reset();
if (testRecorridos) {
res=b.inOrder();
assertEquals("",res);
res=b.preOrder();
assertEquals("",res);
res=b.postOrder();
assertEquals("",res);
}
System.setOut(current);
sumaNota(1);
}
@Test
public void testRemoveInf1() {
BSTree<Informacion> b = bI1;
String res;
int sig=0;
Integer[] num=new Integer[]{1,2,0,9,7,3,5,8,6,4};
String[] cad=new String[]{"1-Uno","2-dos","0-cero","9-nueve","7-siete","3-tres","5-cinco","8-ocho","6-seis","4-cuatro"};
int [] orden=new int[]{0,2,6,8,3,4,7,1,5,9};
if (!testInformacion || !testRemove)
fail();
ByteArrayOutputStream outContent = new ByteArrayOutputStream();
PrintStream current = System.out;
System.setOut(new PrintStream(outContent));
for (;sig<=2;sig++) {
assertTrue("remove("+cad[orden[sig]]+") ",b.remove(new Informacion(num[orden[sig]])));
}
// System.err.println(b);
System.out.print(b);
if (testPrint)
assertEquals(
"\t[9:9-nueve]\n"+
"\t\t\t[8:8-ocho]\n"+
"\t\t[7:7-siete]\n"+
"\t\t\t\t\t[6:6-seis]\n"+
"\t\t\t\t[4:4-cuatro]\n"+
"\t\t\t[3:3-tres]\n"+
"[2:2-dos]\n"
, outContent.toString());
outContent.reset();
if (testRecorridos) {
res=b.inOrder();
assertEquals("[2:2-dos]\t[3:3-tres]\t[4:4-cuatro]\t[6:6-seis]\t[7:7-siete]\t[8:8-ocho]\t[9:9-nueve]\t",res);
res=b.preOrder();
assertEquals("[2:2-dos]\t[9:9-nueve]\t[7:7-siete]\t[3:3-tres]\t[4:4-cuatro]\t[6:6-seis]\t[8:8-ocho]\t",res);
res=b.postOrder();
assertEquals("[6:6-seis]\t[4:4-cuatro]\t[3:3-tres]\t[8:8-ocho]\t[7:7-siete]\t[9:9-nueve]\t[2:2-dos]\t",res);
}
assertTrue("remove("+cad[orden[sig]]+") ",b.remove(new Informacion(num[orden[sig]])));
sig++;
// System.err.println(b);fail();
System.out.print(b);
if (testPrint)
assertEquals(
"\t[9:9-nueve]\n"+
"\t\t\t[8:8-ocho]\n"+
"\t\t[7:7-siete]\n"+
"\t\t\t\t[4:4-cuatro]\n"+
"\t\t\t[3:3-tres]\n"+
"[2:2-dos]\n"
, outContent.toString());
outContent.reset();
if (testRecorridos) {
res=b.inOrder();
assertEquals("[2:2-dos]\t[3:3-tres]\t[4:4-cuatro]\t[7:7-siete]\t[8:8-ocho]\t[9:9-nueve]\t",res);
res=b.preOrder();
assertEquals("[2:2-dos]\t[9:9-nueve]\t[7:7-siete]\t[3:3-tres]\t[4:4-cuatro]\t[8:8-ocho]\t",res);
res=b.postOrder();
assertEquals("[4:4-cuatro]\t[3:3-tres]\t[8:8-ocho]\t[7:7-siete]\t[9:9-nueve]\t[2:2-dos]\t",res);
}
// System.err.println(b);fail();
for (;sig<=8;sig++) {
assertTrue("remove("+cad[orden[sig]]+") ",b.remove(new Informacion(num[orden[sig]])));
}
// System.err.println(b);fail();
System.out.print(b);
if (testPrint)
assertEquals(
"[4:4-cuatro]\n"
, outContent.toString());
outContent.reset();
if (testRecorridos) {
res=b.inOrder();
assertEquals("[4:4-cuatro]\t",res);
res=b.preOrder();
assertEquals("[4:4-cuatro]\t",res);
res=b.postOrder();
assertEquals("[4:4-cuatro]\t",res);
}
assertTrue("remove("+cad[orden[sig]]+") ",b.remove(new Informacion(num[orden[sig]])));sig++;
if (testPrint)
assertEquals(
""
, outContent.toString());
outContent.reset();
if (testRecorridos) {
res=b.inOrder();
assertEquals("",res);
res=b.preOrder();
assertEquals("",res);
res=b.postOrder();
assertEquals("",res);
}
System.setOut(current);
sumaNota(1);
}
@Test
public void testRemovesVarios() {
BSTree<Integer> b = bE1;
String res;
if (!testRemove)
fail();
ByteArrayOutputStream outContent = new ByteArrayOutputStream();
PrintStream current = System.out;
System.setOut(new PrintStream(outContent));
assertTrue("remove(5) ",b.remove(5));
assertFalse("remove(5) ",b.remove(5));
assertTrue("remove(0) ",b.remove(0));
assertFalse("remove(0) ",b.remove(0));
System.out.print(b);
if (testPrint)
assertEquals(
"\t\t4\n"+
"\t3\n"+
"\t\t\t\t2\n"+
"\t\t\t1\n"+
"\t\t\t\t-1\n"+
"\t\t-2\n"+
"\t\t\t-3\n"+
"-4\n"
, outContent.toString());
outContent.reset();
if (testRecorridos) {
res=b.inOrder();
assertEquals("-4\t-3\t-2\t-1\t1\t2\t3\t4\t",res);
res=b.preOrder();
assertEquals("-4\t3\t-2\t-3\t1\t-1\t2\t4\t",res);
res=b.postOrder();
assertEquals("-3\t-1\t2\t1\t-2\t4\t3\t-4\t",res);
}
for (int i=4;i!=3;i--) {
assertTrue("remove("+i+") ",b.remove(i));
assertTrue("remove("+(-i)+") ",b.remove(-i));
assertFalse("remove("+i+") ",b.remove(i));
assertFalse("remove("+(-i)+") ",b.remove(-i));
}
System.out.print(b);
if (testPrint)
assertEquals(
"3\n"+
"\t\t\t2\n"+
"\t\t1\n"+
"\t\t\t-1\n"+
"\t-2\n"+
"\t\t-3\n"
, outContent.toString());
outContent.reset();
if (testRecorridos) {
res=b.inOrder();
assertEquals("-3\t-2\t-1\t1\t2\t3\t",res);
res=b.preOrder();
assertEquals("3\t-2\t-3\t1\t-1\t2\t",res);
res=b.postOrder();
assertEquals("-3\t-1\t2\t1\t-2\t3\t",res);
}
assertTrue("remove("+1+") ",b.remove(1));
assertTrue("remove("+(-1)+") ",b.remove(-1));
assertFalse("remove("+1+") ",b.remove(1));
assertFalse("remove("+(-1)+") ",b.remove(-1));
System.out.print(b);
if (testPrint)
assertEquals(
"3\n"+
"\t\t2\n"+
"\t-2\n"+
"\t\t-3\n"
, outContent.toString());
outContent.reset();
if (testRecorridos) {
res=b.inOrder();
assertEquals("-3\t-2\t2\t3\t",res);
res=b.preOrder();
assertEquals("3\t-2\t-3\t2\t",res);
res=b.postOrder();
assertEquals("-3\t2\t-2\t3\t",res);
}
assertFalse("remove(null) ",b.remove(null));
for (int i=2;i<=3;i++) {
assertTrue("remove("+i+") ",b.remove(i));
assertTrue("remove("+(-i)+") ",b.remove(-i));
assertFalse("remove("+i+") ",b.remove(i));
assertFalse("remove("+(-i)+") ",b.remove(-i));
}
if (testRecorridos) {
res=b.inOrder();
assertEquals("",res);
res=b.preOrder();
assertEquals("",res);
res=b.postOrder();
assertEquals("",res);
}
assertFalse("remove(null) ",b.remove(null));
System.setOut(current);
sumaNota(1);
}
@Test
public void testsearch() {
BSTree<Integer> b = bE1;
if (!testsearch)
fail();
// System.err.println(b);
for (int i=5;i!=0;i--) {
assertTrue("search("+i+") ",b.search(i).equals(i));
assertTrue("search("+(-(i-1))+") ",b.search(-(i-1)).equals(-(i-1)));
}
BSTree<Integer> bn = new BSTree<Integer>();
assertNull(bn.search(null));
for (int i=1;i<10;i++) {
assertNull("search("+(i)+") ",bn.search(i));
assertNull("search("+(-i)+") ",bn.search(-i));
}
bn=bE1;
// System.err.println(bn);
for (int i=1;i<10;i++) {
assertNull("search("+(i+10)+") ",bn.search(i+10));
assertNull("search("+(-i-10)+") ",bn.search(-i-10));
}
if (testString){
BSTree<String> bs = bS1;
String[] cadS=new String[]{"40","60","20","10","90","30","50","80","70"};
for (int i=0;i<cadS.length;i++){
assertEquals("search("+cadS[i]+") ",cadS[i],bs.search(cadS[i]));
assertNull("search("+cadS[i]+"+basura) ",bs.search(cadS[i]+"+basura"));
}
sumaNota(0.5f);
}
if (testInformacion){
BSTree<Informacion> bI = bI1;
Integer[] num=new Integer[]{1,2,0,9,7,3,5,8,6,4};
String[] cad=new String[]{"1-Uno","2-dos","0-cero","9-nueve","7-siete","3-tres","5-cinco","8-ocho","6-seis","4-cuatro"};
for (int i=0;i<cad.length;i++){
assertEquals("search("+num[i]+":null) ",new Informacion(num[i],cad[i]),bI.search(new Informacion(num[i])));
assertNull("search("+num[i]+10+":null) ",bI.search(new Informacion(num[i]+10)));
}
sumaNota(1);
}
sumaNota(0.5f);
}
@After
public void MuestraNota() {
System.err.println("La nota es: "+nota);
}
}Arboles AVL:
- AVLNode
- AVLTree
- AVLTreeTest
- AVLExhaustiveTreeTest
AVLNode:
package arboles;
/**
* Clase derivada de BSTNode añadiendo funcionalidad de AVL
* @author Esteban
* @version 2015-16
*
*/
public class AVLNode<T extends Comparable<T>> extends BSTNode<T>
{
//ELIMINADA LA PROPIEDAD <<balanceFactor>> puesto que puede no existir
private int height;
/**
* Añade la información propia de AVL
* @param info la información que se mete en el nuevo nodo
*/
public AVLNode(T info)
{
super(info);
height = 1;
}
/**
* Método que devuelve la height del nodo en el árbol
* @return
*/
public int getheight()
{
return height;
}
/**
* @return Devuelve el factor de balance según equilibrio del árbol
*/
public byte getBF()
{
//Si no tiene hijos, la height de los subárboles será 0
int hIzq = 0;
int hDer = 0;
//En caso de tener hijo derecho, coge su height
if(getRight() != null)
{
hDer = getRight().getheight();
}
//En caso de tener hijo izquierdo, coge su height
if(getLeft() != null)
{
hIzq = getLeft().getheight();
}
//El BF de un nodo es la diferencia entre la height de su subárbol derecho con respecto al subárbol izquierdo
return (byte) (hDer - hIzq);
}
/**
* Establece el factor de balance y/o height
*/
public void updateHeight()
{
//Si el nodo al que llegamos es una hoja, su height será 1
if(getLeft() == null && getRight() == null)
{
height = 1;
}
//Si sólo tiene hijo derecho, su height será la de su subárbol derecho + 1
else if(getLeft() == null)
{
height = 1 + getRight().height;
}
//Si sólo tiene hijo izquierdo, su height será la de su subárbol izquierdo + 1
else if(getRight() == null)
{
height = 1 + getLeft().height;
}
//Si tiene hijo izquierdo y derecho, su height será la height mayor de los dos subárboles + 1
else
{
height = 1 + Math.max(getRight().height, getLeft().height);
}
}
/* (non-Javadoc)
* @see BSTNode#getLeft()
*/
public AVLNode<T> getLeft()
{
return (AVLNode<T>) super.getLeft();
}
/* (non-Javadoc)
* @see BSTNode#getRight()
*/
public AVLNode<T> getRight()
{
return (AVLNode<T>) super.getRight();
}
/* (non-Javadoc)
* @see BSTNode#toString()
* Añade factor de balance
*/
public String toString()
{
return super.toString()+":FB="+ getBF();
}
}package arboles;
/**
* Clase derivada de BSTree añadiendo funcionalidad de AVL
* @author Esteban Montes
*
*/
public class AVLTree <T extends Comparable<T> >extends BSTree <T>
{
/**
* Constructor
*/
public AVLTree()
{
super();
}
/* (non-Javadoc)
* @see BSTree#add(java.lang.Comparable)
* Redefine add para funcionalidad AVL, se debe optar por doble rotación
* en caso de que se pueda hacer rotación doble o simple.
*/
public boolean add (T info)
{
//Comprueba que la clave que se quiere insertar no es null
if(info == null)
{
return false;
}
//Si el árbol es vacío, añadimos el nodo como si fuese la raíz (CASO BASE)
if(getRaiz() == null)
{
setRaiz((new AVLNode<T>(info)));
}
//En caso contrario, lo añadimos recursivamente
else
{
//Si se produce una excepción es que la clave que intentamos insertar ya existe en el árbol
try
{
//Asignamos a la variable raíz, la raíz del árbol (pudo haber cambiado debido a reequilibrios)
setRaiz(addRecAVL(info, (AVLNode<T>) getRaiz()));
} catch (Exception e)
{
return false;
}
}
return true;
}
/**
* Método envoltorio que hace que add() sea recursivo
* Cabe destacar, que al terminar de insertar, se actualizan los BF de los nodos modificados para comprobar si es necesario reequilibrar el árbol
* Caso base: EL nodo al que llegamos es null, y por tanto se crea el nodo
* Caso general: Comparamos la clave que queremos insertar con la clave del nodo al que llegamos
* @param node Nodo con el que comparamos
* @param info Clave que queremos insertar
* @return La referencia al nodo que hemos modificado o no
*/
private AVLNode<T> addRecAVL(T info, AVLNode<T> node) throws Exception
{
//Si el nodo es null creamos un nuevo nodo AVL en dicha posición (CASO BASE)
if(node == null)
{
return (new AVLNode<>(info));
}
else
{
//Si la clave que queremos insertar es menor que el nodo...
if(node.getInfo().compareTo(info) > 0)
{
//...asignamos al hijo izquierdo, lo que nos devuelva la llamada recursiva a addRec con el hijo izquierdo de node
node.setLeft(addRecAVL(info, node.getLeft()));
}
//Si la clave que queremos insertar es mayor que el nodo...
else if(node.getInfo().compareTo(info) < 0)
{
//...asignamos al hijo derecho, lo que nos devuelva la llamada recursiva a addRec con el hijo derecho de node
node.setRight(addRecAVL(info, node.getRight()));
}
//Si la clave que queremos ya existe en el árbol...
else
{
node.setInfo(node.getInfo());
}
//Al terminar, es necesario actualizar el BF del nodo, para saber si se debe reequilibrar el árbol
return updateAndBalance(node);
}
}
/* (non-Javadoc)
* @see BSTree#remove(java.lang.Comparable)
* Redefinición para incluir características AVL
*/
public boolean remove (T info)
{
//Comprobamos que la clave que deseamos borrar no es null
if(info == null)
{
return false;
}
else
{
//Si se produce una excepción es que la clave que intentamos insertar ya existe en el árbol
try
{
//Asignamos a la variable raíz, la raíz del árbol (pudo haber cambiado debido a reequilibrios)
setRaiz(removeRecAVL((AVLNode<T>) getRaiz(), info));
return true;
} catch (Exception e)
{
return false;
}
}
}
/**
* Método envoltorio que convierte a remove() en un método recursivo
* Caso base (1): La clave del nodo al que llegamos es igual a la clave que buscamos
* Caso base (2): Encontrar null
* Caso general: Comparar el la información que queremos buscar con la clave del nodo que se nos ha pasado por parámetro
* @param node Nodo con el que comparamos
* @param info Clave que queremos borrar
* @return Referencia al nodo que se nos ha pasado por parámetro, después de realizar el borrado (o no)
*/
private AVLNode<T> removeRecAVL(AVLNode<T> node, T info) throws Exception
{
//El nodo que buscamos no existe, lanzamos una excepción
if(node == null)
{
throw new Exception("El nodo no existe");
}
else
{
//Si la clave del nodo que queremos buscar es mayor que la del nodo actual...
if(node.getInfo().compareTo(info) < 0)
{
//...llamamos recursivamente a removeRec con el hijo derecho y asignamos la referencia que nos devuelve al hijo derecho del nodo
node.setRight(removeRecAVL(node.getRight(), info));
}
//Si la clave del nodo que queremos borrar es menor que la del nodo actual...
else if (node.getInfo().compareTo(info) > 0)
{
//...llamamos recursivamente a removeRec con el hijo izquierdo y asignamos la referencia que nos devuelve al hijo izquierdo del nodo
node.setLeft(removeRecAVL(node.getLeft(), info));
}
//Si hemos encontrado el nodo que queremos borrar...
else
{
//Caso 1: No tiene hijos y por tanto devolvemos null para borrarlo
if(node.getLeft() == null && node.getRight() == null)
{
return null;
}
//Caso 2a: Tiene hijo izquierdo y por tanto, devolvemos la referencia a dicho hijo para eliminar el nodo actual
else if(node.getLeft() != null && node.getRight() == null)
{
return node.getLeft();
}
//Caso 2b: Tiene hijo derecho y por tanto, devolvemos la referencia a dicho hijo para eliminar el nodo actual
else if(node.getLeft() == null && node.getRight() != null)
{
return node.getRight();
}
//Caso 3: Tiene ambos hijos y para borrarlo...
else
{
//Sustituimos al nodo que queremos borrar por el nodo mayor del subárbol izquierdo
node.setInfo(getMax(node.getLeft()));
//Borramos el nodo anterior (el mayor de los menores)
node.setLeft(removeRecAVL(node.getLeft(), node.getInfo()));
}
}
}
//Al terminar, es necesario actualizar el BF del nodo, para saber si se debe reequilibrar el árbol
return updateAndBalance(node);
}
/**
* Método que actualiza el BF de un nodo
* Si es necesario, reequilibra el árbol a partir del nodo pasado por parámetro
* El reequilibrado puede ser simple o doble
* @param nodo el arbol que se quiere actualizar BF y/o balancear
* @return la raíz del árbol por si ha cambiado
*/
private AVLNode<T> updateAndBalance (AVLNode<T> nodo)
{
//Actualiza la height del nodo, y por tanto su BF
nodo.updateHeight();
//Si el BF es -2, indica que la rotación será de izquierda
if(nodo.getBF() == -2)
{
//Si el BF del hijo izquierdo es -1, la rotación será simple
if(((AVLNode<T>) nodo.getLeft()).getBF() == -1)
{
nodo = singleLeftRotation(nodo);
}
//En otros casos, la rotación es doble
else
{
nodo = doubleLeftRotation(nodo);
}
}
//Si el BF es 2, indica que la rotación será de derecha
else if(nodo.getBF() == 2)
{
//Si el BF del hijo derecho es 1, la rotación es simple
if(((AVLNode<T>) nodo.getRight()).getBF() == 1)
{
nodo = singleRightRotation(nodo);
}
//En otros casos, la rotación es doble
else
{
nodo = doubleRightRotation(nodo);
}
}
return nodo;
}
/**
* Método que realiza un reequilibrado simple por la izquierda
* @param nodo la raíz del árbol a balancear con rotación simple
* @return la raíz del nuevo árbol que ha cambiado
*/
private AVLNode<T> singleLeftRotation (AVLNode<T> nodo)
{
//Utilizamos una variable auxiliar que almacena el hijo izquierdo del nodo que tiene el BF con -2
AVLNode<T> aux = (AVLNode<T>) nodo.getLeft();
//El nuevo hijo izquierdo del nodo será el hijo derecho de aux
nodo.setLeft(aux.getRight());
//Pasando a apuntar ahora al propio nodo
aux.setRight(nodo);
//Actualizamos los BF de todos los nodos implicados en el reequilibrio
nodo.updateHeight();
aux.updateHeight();
return aux;
}
/**
* Método que realiza un reequilibrado doble por la izquierda
* @param nodo la raíz del árbol a balancear con rotación doble
* @return la raíz del nuevo árbol que ha cambiado
*/
private AVLNode<T> doubleLeftRotation(AVLNode<T> nodo)
{
//Utilizamos una variable auxiliar que almacena el hijo derecho del hijo izquierdo del nodo que tiene el BF con -2
AVLNode<T> aux = (AVLNode<T>) nodo.getLeft().getRight();
//El nuevo hijo derecho del hijo izquierdo será el hijo izquierdo de aux
nodo.getLeft().setRight(aux.getLeft());
//Pasando a apuntar al hijo izquierdo del nodo
aux.setLeft(nodo.getLeft());
//Pasando a apuntar al hijo derecho de aux
nodo.setLeft(aux.getRight());
//Pasando a apuntar al propio nodo
aux.setRight(nodo);
//Actualizamos los BF de todos los nodos implicados en el reequilibrio
aux.getRight().updateHeight();
aux.getLeft().updateHeight();
aux.updateHeight();
return aux;
}
/**
* Método que realiza un reequilibrado simple por la derecha
* @param nodo la raíz del árbol a balancear con rotación simple
* @return la raíz del nuevo árbol que ha cambiado
*/
private AVLNode<T> singleRightRotation (AVLNode<T> nodo)
{
//Utilizamos una variable auxiliar que almacena el hijo derecho del nodo que tiene el BF con 2
AVLNode<T> aux = (AVLNode<T>) nodo.getRight();
//El nuevo hijo derecho del nodo será el hijo izquierdo de aux
nodo.setRight(aux.getLeft());
//Pasando a apuntar ahora al propio nodo
aux.setLeft(nodo);
//Actualizamos los BF de todos los nodos implicados en el reequilibrio
nodo.updateHeight();
aux.updateHeight();
return aux;
}
/**
* Método que realiza un reequilibrado doble por la derecha
* @param nodo la raíz del árbol a balancear con rotación doble
* @return la raíz del nuevo árbol que ha cambiado
*/
private AVLNode<T> doubleRightRotation(AVLNode<T> nodo)
{
//Utilizamos una variable auxiliar que almacena el hijo izquierdo del hijo derecho del nodo que tiene el BF con 2
AVLNode<T> aux = (AVLNode<T>) nodo.getRight().getLeft();
//El nuevo hijo izquierdo del hijo derecho será el hijo derecho de aux
nodo.getRight().setLeft(aux.getRight());
//Pasando a apuntar al hijo derecho del nodo
aux.setRight(nodo.getRight());
//Pasando a apuntar al hijo izquierdo de aux
nodo.setRight(aux.getLeft());
//Pasando a apuntar al propio nodo
aux.setLeft(nodo);
//Actualizamos los BF de todos los nodos implicados en el reequilibrio
aux.getLeft().updateHeight();
aux.getRight().updateHeight();
aux.updateHeight();
return aux;
}
public String toString()
{
return tumbarArbol(getRaiz(), 1);
}
}package arboles;
import static org.junit.Assert.*;
import org.junit.Test;
public class AVLTreeTest
{
@Test
public void addTest()
{
AVLTree<Integer> tree = new AVLTree<>();
//Pruebas negativas
assertFalse(tree.add(null));
//Prueba positiva con árbol vacío
assertTrue(tree.add(5));
assertEquals("5:FB=0\t", tree.inOrder());
//Prueba negativa
assertTrue(tree.add(5));
//Prueba positiva de rotación simple izquierda
tree.add(4);
tree.add(3);
assertEquals("3:FB=0\t4:FB=0\t5:FB=0\t", tree.inOrder());
//Prueba positiva de rotación simple derecha
tree.add(6);
tree.add(7);
assertEquals("3:FB=0\t4:FB=1\t5:FB=0\t6:FB=0\t7:FB=0\t", tree.inOrder());
//Prueba positiva de rotación doble izquierda
AVLTree<Integer> tree2 = new AVLTree<>();
tree2.add(10);
tree2.add(12);
tree2.add(6);
tree2.add(5);
tree2.add(8);
tree2.add(9);
assertEquals("5:FB=0\t6:FB=-1\t8:FB=0\t9:FB=0\t10:FB=0\t12:FB=0\t", tree2.inOrder());
//Prueba positiva de rotación doble derecha
AVLTree<Integer> tree3 = new AVLTree<>();
tree3.add(10);
tree3.add(6);
tree3.add(14);
tree3.add(12);
tree3.add(16);
tree3.add(11);
assertEquals("6:FB=0\t10:FB=0\t11:FB=0\t12:FB=0\t14:FB=1\t16:FB=0\t", tree3.inOrder());
}
@Test
public void removeTest()
{
AVLTree<Integer> tree = new AVLTree<>();
tree.add(6);
tree.add(3);
tree.add(9);
tree.add(1);
tree.add(5);
tree.add(8);
tree.add(11);
tree.add(2);
tree.add(4);
tree.add(7);
tree.add(10);
tree.add(13);
tree.add(12);
assertEquals("1:FB=1\t2:FB=0\t3:FB=0\t4:FB=0\t5:FB=-1\t6:FB=1\t7:FB=0\t8:FB=-1\t9:FB=1\t10:FB=0\t11:FB=1\t12:FB=0\t13:FB=-1\t", tree.inOrder());
//Prueba 1: Borrar un nodo sin hijos
assertTrue(tree.remove(10));
assertEquals("1:FB=1\t2:FB=0\t3:FB=0\t4:FB=0\t5:FB=-1\t6:FB=0\t7:FB=0\t8:FB=-1\t9:FB=0\t11:FB=0\t12:FB=0\t13:FB=0\t", tree.inOrder());
//Prueba 2: Borrar un nodo con un hijo
assertTrue(tree.remove(8));
assertEquals("1:FB=1\t2:FB=0\t3:FB=0\t4:FB=0\t5:FB=-1\t6:FB=0\t7:FB=0\t9:FB=1\t11:FB=0\t12:FB=0\t13:FB=0\t", tree.inOrder());
//Prueba 3: Borrar un nodo con dos hijos
assertTrue(tree.remove(6));
assertEquals("1:FB=1\t2:FB=0\t3:FB=-1\t4:FB=0\t5:FB=0\t7:FB=0\t9:FB=1\t11:FB=0\t12:FB=0\t13:FB=0\t", tree.inOrder());
//Pruebas Negativas
assertFalse(tree.remove(null));
assertFalse(tree.remove(-5));
//Prueba con un árbol ambiguo (Debe realizar rotación doble en caso de duda)
AVLTree<Integer> tree2 = new AVLTree<>();
tree2.add(6);
tree2.add(3);
tree2.add(7);
tree2.add(2);
tree2.add(5);
tree2.add(8);
tree2.add(1);
tree2.add(4);
assertEquals("1:FB=0\t2:FB=-1\t3:FB=0\t4:FB=0\t5:FB=-1\t6:FB=-1\t7:FB=1\t8:FB=0\t", tree2.inOrder());
assertTrue(tree2.remove(8));
assertEquals("1:FB=0\t2:FB=-1\t3:FB=-1\t4:FB=0\t5:FB=-1\t6:FB=1\t7:FB=0\t", tree2.inOrder());
}
}package arboles;
import static org.junit.Assert.*;
import org.junit.After;
import org.junit.Before;
import org.junit.Test;
public class AVLTreeTestV0Prof {
boolean testSearch=true,
testRemove=true,
testRecorridos=true,
testAddNotBasic=true,
testPrint=false;
static float nota=0;
static boolean enteros;
AVLTree<Integer> bE1;
private void sumaNota(float x){
nota+=x;
}
@Before
public void testAddEnteros1() {
AVLTree<Integer> bE = new AVLTree<Integer>();
for (int i=5;i>-5;i-=2) {
assertTrue("add("+i+") ",bE.add(i));
assertTrue("add("+(-(i-1))+") ",bE.add(-(i-1)));
}
// System.err.println(bE);
if (testPrint)
assertEquals(
"\t\t5:FB=-1\n"+
"\t\t\t4:FB=0\n"+
"\t3:FB=1\n"+
"\t\t2:FB=0\n"+
"1:FB=0\n"+
"\t\t0:FB=-1\n"+
"\t\t\t-1:FB=0\n"+
"\t-2:FB=0\n"+
"\t\t\t-3:FB=0\n"+
"\t\t-4:FB=1\n"
, bE.toString());
bE1=bE;
if (!enteros){
sumaNota(1.5f);
enteros=true;
}
}
@Test
public void testRecorridosE1() {
AVLTree<Integer> bE =bE1;
String res;
if (!testRecorridos)
fail();
// System.err.println(bE);
res=bE.inOrder();
assertEquals("-4:FB=1\t-3:FB=0\t-2:FB=0\t-1:FB=0\t0:FB=-1\t1:FB=0\t2:FB=0\t3:FB=1\t4:FB=0\t5:FB=-1\t",res);
res=bE.preOrder();
assertEquals("1:FB=0\t-2:FB=0\t-4:FB=1\t-3:FB=0\t0:FB=-1\t-1:FB=0\t3:FB=1\t2:FB=0\t5:FB=-1\t4:FB=0\t",res);
res=bE.postOrder();
assertEquals("-3:FB=0\t-4:FB=1\t-1:FB=0\t0:FB=-1\t-2:FB=0\t2:FB=0\t4:FB=0\t5:FB=-1\t3:FB=1\t1:FB=0\t",res);
sumaNota(1.5f);
}
@Test
public void testVariados() {
AVLTree<Integer> b = new AVLTree<Integer>();
String res;
if (testAddNotBasic) assertFalse(b.add(null));
if (testRemove) {
assertFalse(b.remove(null));
assertFalse(b.remove(0));
}
for (int i=1;i<10;i++) {
if (testSearch) assertEquals("search("+i+")",null,b.search(i));
if (testRemove) assertFalse("remove("+i+") ",b.remove(i));
assertTrue("add("+i+") ",b.add(i));
assertTrue("add("+(-i)+") ",b.add(-20-i));
if (testAddNotBasic) {
assertTrue("add("+i+") ",b.add(i));
assertTrue("add("+(-i)+") ",b.add(-20-i));
}
}
if (testRecorridos){
// System.err.println(b);
res=b.inOrder();
assertEquals("-29:FB=0\t-28:FB=0\t-27:FB=0\t-26:FB=-1\t-25:FB=0\t-24:FB=-1\t-23:FB=0\t-22:FB=0\t-21:FB=0\t1:FB=0\t2:FB=0\t3:FB=0\t4:FB=0\t5:FB=1\t6:FB=0\t7:FB=1\t8:FB=1\t9:FB=0\t",res);
res=b.preOrder();
assertEquals("1:FB=0\t-24:FB=-1\t-26:FB=-1\t-28:FB=0\t-29:FB=0\t-27:FB=0\t-25:FB=0\t-22:FB=0\t-23:FB=0\t-21:FB=0\t5:FB=1\t3:FB=0\t2:FB=0\t4:FB=0\t7:FB=1\t6:FB=0\t8:FB=1\t9:FB=0\t",res);
res=b.postOrder();
assertEquals("-29:FB=0\t-27:FB=0\t-28:FB=0\t-25:FB=0\t-26:FB=-1\t-23:FB=0\t-21:FB=0\t-22:FB=0\t-24:FB=-1\t2:FB=0\t4:FB=0\t3:FB=0\t6:FB=0\t9:FB=0\t8:FB=1\t7:FB=1\t5:FB=1\t1:FB=0\t",res);
}
for (int i=10;i<20;i++) {
if (testSearch) assertEquals("search("+i+")",null,b.search(i));
if (testRemove) assertFalse("remove("+i+") ",b.remove(i));
assertTrue("add("+i+") ",b.add(-i));
assertTrue("add("+(-i)+") ",b.add(10-i));
if (testAddNotBasic) {
assertTrue("add("+i+") ",b.add(-i));
assertTrue("add("+(-i)+") ",b.add(10-i));
}
}
if (testRecorridos){
// System.err.println(b);
res=b.inOrder();
assertEquals("-29:FB=0\t-28:FB=0\t-27:FB=0\t-26:FB=-1\t-25:FB=0\t-24:FB=-1\t-23:FB=0\t-22:FB=-1\t-21:FB=0\t-19:FB=0\t-18:FB=0\t-17:FB=0\t-16:FB=-1\t-15:FB=0\t-14:FB=-1\t-13:FB=0\t-12:FB=0\t-11:FB=0\t-10:FB=0\t-9:FB=0\t-8:FB=-1\t-7:FB=0\t-6:FB=0\t-5:FB=0\t-4:FB=0\t-3:FB=-1\t-2:FB=0\t-1:FB=0\t0:FB=0\t1:FB=0\t2:FB=0\t3:FB=0\t4:FB=0\t5:FB=1\t6:FB=0\t7:FB=1\t8:FB=1\t9:FB=0\t",res);
res=b.preOrder();
assertEquals("-10:FB=0\t-21:FB=0\t-24:FB=-1\t-26:FB=-1\t-28:FB=0\t-29:FB=0\t-27:FB=0\t-25:FB=0\t-22:FB=-1\t-23:FB=0\t-14:FB=-1\t-16:FB=-1\t-18:FB=0\t-19:FB=0\t-17:FB=0\t-15:FB=0\t-12:FB=0\t-13:FB=0\t-11:FB=0\t1:FB=0\t-3:FB=-1\t-7:FB=0\t-8:FB=-1\t-9:FB=0\t-5:FB=0\t-6:FB=0\t-4:FB=0\t-1:FB=0\t-2:FB=0\t0:FB=0\t5:FB=1\t3:FB=0\t2:FB=0\t4:FB=0\t7:FB=1\t6:FB=0\t8:FB=1\t9:FB=0\t",res);
res=b.postOrder();
assertEquals("-29:FB=0\t-27:FB=0\t-28:FB=0\t-25:FB=0\t-26:FB=-1\t-23:FB=0\t-22:FB=-1\t-24:FB=-1\t-19:FB=0\t-17:FB=0\t-18:FB=0\t-15:FB=0\t-16:FB=-1\t-13:FB=0\t-11:FB=0\t-12:FB=0\t-14:FB=-1\t-21:FB=0\t-9:FB=0\t-8:FB=-1\t-6:FB=0\t-4:FB=0\t-5:FB=0\t-7:FB=0\t-2:FB=0\t0:FB=0\t-1:FB=0\t-3:FB=-1\t2:FB=0\t4:FB=0\t3:FB=0\t6:FB=0\t9:FB=0\t8:FB=1\t7:FB=1\t5:FB=1\t1:FB=0\t-10:FB=0\t",res);
}
if (testRemove) {
assertFalse(b.remove(null));
assertTrue(b.remove(0));
assertFalse(b.remove(0));
// System.err.println(b);
if (testRecorridos){
res=b.inOrder();
assertEquals("-29:FB=0\t-28:FB=0\t-27:FB=0\t-26:FB=-1\t-25:FB=0\t-24:FB=-1\t-23:FB=0\t-22:FB=-1\t-21:FB=0\t-19:FB=0\t-18:FB=0\t-17:FB=0\t-16:FB=-1\t-15:FB=0\t-14:FB=-1\t-13:FB=0\t-12:FB=0\t-11:FB=0\t-10:FB=0\t-9:FB=0\t-8:FB=-1\t-7:FB=0\t-6:FB=0\t-5:FB=0\t-4:FB=0\t-3:FB=-1\t-2:FB=0\t-1:FB=-1\t1:FB=0\t2:FB=0\t3:FB=0\t4:FB=0\t5:FB=1\t6:FB=0\t7:FB=1\t8:FB=1\t9:FB=0\t",res);
res=b.preOrder();
assertEquals("-10:FB=0\t-21:FB=0\t-24:FB=-1\t-26:FB=-1\t-28:FB=0\t-29:FB=0\t-27:FB=0\t-25:FB=0\t-22:FB=-1\t-23:FB=0\t-14:FB=-1\t-16:FB=-1\t-18:FB=0\t-19:FB=0\t-17:FB=0\t-15:FB=0\t-12:FB=0\t-13:FB=0\t-11:FB=0\t1:FB=0\t-3:FB=-1\t-7:FB=0\t-8:FB=-1\t-9:FB=0\t-5:FB=0\t-6:FB=0\t-4:FB=0\t-1:FB=-1\t-2:FB=0\t5:FB=1\t3:FB=0\t2:FB=0\t4:FB=0\t7:FB=1\t6:FB=0\t8:FB=1\t9:FB=0\t",res);
res=b.postOrder();
assertEquals("-29:FB=0\t-27:FB=0\t-28:FB=0\t-25:FB=0\t-26:FB=-1\t-23:FB=0\t-22:FB=-1\t-24:FB=-1\t-19:FB=0\t-17:FB=0\t-18:FB=0\t-15:FB=0\t-16:FB=-1\t-13:FB=0\t-11:FB=0\t-12:FB=0\t-14:FB=-1\t-21:FB=0\t-9:FB=0\t-8:FB=-1\t-6:FB=0\t-4:FB=0\t-5:FB=0\t-7:FB=0\t-2:FB=0\t-1:FB=-1\t-3:FB=-1\t2:FB=0\t4:FB=0\t3:FB=0\t6:FB=0\t9:FB=0\t8:FB=1\t7:FB=1\t5:FB=1\t1:FB=0\t-10:FB=0\t",res);
}
assertTrue(b.remove(-19));
assertFalse(b.remove(-19));
assertTrue(b.remove(-10));
assertFalse(b.remove(-10));
assertTrue(b.remove(5));
assertFalse(b.remove(5));
if (testRecorridos){
// System.err.println(b);
res=b.inOrder();
assertEquals("-29:FB=0\t-28:FB=0\t-27:FB=0\t-26:FB=-1\t-25:FB=0\t-24:FB=-1\t-23:FB=0\t-22:FB=-1\t-21:FB=0\t-18:FB=1\t-17:FB=0\t-16:FB=-1\t-15:FB=0\t-14:FB=-1\t-13:FB=0\t-12:FB=-1\t-11:FB=0\t-9:FB=0\t-8:FB=-1\t-7:FB=0\t-6:FB=0\t-5:FB=0\t-4:FB=0\t-3:FB=-1\t-2:FB=0\t-1:FB=-1\t1:FB=0\t2:FB=0\t3:FB=-1\t4:FB=1\t6:FB=0\t7:FB=1\t8:FB=1\t9:FB=0\t",res);
res=b.preOrder();
assertEquals("-11:FB=0\t-21:FB=0\t-24:FB=-1\t-26:FB=-1\t-28:FB=0\t-29:FB=0\t-27:FB=0\t-25:FB=0\t-22:FB=-1\t-23:FB=0\t-14:FB=-1\t-16:FB=-1\t-18:FB=1\t-17:FB=0\t-15:FB=0\t-12:FB=-1\t-13:FB=0\t1:FB=0\t-3:FB=-1\t-7:FB=0\t-8:FB=-1\t-9:FB=0\t-5:FB=0\t-6:FB=0\t-4:FB=0\t-1:FB=-1\t-2:FB=0\t4:FB=1\t3:FB=-1\t2:FB=0\t7:FB=1\t6:FB=0\t8:FB=1\t9:FB=0\t",res);
res=b.postOrder();
assertEquals("-29:FB=0\t-27:FB=0\t-28:FB=0\t-25:FB=0\t-26:FB=-1\t-23:FB=0\t-22:FB=-1\t-24:FB=-1\t-17:FB=0\t-18:FB=1\t-15:FB=0\t-16:FB=-1\t-13:FB=0\t-12:FB=-1\t-14:FB=-1\t-21:FB=0\t-9:FB=0\t-8:FB=-1\t-6:FB=0\t-4:FB=0\t-5:FB=0\t-7:FB=0\t-2:FB=0\t-1:FB=-1\t-3:FB=-1\t2:FB=0\t3:FB=-1\t6:FB=0\t9:FB=0\t8:FB=1\t7:FB=1\t4:FB=1\t1:FB=0\t-11:FB=0\t",res);
}
for (int i=-30;i<30;i++){
if (testSearch)
if (b.search(i)==null)
assertFalse("remove("+i+") ",b.remove(i));
else
assertTrue("remove("+i+") ",b.remove(i));
else
if (b.remove(i))
System.err.println("remove("+i+") es TRUE");
else
System.err.println("remove("+i+") es FALSE");
if (i==0)
if (testRecorridos){
res=b.inOrder();
assertEquals("1:FB=0\t2:FB=0\t3:FB=0\t4:FB=1\t6:FB=0\t7:FB=1\t8:FB=1\t9:FB=0\t",res);
res=b.preOrder();
assertEquals("4:FB=1\t2:FB=0\t1:FB=0\t3:FB=0\t7:FB=1\t6:FB=0\t8:FB=1\t9:FB=0\t",res);
res=b.postOrder();
assertEquals("1:FB=0\t3:FB=0\t2:FB=0\t6:FB=0\t9:FB=0\t8:FB=1\t7:FB=1\t4:FB=1\t",res);
}
else
System.err.println(b);
}
if (testRecorridos){
res=b.inOrder();
assertEquals("",res);
res=b.preOrder();
assertEquals("",res);
res=b.postOrder();
assertEquals("",res);
}
}
sumaNota(2);
}
@Test
public void testRemoveE1() {
AVLTree<Integer> b = bE1;
String res;
if ( !testRemove)
fail();
assertTrue("remove(5) ",b.remove(5));
for (int i=4;i!=3;i--) {
assertTrue("remove("+i+") ",b.remove(i));
assertTrue("remove("+(-i)+") ",b.remove(-i));
}
// System.err.println(b);
if (testPrint)
assertEquals(
"\t3:FB=-1\n"+
"\t\t2:FB=0\n"+
"1:FB=-1\n"+
"\t\t0:FB=-1\n"+
"\t\t\t-1:FB=0\n"+
"\t-2:FB=1\n"+
"\t\t-3:FB=0\n"
, b.toString());
if (testRecorridos) {
res=b.inOrder();
assertEquals("-3:FB=0\t-2:FB=1\t-1:FB=0\t0:FB=-1\t1:FB=-1\t2:FB=0\t3:FB=-1\t",res);
res=b.preOrder();
assertEquals("1:FB=-1\t-2:FB=1\t-3:FB=0\t0:FB=-1\t-1:FB=0\t3:FB=-1\t2:FB=0\t",res);
res=b.postOrder();
assertEquals("-3:FB=0\t-1:FB=0\t0:FB=-1\t-2:FB=1\t2:FB=0\t3:FB=-1\t1:FB=-1\t",res);
}
assertTrue("remove("+1+") ",b.remove(1));
assertTrue("remove("+(-1)+") ",b.remove(-1));
// System.err.println(b);
if (testPrint)
assertEquals(
"\t3:FB=-1\n"+
"\t\t2:FB=0\n"+
"0:FB=0\n"+
"\t-2:FB=-1\n"+
"\t\t-3:FB=0\n"
, b.toString());
if (testRecorridos) {
res=b.inOrder();
assertEquals("-3:FB=0\t-2:FB=-1\t0:FB=0\t2:FB=0\t3:FB=-1\t",res);
res=b.preOrder();
assertEquals("0:FB=0\t-2:FB=-1\t-3:FB=0\t3:FB=-1\t2:FB=0\t",res);
res=b.postOrder();
assertEquals("-3:FB=0\t-2:FB=-1\t2:FB=0\t3:FB=-1\t0:FB=0\t",res);
}
for (int i=2;i<=3;i++) {
assertTrue("remove("+i+") ",b.remove(i));
assertTrue("remove("+(-i)+") ",b.remove(-i));
}
// System.err.println(b);
if (testPrint)
assertEquals(
"0:FB=0\n"
, b.toString());
if (testRecorridos) {
res=b.inOrder();
assertEquals("0:FB=0\t",res);
res=b.preOrder();
assertEquals("0:FB=0\t",res);
res=b.postOrder();
assertEquals("0:FB=0\t",res);
}
sumaNota(2);
}
@Test
public void testRemovesVarios() {
AVLTree<Integer> b = bE1;
String res;
if (!testRemove)
fail();
assertTrue("remove(5) ",b.remove(5));
assertFalse("remove(5) ",b.remove(5));
assertTrue("remove(0) ",b.remove(0));
assertFalse("remove(0) ",b.remove(0));
// System.err.print(b);
if (testPrint)
assertEquals(
"\t\t4:FB=0\n"+
"\t3:FB=0\n"+
"\t\t2:FB=0\n"+
"1:FB=-1\n"+
"\t\t-1:FB=0\n"+
"\t-2:FB=-1\n"+
"\t\t\t-3:FB=0\n"+
"\t\t-4:FB=1\n"
, b.toString());
if (testRecorridos) {
res=b.inOrder();
assertEquals("-4:FB=1\t-3:FB=0\t-2:FB=-1\t-1:FB=0\t1:FB=-1\t2:FB=0\t3:FB=0\t4:FB=0\t",res);
res=b.preOrder();
assertEquals("1:FB=-1\t-2:FB=-1\t-4:FB=1\t-3:FB=0\t-1:FB=0\t3:FB=0\t2:FB=0\t4:FB=0\t",res);
res=b.postOrder();
assertEquals("-3:FB=0\t-4:FB=1\t-1:FB=0\t-2:FB=-1\t2:FB=0\t4:FB=0\t3:FB=0\t1:FB=-1\t",res);
}
for (int i=4;i!=3;i--) {
assertTrue("remove("+i+") ",b.remove(i));
assertTrue("remove("+(-i)+") ",b.remove(-i));
assertFalse("remove("+i+") ",b.remove(i));
assertFalse("remove("+(-i)+") ",b.remove(-i));
}
// System.err.print(b);
if (testPrint)
assertEquals(
"\t3:FB=-1\n"+
"\t\t2:FB=0\n"+
"1:FB=0\n"+
"\t\t-1:FB=0\n"+
"\t-2:FB=0\n"+
"\t\t-3:FB=0\n"
, b.toString());
if (testRecorridos) {
res=b.inOrder();
assertEquals("-3:FB=0\t-2:FB=0\t-1:FB=0\t1:FB=0\t2:FB=0\t3:FB=-1\t",res);
res=b.preOrder();
assertEquals("1:FB=0\t-2:FB=0\t-3:FB=0\t-1:FB=0\t3:FB=-1\t2:FB=0\t",res);
res=b.postOrder();
assertEquals("-3:FB=0\t-1:FB=0\t-2:FB=0\t2:FB=0\t3:FB=-1\t1:FB=0\t",res);
}
assertTrue("remove("+1+") ",b.remove(1));
assertTrue("remove("+(-1)+") ",b.remove(-1));
assertFalse("remove("+1+") ",b.remove(1));
assertFalse("remove("+(-1)+") ",b.remove(-1));
// System.err.print(b);
if (testPrint)
assertEquals(
"\t3:FB=-1\n"+
"\t\t2:FB=0\n"+
"-2:FB=1\n"+
"\t-3:FB=0\n"
, b.toString());
if (testRecorridos) {
res=b.inOrder();
assertEquals("-3:FB=0\t-2:FB=1\t2:FB=0\t3:FB=-1\t",res);
res=b.preOrder();
assertEquals("-2:FB=1\t-3:FB=0\t3:FB=-1\t2:FB=0\t",res);
res=b.postOrder();
assertEquals("-3:FB=0\t2:FB=0\t3:FB=-1\t-2:FB=1\t",res);
}
assertFalse("remove(null) ",b.remove(null));
for (int i=2;i<=3;i++) {
assertTrue("remove("+i+") ",b.remove(i));
assertTrue("remove("+(-i)+") ",b.remove(-i));
assertFalse("remove("+i+") ",b.remove(i));
assertFalse("remove("+(-i)+") ",b.remove(-i));
}
if (testRecorridos) {
res=b.inOrder();
assertEquals("",res);
res=b.preOrder();
assertEquals("",res);
res=b.postOrder();
assertEquals("",res);
}
assertFalse("remove(null) ",b.remove(null));
sumaNota(2);
}
@Test
public void testSearch() {
AVLTree<Integer> b = bE1;
if (!testSearch)
fail();
// System.err.println(b);
for (int i=5;i!=0;i--) {
assertTrue("search("+i+") ",b.search(i).equals(i));
assertTrue("search("+(-(i-1))+") ",b.search(-(i-1)).equals(-(i-1)));
}
AVLTree<Integer> bn = new AVLTree<Integer>();
assertNull(bn.search(null));
for (int i=1;i<10;i++) {
assertNull("search("+(i)+") ",bn.search(i));
assertNull("search("+(-i)+") ",bn.search(-i));
}
bn=bE1;
// System.err.println(bn);
for (int i=1;i<10;i++) {
assertNull("search("+(i+10)+") ",bn.search(i+10));
assertNull("search("+(-i-10)+") ",bn.search(-i-10));
}
sumaNota(1);
}
@After
public void MuestraNota() {
System.err.println("La nota es: "+nota);
}
}