Tuesday, 30 June 2009

Concordion

Bueno, este mes ya veo que me estoy superando con la friolera de más de 30 artículos. Espero que os de tiempo de leerlos todos porque ya veis que son muy interesantes. En éste artículo y continuando con mi planificación voy a hablaros de Concordion. Hace unas horas os estuve entreteniendo con FIT (Framework for Integrated Test), pues bién, Concordion es una mejora de éste marco de trabajo y mucho más intuitivo para los lenguages Java, .NET y Ruby. Concordion ha sido desarrollado por David Peterson, y uno de sus desarrolladores es José Manuel Beas, el cual podéis encontrar en mi lista de blog roll. Éste al igual que FIT trabaja mediante tablas HTML, pero es mucho más fácil de añadirlo a nuestro proyecto Java. Mediante una keywords muy básicas, podemos crear nuestras hojas de test para comprobar que el programa devuelve lo que nosotros queremos.
  • Que necesitamos para empezar?
Primero, descargamos la última versión de concordion desde la misma web: Concordion-1.3.1. Luego una vez descargado, tenemos que añadir las librerias necesárias a nuestro class path en el eclipse:

Como podéis observar, tengo enlazadas las librerías concordion-1.3.1.jar, la última versión de la junit (junit-4.6.jar) y las ognl-2.6.9.jar y xom-1.1.jar. Una vez tengo esto, creo un pequeño package llamado example donde pondré el código que voy a probar.
Podréis encontrar más información del funcionamiento de Concordion en la web : http://www.concordion.org/Tutorial.html.

Ahora, aprovechando el código fuente de mi anterior post (Arithmetic.java) crearé un HTML de pruebas para ver si la clase me genera bien los resultados esperados. Aquí os pongo la definición del fichero java:

ArithmeticTest.java:




/**
* @Author : Jordi Coll
* Test With Concordion
*/
package example;

import org.concordion.integration.junit3.ConcordionTestCase;

public class ArithmeticTest extends ConcordionTestCase {
private int x;
private int y;

public int plus () {
return getX() + getY();
}

public int minus() {
return getX() - getY();
}

public int multiply () {
return getX() * getY();
}

public int divide () {
return getX() / getY();
}

public float floating () {
return (float)getX() / (float)getY();
}

public float sin () {
return (float)Math.sin(Math.toRadians(getX()));
}

public float cos () {
return (float) Math.cos(Math.toRadians(getX()));
}

public void setX(int x) {
this.x = x;
}

public int getX() {
return x;
}

public void setY(int y) {
this.y = y;
}

public int getY() {
return y;
}
}





Como podéis ver, hay que heredar de la clase ConcordionTestCase para que parsee el documento HTML y localice las entradas que queremos.

Una vez ejecutamos el proyecto con el jUnit, nos tiene que aparecerer en la ventana resultado:

C:\Temp\concordion\example\Arithmetic.html Successes: 4, Failures: 2, Exceptions: 1

La parte del HTML es muy fácil. Simplemente tenemos que generar éste con una sería de metaKeywords definidos por concordion. De ésta manera, podemos escribir sobre un método y leer de él con mucha facilidad. Por ejemplo voy a cargar los valores x y y con números y luego voy a comprobar el resultado. Si el resultado es correcto, me marcará el número en verde y sino en rojo.

Arithmetic.html:

El HTML se tiene que decir igual que la clase, pero sin el Test, de esta manera el hace el matching de una clase a su HTML correspondiente.




<html xmlns:concordion="http://www.concordion.org/2007/concordion">
<body>
<p>
x:
<span concordion:execute="setX(#TEXT)">2</span>
y:
<span concordion:execute="setY(#TEXT)">2</span>
- x+y:
<span concordion:assertEquals="plus()">4</span>
</p>
<p>
x:
<span concordion:execute="setX(#TEXT)">2</span>
y:
<span concordion:execute="setY(#TEXT)">2</span>
- x*y:
<span concordion:assertEquals="multiply()">4</span>
</p>
<p>
x:
<span concordion:execute="setX(#TEXT)">2</span>
y:
<span concordion:execute="setY(#TEXT)">2</span>
- x div y:
<span concordion:assertEquals="divide()">1</span>
</p>
<p>
x:
<span concordion:execute="setX(#TEXT)">2</span>
y:
<span concordion:execute="setY(#TEXT)">2</span>
- x / y:
<span concordion:assertEquals="floating()">1.0</span>
</p>
<p>
x:
<span concordion:execute="setX(#TEXT)">2</span>
- sin(x):
<span concordion:assertEquals="sin()">0.034899495</span>
</p>
<p>
x:
<span concordion:execute="setX(#TEXT)">2</span>
- cos(x):
<span concordion:assertEquals="cos()">0.99939084</span>
</p>
</body>
</
html>




En el caso de que la prueba tubiese éxito aparecería:


Si uno de los valores no devolviese el valor esperado, nos aparecería de la siguiente manera:

Una de las cosas más interesantes que he visto y que más me ha gustado ha sido el mostrado de los errores. Si nos equivocamos al escribir un método en el HTML, luego en el resultado nos aparece:



FIT (Framework for integrated test)

FIT, o Framework for Integrated Test, es un marco de trabajo para el aprovechamiento integral de los ensayos o pruebas. Es una herramienta open source para la automatización de pruebas del cliente. Integra el trabajo de los clientes, analistas, testers y desarrolladores. FIT mejora la comunicación y la colaboración. Crea un circuito de retroalimentación entre los clientes y programadores y permite a los clientes y los testers utilizar herramientas como Microsoft Office para dar ejemplos de cómo debe comportarse un programa (sin ser programadores). Con ésta utilidad construimos un simple y poderoso puente entre la empresa y el mundo de la ingeniería del software. Mediante FIT, los clientes pueden proporcionar una mayor orientación en el proceso de desarrollo, y obtienen mayor visibilidad sobre lo que está sucediendo en el producto y si están dentro de los límites o no.

  • Cómo funciona?
Los clientes proporcionan ejemplos de cómo el software debería funcionar. Estos ejemplos serán la pasarela entre los programadores y los testers. Mediante tablas en HTML (ya sea utilizando Microsoft Word o Excel y luego guardando el resultado en HTML) FIT comprueba el valor a obtener por el programa y lo compara con el valor de muestra. En el caso de que pase la prueba marca la casilla en verde y sino en rojo. También puede marcarlo en amarillo para indicar otros estados.

FIT fue inventado por Ward Cunningham en el año 2002. Él creó la primera versión de FIT para java y en junio de 2005 se actualizó la versión para Java, C#, Python, Perl, PHP y SmallTalk. Si miramos en la web de FIT, podemos encontrar versiones para Ruby y Delphi (fit4Delphi).
Han aparecido nuevas herramientas como FitNesse o Concordion de los que hablaré más adelante.

Si nos bajamos la última versión para Java (fit-java1.1) encontraremos varios ejemplos y el código fuente de su utilización, podemos iniciar el programa de prueba ejecutando la siguiente línea en el cmd:

java -classpath fit.jar fit.FileRunner examples/input/arithmetic.html results.html

El ejemplo se basa en parametrizar unos valores de prueba para unas operaciones matemáticas y el resultado esperado. Luego mediante FIT se compara que el resultado esperado por el cliente es el resultado mostrado por el programa:

Plantilla:

Se le indica la clase, las operaciones en las columnas y el resultado esperado. Luego una vez ejecutadas las pruebas podemos ver el resultado:



Mock Objects

Continuando en la misma línea del Test Driven Development, existe una evolución o mejora de los xUnit basada en los Mock Objects. Los Mock Objects utilizan una técnica para que el diseño del software se haga sobre el TDD. Al igual que los xUnit, podemos encontrar ésta técnica en varios lenguajes de programación: java (jMock y EasyMock), Delphi (pascalMock), .NET (NMock), etc. Aquí os mostraré un par de ejemplos sobre la implementación en Java y Delphi.
  • Utilizando jMock:
Para este ejemplo, nos descargaremos el jMock de la web en éste caso la versión 2.5.1 (jmock-2.5.1), y la última versión del jUnit (la 4.6) -> jUnit-4.6.jar. Una vez tenemos todos los .jar descargados, tenemos que añadirlos en el class path de nuestro proyecto. Por lo tanto tenemos que vincularlo de la siguiente manera:

Voy a aprovechar el ejemplo que posteé ayer sobre la clase TArithmetic, y la he implementado en java para simular el mismo comportamiento. Además es muy fácil de seguir sin complicar mucho el código.

De acuerdo con el TDD, primero tenemos que crear el test case:




/**
* @Author : Jordi Coll
* Test With Mock Objects
*/
import static org.junit.Assert.assertEquals;

import org.junit.Test;

public class TestJMockIniCase {
@Test
public void testSayGreeting(){
Arithmetic a = new Arithmetic();
assertEquals(0, a.plus());
}
}





En este caso, como no hemos creado la clase Arithmetic da un error. Para hacer que compile, necesito crear la clase. Luego tenemos que crear una clase llamada ComponentArithmetic que es la que comunicará con la clase Arithmetic para entregarle las variables x y y para sus cálculos. Luego explicaremos el porqué de esto.

Aquí está la clase Arithmetic:




/**
* @Author : Jordi Coll
* Test With Mock Objects
*/
public class Arithmetic {
private ComponentArithmetic component;

public void SetComponent(ComponentArithmetic component) {
this.component = component;
}

public int plus () {
return component.getX() + component.getY();
}

public int minus() {
return component.getX() - component.getY();
}

public int multiply () {
return component.getX() * component.getY();
}

public int divide () {
return component.getX() / component.getY();
}

public float floating () {
return (float)component.getX() / (float)component.getY();
}

public float sin () {
return (float)Math.sin(Math.toRadians(component.getX()));
}

public float cos () {
return (float) Math.cos(Math.toRadians(component.getX()));
}
}




Para seguir con la compilación, tenemos que crear la clase ComponentArithmetic. Como queremos utilizar mock objects, debemos crear ésta como una interfaz:




/**
* @Author : Jordi Coll
* Test With Mock Objects
*/
public interface ComponentArithmetic {
public int getX();
public int getY();
}




Uno de los pre-requisitos para el uso de los mock objects, es que la clase que parametrizaremos la tenemos que declarar como una interfaz. Además, tenemos que utilizar métodos setter para inyectar la instancia de ComponentArithmetic a Arithmetic. (No podemos utilizar la notación "new" en una interfaz).

Ahora, solo tenemos que modificar la clase de test para que cumpla con nuestras expectativas:




/**
* @Author : Jordi Coll
* Test With Mock Objects
*/

import org.jmock.Expectations;
import org.jmock.Mockery;

import org.jmock.integration.junit4.JMock;
import org.jmock.integration.junit4.JUnit4Mockery;
import static org.junit.Assert.assertEquals;

import org.junit.Test;
import org.junit.runner.RunWith;

@RunWith(JMock.class)
public class TestUsingjMock {
//Creamos el contexto para el mock Object
Mockery context = new JUnit4Mockery();

@Test
public void testArithmetic() {
//Mock sobre la clase ComponentArithmetic utilizando la tecnologia de refexión
//La tenemos que definir como variable final
//ya que va a ser utilizada como clase interna
final ComponentArithmetic ca = context.mock(ComponentArithmetic.class);
Arithmetic a = new Arithmetic();
a.SetComponent(ca);

//Ponemos lo que vamos a esperar del mock Object
context.checking(new Expectations() {
{
one(ca).getX();
will(returnValue(2));
one(ca).getY();
will(returnValue(2));
}
});

int plus = a.plus();
//comparamos el resultado con el valor esperado
assertEquals(3, plus);
}
}




(Todo el tema de los expectators lo podemos encontrar en la web del jUnit : http://www.jmock.org/cookbook.html)

Ahora, si ejecutamos el test con el JUnit, obtendremos:

Prueba correcta:

Prueba con error:
  • Utilizando Pascal Mock:
Podemos encontrar la última versión de Pascal Mock en SourceForge. La última versión estable es la 1.1, y podemos descargarla directamente desde aquí. Su utilización es muy parecida al DUnit y hay que generar las interfases necesarias para que los mock object actúen. Podremos encontrar muchos ejemplos dentro del código. El ejemplo que hay dentro del proyecto, lo podemos ejecutar y visualizar:

Es un proyecto que no está muy vivo (desde el 2007 sin ninguna actualización) y es bastante más complicado de utilizar que con java.

Monday, 29 June 2009

Extreme Programming

Extreme Programming o Programación extrema es una de las llamadas metodologías Ágiles de desarrollo de software. Ésta metodología fue formulada por Kent beck quién fundó el test-first programming, la família xUnit de developer testing tools, y el Extreme Programming. Todos éstos metodos convergen en la búsqueda de un diseño de software efectivo. Hay varios libros interesantes y mucha información por la red, pero la mayoría en inglés. Desde éste artículo os indico cuales son las características fundamentales de la programación extrema y el impacto que está teniendo en el desarrollo del software. Gracias a todas éstas metodologías de trabajo, podemos crear software más estable, con mejores tests y ser más rápidos aportando gran calidad al proyecto. Hoy en día podemos encontrar ésta metodología en cualquier lenguaje de programación, por ejemplo con Delphi en delphiXtreme.
  • Características fundamentales:
  1. Desarrollo iterativo e incremental: Se generan pequeñas mejoras una detrás de la otra.
  2. Pruebas unitarias continuas, frecuentemente repetidas y automáticas, incluyendo pruebas de regresión: Se aconseja escribir el código de la prueba antes de la codificación. Ver el TDD.
  3. Pair-Programming (Programación por parejas): Se recomienda que las tareas de desarrollo se lleven a cabo por 2 personas en un mismo sitio. Se supone que la mayor calidad del código escrito de esta forma (el código es revisado y discutido mientras se escribe) es más importante que la posible pérdida de productividad inmediata.
  4. Frecuente interacción del equipo de programación con el cliente o usuario:. Se recomienda que un representante del cliente trabaje juntamente con el equipo de desarrollo.
  5. Corrección de todos los errores antes de añadir una nueva funcionalidad: Realizar entregas frecuentes.
  6. Refactoring del código: Reescribir ciertas partes del código para aumentar su legibilidad y mantenimiento pero sin modificar su comportamiento. Las pruebas tienen que garantizar que en el refactoring no se ha introducido ningún error.
  7. Propiedades del código compartido: El lugar de dividir la responsabilidad en el desarrollo de cada módulo en grupos de trabajo diferentes, este método promueve que todo el personal pueda corregir y extender cualquier parte del proyecto. Las frecuentes pruebas de regresión garantizan que los posibles errores sean detectados.
  8. Simplicidad en el código: Es la mejor manera de que las cosas funcionen. Cuando todo funcione se podrán añadir funcionalidades si es necesario.
Tal como indica la wikipedia, existen una serie de principios y valores básicos que hay que seguir, tales como la comunicación, simplicidad, feedback, coraje y humildad.

Para profundizar sobre el tema os recomiendo los libros de Extreme Programming, sobretodo Extreme Programming Explained y Extreme Programming Installed.

Como podéis ver, hay un vínculo muy estrecho entre XP y AGILE, y hay muchas comunidades on-line que se intentan dar a conocer para que los desarrolladores de software utilicen éstas metodologías.

Las DUnit y el test Programming

En este artículo profundizaré un poco más sobre los test unitarios y su funcionamiento. Como expliqué en su día (con el Test Driven Development), tenemos que realizar las pruebas unitarias de nuestros módulos y automatizarlas. Para éste post, crearé un ejemplo sencillo con una pequeña clase llamada TArithmetic que tiene unos cuantos métodos matemáticos, y luego lanzaré un pequeño test unitario para ver si el módulo está correctamente diseñado o no.

Cómo funciona el test unitario?
Las xUnit, crean un test por cada clase que tenga, por lo tanto testa los métodos de mi clase.

  • Ejemplo clase TArithmetic:
Con esta clase básica podremos ver como Delphi realiza las pruebas unitarias.

unit Arithmetic;

interface

type
    TArithmetic = class(TObject)
    private
        Fx: integer;
        Fy: integer;
        procedure Setx(const Value: integer);
        procedure Sety(const Value: integer);
    public
        property x: integer read Fx write Setx;
        property y: integer read Fy write Sety;
        function plus(): integer;
        function minus(): integer;
        function multiply(): integer;
        function divide(): integer;
        function floatDivision(): double;
        function sinus(): double;
        function cosinus(): double;
    end;

implementation

{ TArithmetic }

function TArithmetic.cosinus: double;
begin
    result := cos(self.Fx);
end;

function TArithmetic.divide: integer;
begin
    result := Self.Fx div Self.Fy;
end;

function TArithmetic.floatDivision: double;
begin
    result := Self.Fx / Self.Fy;
end;

function TArithmetic.minus: integer;
begin
    result := Self.Fx - Self.Fy;
end;

function TArithmetic.multiply: integer;
begin
    result := Self.Fx * Self.Fy;
end;

function TArithmetic.plus: integer;
begin
    result := Self.Fx + Self.Fy;
end;

procedure TArithmetic.Setx(const Value: integer);
begin
    Fx := Value;
end;

procedure TArithmetic.Sety(const Value: integer);
begin
    Fy := Value;
end;

function TArithmetic.sinus: double;
begin
    result := sin(self.Fx);
end;

end.

  • Creando el Test Project:
Una vez tengo creada mi Unit, voy a File -> New -> Other, y en el árbol de la derecha marco Unit Test.

Selecciono Test Project, y lo añado a mi grupo de proyectos:

Su configuración es bastante sencilla, primero solo tenemos que configurar la ruta donde está nuestro proyecto y seleccionar la interfaz GUI:

Una vez tenemos el Test Project creado, tenemos que añadir una Test Case. Seleccionamos el Proyecto del test que hemos añadido, y luego nos dirigimos a File -> New -> Other y seleccionamos "Test Case".

Seleccionamos los métodos que queremos para nuestro test y luego le damos un nombre y lo asociamos a nuestro proyecto:

Una vez el asistente ha acabado, nos genera una unit llamada TestArithmetic, con el siguiente contenido:

unit TestArithmetic;
{

Delphi DUnit Test Case
----------------------
This unit contains a skeleton test case class generated by the Test Case Wizard.
Modify the generated code to correctly setup and call the methods from the unit
being tested.

}

interface

uses
    TestFramework, Arithmetic;

type
    // Test methods for class TArithmetic

    TestTArithmetic = class(TTestCase)
        strict private
            FArithmetic: TArithmetic;
    public
        procedure SetUp; override;
        procedure TearDown; override;
    published
        procedure Testplus;
        procedure Testminus;
        procedure Testmultiply;
        procedure Testdivide;
        procedure TestfloatDivision;
        procedure Testsinus;
        procedure Testcosinus;
    end;

implementation

procedure TestTArithmetic.SetUp;
begin
    FArithmetic := TArithmetic.Create;
end;

procedure TestTArithmetic.TearDown;
begin
    FArithmetic.Free;
    FArithmetic := nil;
end;

procedure TestTArithmetic.Testplus;
var
    ReturnValue: Integer;
begin
    ReturnValue := FArithmetic.plus;
    // TODO: Validate method results
end;

procedure TestTArithmetic.Testminus;
var
    ReturnValue: Integer;
begin
    ReturnValue := FArithmetic.minus;
    // TODO: Validate method results
end;

procedure TestTArithmetic.Testmultiply;
var
    ReturnValue: Integer;
begin
    ReturnValue := FArithmetic.multiply;
    // TODO: Validate method results
end;

procedure TestTArithmetic.Testdivide;
var
    ReturnValue: Integer;
begin
    ReturnValue := FArithmetic.divide;
    // TODO: Validate method results
end;

procedure TestTArithmetic.TestfloatDivision;
var
    ReturnValue: Double;
begin
    ReturnValue := FArithmetic.floatDivision;
    // TODO: Validate method results
end;

procedure TestTArithmetic.Testsinus;
var
    ReturnValue: Double;
begin
    ReturnValue := FArithmetic.sinus;
    // TODO: Validate method results
end;

procedure TestTArithmetic.Testcosinus;
var
    ReturnValue: Double;
begin
    ReturnValue := FArithmetic.cosinus;
    // TODO: Validate method results
end;

initialization
    // Register any test cases with the test runner
    RegisterTest(TestTArithmetic.Suite);
end.

Como podéis ver, ha generado una llamada a cada uno de nuestros métodos y la asignación de variables para poder realizar el test. Si ahora iniciamos el proyecto y hacemos un run para pasar las pruebas unitarias sucede lo siguiente:

Como podéis ver, no ha pasado las pruebas porqué hay divisiones por 0. Entonces nuestra clase no está protegida contra este tipo de valores, y hay que protegerla.

Si suponemos que el valor del divisor puede ser 0, entonces tenemos que indicarle al test que posiblemente le llegará una excepción de este tipo. Para realizar esto, tenemos que hacer lo siguiente:

unit TestArithmetic;

uses
    SysUtils;

procedure TestTArithmetic.Testdivide;
var
    ReturnValue: Integer;
begin
    StartExpectingException(EDivByZero);
    ReturnValue := FArithmetic.divide;
    StopExpectingException();  
end;

procedure TestTArithmetic.TestfloatDivision;
var
    ReturnValue: Double;
begin
    StartExpectingException(EInvalidOp);
    ReturnValue := FArithmetic.floatDivision;
    StopExpectingException();
end;

y poner el tipo de excepción que esperamos que suceda al realizar la operación del método. Aunque nos aparezca el mensaje:

luego las pruebas unitarias pasan los diferentes test:

También podemos especificar las operaciones añadiendo valores al método y haciendo la comparación. Por ejemplo si en la operación suma sabemos que el resultado es un valor concreto lo podemos comparar con el valor devuelto del método y así podemos ver si el resultado es correcto o no. A modo de ejemplo tendríamos:

procedure TestTArithmetic.Testplus;
var
    ReturnValue: Integer;
begin
    FArithmetic.x := 10;
    FArithmetic.y := 10;
    ReturnValue := FArithmetic.plus;
    checkEquals(ReturnValue, 20);
end;


Si miramos la respuesta del test unitario obtenemos:

Tenemos un fallo, esperábamos un 21 (a modo de ejemplo), pero el método devolvió un 20. Con ésto nos podemos imaginar como podríamos testar los otros métodos. Después de montar todos los test, las pruebas unitarias tienen que pasar sin problemas. Luego mientras hacemos cambios en nuestro código tenemos que tener en cuenta que las pruebas unitarias tienen que pasar y debemos tener la mayoría de los casos pensados. Lo interesante del TDD, es que primero se genera el test y luego se crea la clase, de esta manera el desarrollo de la clase no pierde el rumbo y solo creamos aquello que necesitamos.

  • Cómo funciona el xtesting framework?

El programa lanza threats y los lanza en paralelo para ir más rápido. Los test han de ser repetibles, por lo tanto en cada método hay que crear el estado para el test, ejecutar el test y luego destruir el estado. Para cada método del test, se llama al SetUp y al TearDown. Cada vez que se hace una prueba, se llama a una nueva instáncia del Test/Case, por lo tanto todo es bastante independiente.
El TestSuite es agrupar un montón de TestCase. Registrando tu TestCase en una TestSuite nos permite hacer lo mismo. Lo que te propone el TestSuite es hacer un test por método, pero lo que te sugieren es hacer un test por expectación.

Los test, hay que automatizarlos. Por pequeño que sea el cambio, ejecuto el test. En los siguientes post, hablaré del Extreme Programming y de diversos sistemas para realizar pruebas unitarias y de integración. Existen muchas herramientas tales como FIT (Framework for integrated test), Mock Objects, etc. Y sobretodo tenemos que tener en cuenta los bad smells en nuestro código, como el DRY (Don't Repeat Yourself) y el YAGNI (You Ain't Gonna Need It) que hablaré un poco más de éstos en los siguientes artículos.

Espero que os sirva de ayuda!.

  • Enlaces de interés:
DUnit Framework.
Pruebas automatizadas con DUnit.

Friday, 26 June 2009

Implementando un AVL Tree en Delphi

Como se conoce en informática un AVL Tree, es un árbol binario de búsqueda balanceado. De esta manera al ir añadiendo nodos o hojas al árbol, éste se balancea automáticamente para mantener siempre un equilibrio en sus niveles y conseguir que el coste de búsqueda de un valor sea de O(log n). En este artículo aprovecho el trabajo realizado por Nicklaus Wirth y Giacomo Policicchio, y adapto su trabajo para el ejemplo que quiero mostrar, y es el de dibujar el árbol mediante la utilización de métodos abstractos sobre un Timage y mi querido TCanvas. El ejemplo principal, lo podemos encontrar en ibrt, una web dedicada a soluciones científicas e ingeniería. En mi ejemplo Thundax AVL Tree, muestro un pequeño diagrama montando el árbol con su balanceo. Si vamos añadiendo nodos, podremos ver que al final el árbol se ve bastante balanceado. Luego podéis analizar el código y ver como produce el equilibrado hacia la derecha o la izquierda. He adaptado el código para que me permita visualizar los nodos evitando mostrarlos simplemente en un TMemo, de ésta manera podemos asegurar que el algoritmo funciona correctamente y que al final los datos están nivelados.

Ejemplo con 8 nodos:

Ejemplo con 1000 nodos:


Podéis descargaros la aplicación desde aquí para que la podáis analizar: Thundax AVL Tree. Además podemos encontrar miles de aplicaciones por la red, y sobretodo applets en Java donde podemos ver su funcionamiento aún mejor:

AVL Tree Java Applet:
http://webpages.ull.es/users/jriera/Docencia/AVL/AVL%20tree%20applet.htm
http://www.site.uottawa.ca/~stan/csi2514/applets/avl/BT.html
http://www.cs.jhu.edu/~goodrich/dsa/trees/avltree.html

Aquí os dejo el código fuente del AVLTree, y su utilización.

AVLTree.pas:




// @Author : Jordi Coll 27/06/2009
//
// Taken from Nicklaus Wirth and Giacomo Policicchio:
// Algorithmen und Datenstrukturen ( in Pascal )
// Balanced Binary Trees p 250 ++
//

unit AVLTree;

interface

uses
classes, ExtCtrls, Types;

type
TAWLTreeItem = class(TObject)
Left: TAWLTreeItem;
Right: TAWLTreeItem;
balance: - 1..1;
positionL : TPoint;
positionR : TPoint;
private
count: integer;
public
constructor create;
function compare(a: TAWLTreeItem): Shortint; virtual; abstract;
procedure copy(ToA: TAWLTreeItem); virtual; abstract;
procedure list; virtual; abstract;
procedure Draw(point: TPoint; color: integer); virtual; abstract;
procedure DrawLine(pointO, PointD : TPoint; color : integer); virtual; abstract;
end;

TAWLTree = class(TPersistent)
root: TAWLTreeItem;
private
ItemCount: integer;
procedure Delete(item: TAWLTreeItem; var p: TAWLTreeItem; var h: boolean; var ok: boolean);
procedure SearchAndInsert(item: TAWLTreeItem; var p: TAWLTreeItem; var h: boolean; var Found: boolean);
function SearchItem(item: TAWLTreeItem; var p: TAWLTreeItem): boolean;
procedure balanceLeft(var p: TAWLTreeItem; var h: boolean; dl: boolean);
procedure balanceRight(var p: TAWLTreeItem; var h: boolean; dl: boolean);
procedure listitems(var p: TAWLTreeItem);
procedure DrawItems(var p: TAWLTreeItem; node: TPoint);
procedure DrawLines(var p: TAWLTreeItem; node: TPoint);
public
constructor Create;
destructor Destroy; override;
function add(item: TAWLTreeItem): boolean;
function remove(item: TAWLTreeItem): boolean;
function search(item: TAWLTreeItem): boolean;
procedure list;
procedure DrawNodes(Point: TPoint);
end;

implementation


constructor
TAWLTreeItem.create;
begin
inherited create;
count := 0;
end;

constructor TAWLTree.create;
begin
inherited create;
root := nil;
ItemCount := 0;
end;

destructor TAWLTree.destroy;
begin
while root <> nil do
remove(root);
inherited destroy;
end;

procedure TAWLTree.SearchAndInsert(item: TAWLTreeItem; var p: TAWLTreeItem; var h: boolean; var Found: boolean);
begin
found := false;
if p = nil then
begin
p := item;
h := true;
with p do
begin
if root = nil then
root := p;
count := 1;
left := nil;
right := nil;
balance := 0;
end;
end
else if (item.compare(p) > 0) then
begin
searchAndInsert(item, p.left, h, found);
if h and not found then
BalanceLeft(p, h, false);
end
else if (item.compare(p) < 0) then
begin
searchAndInsert(item, p.right, h, found);
if h and not found then
balanceRight(p, h, false);
end
else
begin
p.count := p.count + 1;
h := false;
found := true;
end;
end;

function TAWLTree.SearchItem(item: TAWLTreeItem; var p: TAWLTreeItem): boolean;
begin
result := false;
if (p = nil) then
result := false
else
begin
if (item.compare(p) = 0) then
result := true
else
begin
if (item.compare(p) > 0) then
result := searchitem(item, p.left)
else
begin
if (item.compare(p) < 0) then
result := searchitem(item, p.right)
end;
end;
end;
end;


procedure TAWLTree.balanceRight(var p: TAWLTreeItem; var h: boolean; Dl: boolean);
var
p1, p2: TAWLTreeItem;
begin
case p.balance of
-1:
begin
p.balance := 0;
if not dl then
h := false;
end;
0:
begin
p.balance := +1;
if dl then
h := false;
end;
+1:
begin
p1 := p.right;
if (p1.balance = +1) or ((p1.balance = 0) and dl) then
begin
p.right := p1.left;
p1.left := p;
if not dl then
p.balance := 0
else
begin
if p1.balance = 0 then
begin
p.balance := +1;
p1.balance := -1;
h := false;
end
else
begin
p.balance := 0;
p1.balance := 0;
end;
end;
p := p1;
end
else
begin
p2 := p1.left;
p1.left := p2.right;
p2.right := p1;
p.right := p2.left;
p2.left := p;
if p2.balance = +1 then
p.balance := -1
else
p.balance := 0;
if p2.balance = -1 then
p1.balance := +1
else
p1.balance := 0;
p := p2;
if dl then
p2.balance := 0;
end;
if not dl then
begin
p.balance := 0;
h := false;
end;
end;
end;
end;

procedure TAWLTree.balanceLeft(var p: TAWLTreeItem; var h: boolean; dl: boolean);
var
p1, p2: TAWLTreeItem;
begin
case p.balance of
1:
begin
p.balance := 0;
if not dl then
h := false;
end;
0:
begin
p.balance := -1;
if dl then
h := false;
end;
-1:
begin
p1 := p.left;
if (p1.balance = -1) or ((p1.balance = 0) and dl) then
begin
p.left := p1.right;
p1.right := p;
if not dl then
p.balance := 0
else
begin
if p1.balance = 0 then
begin
p.balance := -1;
p1.balance := +1;
h := false;
end
else
begin
p.balance := 0;
p1.balance := 0;
end;
end;
p := p1;
end
else
begin
p2 := p1.right;
P1.Right := p2.left;
p2.left := p1;
p.left := p2.right;
p2.right := p;
if p2.balance = -1 then
p.balance := +1
else
p.balance := 0;
if p2.balance = +1 then
p1.balance := -1
else
p1.balance := 0;
p := p2;
if dl then
p2.balance := 0;
end;
if not dl then
begin
p.balance := 0;
h := false;
end;
end;
end;
end;

procedure TAWLTree.Delete(item: TAWLTreeItem; var p: TAWLTreeItem; var h: boolean; var ok: boolean);
var
q: TAWLTreeItem;
procedure del(var r: TAWLTreeItem; var h: boolean);
begin
if r.right <> nil then
begin
del(r.right, h);
if h then
balanceLeft(r, h, True);
end
else
begin
r.copy(q);
q.count := r.count;
q := r;
r := r.left;
h := true;
end;
end;
begin
ok := true;
if (p = nil) then
begin
Ok := false;
h := false;
end
else if (item.compare(p) > 0) then
begin
delete(item, p.left, h, ok);
if h then
balanceRight(p, h, True);
end
else if (item.compare(p) < 0) then
begin
delete(item, p.right, h, ok);
if h then
balanceLeft(p, h, True);
end
else
begin
q := p;
if q.right = nil then
begin
p := q.left;
h := true;
end
else if (q.left = nil) then
begin
p := q.right;
h := true;
end
else
begin
del(q.left, h);
if h then
balanceRight(p, h, True);
end;
q.free;
end;
end;

function TAWLTree.add(item: TAWLTreeItem): boolean;
var
h, found: boolean;
begin
SearchAndInsert(item, root, h, found);
add := found;
end;

function TAWLTree.remove(item: TAWLTreeItem): Boolean;
var
h, ok: boolean;
begin
Delete(item, root, h, ok);
remove := ok;
end;

function TAWLTree.Search(item: TAWLTreeItem): Boolean;
begin
result := SearchItem(item, root);
end;

procedure TAWLTree.listitems(var p: TAWLTreeItem);
begin
if p <> nil then
begin
if (p.left <> nil) then
listitems(p.left);
p.list;
if (p.right <> nil) then
listitems(p.right);
end;
end;

procedure TAWLTree.list;
begin
listitems(root);
end;

procedure TAWLTree.DrawItems(var p: TAWLTreeItem; node: TPoint);
var
pLeft, pRight : TPoint;
begin
if p <> nil then
begin
if (p.left <> nil) then
begin
pLeft := Point(node.x - 6, node.y + 20);
p.Draw(pLeft, $003005FA);
p.positionL := pLeft;
DrawItems(p.left, Point(pLeft.x - 3 , pLeft.y + 20));
end;

if (p.right <> nil) then
begin
pRight := point(node.x + 6, node.y + 20);
p.Draw(pRight, $005BFD84);
p.positionR := pRight;
DrawItems(p.right, Point(pRight.x + 3 , pRight.y + 20));
end;
end;
end;

procedure TAWLTree.DrawLines(var p: TAWLTreeItem; node: TPoint);
begin
if p <> nil then
begin
if (p.left <> nil) then
begin
p.DrawLine(node, p.positionL, $00F7F7F7);
DrawLines(p.left, p.positionL);
end;

if (p.right <> nil) then
begin
p.DrawLine(node, p.positionR, $00F7F7F7);
DrawLines(p.right, p.positionR);
end;
end;
end;

procedure TAWLTree.DrawNodes(Point: TPoint);
begin
root.Draw(Point, $004AFFFF);
root.positionL := Point;
root.positionR := Point;
DrawItems(root, Point);
DrawLines(root,Point);
end;

end.






Utilización:




type
TmyTreeItem = class(TAWLTreeItem)
public
data: integer;
constructor create(i: integer);
function compare(a: TAWLTreeItem): Shortint; override;
procedure copy(ToA: TAWLTreeItem); override;
procedure list; override;
procedure Draw(point: TPoint; color: integer); override;
procedure DrawLine(pointO, PointD: TPoint; color: integer); override;
end;

constructor TmyTreeItem.create(i: integer);
begin
inherited create;
data := i;
end;

function TmyTreeItem.compare(a: TAWLTreeItem): Shortint;
begin
result := 0;
if TmyTreeItem(a).data < data then
result := -1
else if TmyTreeItem(a).data = data then
result := 0
else if TmyTreeItem(a).data > data then
result := 1;
end;

procedure TmyTreeItem.copy(ToA: TAWLTreeItem);
begin
TmyTreeItem(ToA).data := data;
end;

procedure TmyTreeItem.list;
begin
form3.memo1.lines.add(inttostr(data));
end;

procedure TmyTreeItem.Draw(point: TPoint; color: integer);
begin
form3.DrawPoint(point, color);
end;

procedure TmyTreeItem.DrawLine(pointO, PointD: TPoint; color: integer);
begin
form3.DrawLine(pointO, pointD, color);
end;

procedure TForm3.Button2Click(Sender: TObject);
begin
bt.remove(TmyTreeItem.create(StrToInt(Edit3.text)));
listClick(sender);
end;

procedure TForm3.AddData(Sender: TObject);
var
bti: TmyTreeItem;
i: integer;
begin
bt.destroy;
bt := TAWLTree.create;
for i := 0 to StrToInt(Edit1.text) - 1 do
begin
bti := TmyTreeItem.create(1 + random(11) + random(10000));
bt.add(bti);
end;
listing();
end;

procedure TForm3.listing();
begin
memo1.clear;
bt.list;
DrawRectangle(image1, clblack, clblack);
bt.DrawNodes(Point(219, 10));
end;




Fijaros en la implementación de la utilización de la clase TAWLTreeItem donde todos sus métodos son abstractos. Luego en la clase que hereda de esta, sobreescribo los métodos y los redirecciono al formulario donde tengo el TImage. Luego a partir de unos puntos calculados dibujo éstos en el formulario y hago las conexiones guardándome la posición del nodo.

Éste ejemplo es meramente didáctico y puede que a algún estudiante le pueda ayudar a entender un poco mejor esta estructura de datos. Podemos encontrar diversas implementaciones del algoritmo en diferentes lenguajes. También os dejo un recopilatorio de enlaces dónde podemos encontrar el código fuente de ésta EI y poder utilizarla en nuestras aplicaciones.

Java AVL Tree:
AVLTree.java

C AVL Tree:
AVLTree.c

Ruby AVL Tree:
RubyAVL
  • Enlaces de interés:
Algorithm Repository
Árbol AVL