|
INTRODUCCIÓN
A pesar de la extremada capacidad, potencia y
velocidad que ofrecen los ordenadores de última
generación aún son incapaces de aproximarse en
términos de abstracción a una mínima fracción de
las posibilidades del cerebro humano, por ello
siempre es necesario optimizar las técnicas de
programación para conseguir el máximo rendimiento
con el menor consumo de recursos de procesador.
La algoritmia junto a la metodología de procesos
trata de estudiar el conjunto finito de expresiones
aritméticas y lógicas que, debidamente ordenadas,
conducen a la solución de un problema concreto. La
algoritmia computacional persigue por todos los
medios aproximar la forma de actuar de los
ordenadores a la forma del razonamiento humano.
Para un ser humano determinar que un objeto
se encuentra situado en una determinada posición,
que es verde, azul, un avión o un florero, es tan
sencillo como observar y resolver de forma
inmediata el problema, por el contrario le resulta
extremadamente difícil recordar una lista de una
veintena de números aleatorios, sin embargo el mas
humilde de los ordenadores es capaz de recordar
cientos de miles de datos con absoluta precisión.
El verdadero problema comienza a la hora de
realizar la búsqueda de un determinado dato entre
toda la información existente y es en este sentido
en el que debemos volcarnos hacia la abstracción
ESTRUCTURAS DE DATOS
Un conjunto de items debe encontrarse recogido en
una estructura de datos siendo ésta lineal o no
lineal, ordenada o desordenada. Entre las
estructuras lineales nos encontramos con Arrays,
Vectores, Listas encadenadas, Pilas y Colas; y
entre las no lineales con Mapas Hashing y Mapas de
Árboles, siendo esta última la que usaremos en el
desarrollo de la librería acxTreeMap.
El árbol es una estructura de datos muy importante
en informática y se utiliza para realizar búsquedas
en grandes volúmenes de información , pero también
es la base en la que se apoyan otros métodos como
algoritmos de cifrado, redes neuronales, bases de
datos, compiladores y una larga lista de utilidades
que sería difícil recoger en este documento.
Este método está comúnmente aceptado por la mayoría
de desarrolladores por su excelente velocidad de
respuesta independientemente de la magnitud de
datos contenidos, de hecho podemos observar en las
siguientes figuras la comparativa de respuesta
entre un array desordenado (n), dicotómica en un
vector ordenado nlog(n) y por último sobre un árbol
binario log(n).
|
Items |
Secuencial |
Ordenado |
Binario |
|
1 |
1,000 |
1,000 |
1,000 |
|
2 |
2,000 |
1,602 |
1,301 |
|
3 |
3,000 |
1,954 |
1,477 |
|
4 |
4,000 |
2,204 |
1,602 |
|
5 |
5,000 |
2,398 |
1,699 |
|
6 |
6,000 |
2,556 |
1,778 |
|
7 |
7,000 |
2,690 |
1,845 |
|
8 |
8,000 |
2,806 |
1,903 |
|
9 |
9,000 |
2,908 |
1,954 |
|
10 |
10,000 |
3,000 |
2,000 |
|
11 |
11,000 |
3,083 |
2,041 |
|
12 |
12,000 |
3,158 |
2,079 |
|
13 |
13,000 |
3,228 |
2,114 |
|
 |
|
Items |
Secuencial |
Ordenado |
Binario |
|
1 |
1,000 |
1,000 |
1,000 |
|
2 |
2,000 |
1,602 |
1,301 |
|
3 |
3,000 |
1,954 |
1,477 |
|
5 |
5,000 |
2,398 |
1,699 |
|
8 |
8,000 |
2,806 |
1,903 |
|
13 |
13,000 |
3,228 |
2,114 |
|
21 |
21,000 |
3,644 |
2,322 |
|
34 |
34,000 |
4,063 |
2,531 |
|
55 |
55,000 |
4,481 |
2,740 |
|
89 |
89,000 |
4,899 |
2,949 |
|
144 |
144,000 |
5,317 |
3,158 |
|
233 |
233,000 |
5,735 |
3,367 |
|
377 |
377,000 |
6,153 |
3,576 |
|
610 |
610,000 |
6,571 |
3,785 |
|
987 |
987,000 |
6,989 |
3,994 |
|
1.597 |
1.597,000 |
7,407 |
4,203 |
|
2.584 |
2.584,000 |
7,825 |
4,412 |
|
4.181 |
4.181,000 |
8,243 |
4,621 |
|
6.765 |
6.765,000 |
8,661 |
4,830 |
|
10.946 |
10.946,000 |
9,079 |
5,039 |
|
17.711 |
17.711,000 |
9,496 |
5,248 |
|
28.657 |
28.657,000 |
9,914 |
5,457 |
|
46.368 |
46.368,000 |
10,332 |
5,666 |
|
75.025 |
75.025,000 |
10,750 |
5,875 |
|
 |
Los algoritmos relativos a árboles binarios se
encuentran ampliamente documentados en la
bibliografía temática e incluso se pueden encontrar
algunos interesantes artículos en internet.
Es razonable pensar que no descubro nada nuevo en
este documento, y efectivamente así es siempre y
cuando no tengamos presente que el desarrollo está
realizado exclusivamente en Visual Basic 6.0.
El origen de este empeño que en opinión de algunos
miembros pueda parecer carente de sentido, se
encuentra en le interés personal por demostrar que
con Visual Basic es posible construir herramientas
que poco o nada tienen que envidiar a aquellas
construidas con otros lenguajes de más bajo nivel.
Bien cierto es que con C y ensamblador podemos
dialogar con el procesador en petit-comité, pero la
mala prensa de VB puede disiparse con utilidades
como la que trato de exponer en este artículo y con
otras de autores de incuestionable prestigio.
LA TEORÍA
Un árbol binario funciona de forma que cualquier
dato insertado pasa a ocupar la posición jerárquica
que ‘casi por derecho’ le corresponde, en otros
términos podríamos decir que trata de igualarse al
pensamiento humano. Los datos más pequeños están a
la izquierda y los mayores a la derecha.
En la imagen podemos ver una estructura de árbol
binario cuyos valores representan la clave por la
que buscaremos un determinado item dentro del
conjunto de datos, pero ¿ como lo hacemos ¿. A
partir de este punto vamos a diferenciar las
búsquedas lineales de las dicotómicas y binarias.
Supongamos que el valor de clave deseado es 70. El
primer paso es interrogar el nodo raíz del árbol,
el cual mantendremos actualizado de forma
persistente.
Si comparamos el nodo raíz (30) con el valor
buscado podemos afirmar que en la parte izquierda
del árbol no lo encontraremos por lo tanto –Regla
dicotómica- todos los nodos situados a la izquierda
del nodo raíz los descartamos (Pueden ser tres
nodos, tres mil o tres mil millones de nodos) con
lo que podemos asegurar que nuestra búsqueda se
reduce en principio a N/2 items siempre y cuando el
árbol se encuentre equilibrado.
Tomamos ahora el nodo hijo del raíz (60)
transformándolo como raíz desde este momento.
Volvemos a realizar una comparación descartando
todos los nodos que se encuentran a la izquierda de
(60), reduciendo en la segunda búsqueda a N/22.
Continuaremos sucesivamente hasta alcanzar el dato
deseado.
Para comprenderlo mejor, vamos a observar el nodo
raíz un poco más de cerca entrando de lleno en
álgebra de punteros (Pido perdón a los puristas
porque pensarán que estoy sugiriendo que VB es
capaz de gestionar punteros).
|
Padre |
0 |
|
Id nodo |
Valor |
| 5 |
30 |
|
Hijo Menor |
Hijo Mayor |
| 3 |
1 |
Como podemos observar cada nodo del árbol ha de ser
capaz de acceder a la información de los nodos que
le rodean; Padre, hijo menor e hijo mayor, y a sus
propios datos. Esta estructura nos va a permitir
una extraordinaria agilidad en la manipulación de
los datos contenidos en la tabla por la adecuada
gestión de sus punteros.
Para ello vamos a transformar la estructura típica
de C.
typedef struct nodo *treenode
struct nodo {
int datos;
treenode izq, dch, padre;
}
Por la que a partir de este momento será nuestra
piedra angular en Visual Basic.
Public Type nodo
key As String
nkeys As Integer
item() As Variant
izq As Long
dch As Long
padre As Long
End Type
Con esta estructura básica tendremos que construir
una tabla a medida que se añadan nuevos items en el
árbol. Como Visual Basic no dispone de ningún
método que nos permita asignar memoria dinámica,
vamos a utilizar la capacidad de redimensionar
arrays implementando nuestra particular aritmética
de punteros.
En cada nodo vamos a mantener actualizada la
siguiente información.
KEY Valor de la clave contenida en el nodo
NKEYS Número de items de datos que contiene la
clave (Duplicadas)
ITEM() Array que contendrá los datos vinculados al
valor de la clave
IZQ Índice de la tabla de array que apunta al valor
inmediato inferior
DCH Ídem para el valor inmediato
superior
PADRE Índice troncal del nodo.
Observemos en la tabla y esquema que se muestran a
continuación, como quedaría constituida la
estructura de datos tras insertar -en este mismo
orden- los items cuyos valores de clave son
30;60;25;27;50
|
Id |
Key |
Items |
Datos |
PDR |
IZQ |
DCH |
| 1 |
30 |
1 |
{datos} |
3 |
2 |
0 |
| 2 |
60 |
1 |
{datos} |
5 |
0 |
1 |
| 3 |
25 |
1 |
{datos} |
0 |
4 |
1 |
| 4 |
27 |
1 |
{datos} |
0 |
0 |
3 |
| 5 |
50 |
1 |
{datos} |
0 |
0 |
2 |
Curiosamente, y a diferencia de un vector ordenado,
los items de un árbol se insertan en la tabla en la
misma secuencia en la que se reciben, manteniendo
la posición a lo largo de toda su existencia. Esta
particularidad es la que permite conseguir una
óptima velocidad de manipulación de datos, pues
éstos nunca cambian su posición inicial manteniendo
su orden lógico por actualización simple de
punteros.
No podemos pasar por alto el equilibrio de un
árbol, pieza fundamental para su correcto
funcionamiento. Cuesta creer que el caso más
desfavorable en el que se encuentra un árbol
binario es aquel en el que recibe una lista de
items totalmente ordenada, transformándose
automáticamente en una lista doblemente encadenada.
Veamos esquemáticamente como se comporta un árbol
cuando recibe una lista de claves tal que
1;2;3;4;5;6;7
Este es el caso típico de un árbol desequilibrado
en el que resulta necesario recorrer los nodos de
forma secuencial para localizar un determinado
valor de clave. Para evitar este inconveniente será
necesario construir en nuestro componente un método
que mantenga el árbol perfectamente balanceado.
Está técnica se denomina Red-Black-Node y ejecuta
una rotación de punteros a derecha o izquierda
dependiendo del peso aparente de desequilibrio del
árbol.
Aplicándola al ejemplo anterior el resultado sería
el siguiente.
Nombre
Leonardo
Pradera Osterman
Ubicación
Madrid - España
Nota del Webmaster
Leonardo (Acalanto) se ha convertido desde los comienzos
de VB-MUNDO en un engranaje fundamental del sitio. Sus
conocimientos, Participaciones y lecciones brindados en el
foro son sin duda de las delicias de los usuarios
Este amigo Ingeniero posee excelentes conocimientos en el
desarrollo de aplicaciones para ingeniería civil y ha
desarrollado numerosos aplicativos para ese rubro.
Si quieres
conocer más sobre Leonardo haz clic
aquí
Si quieres acceder a nuestro
exclusivo foro haz clic
aquí
|
|
Descarga
desde nuestra exclusiva sección de códigos fuente, todas las
aplicaciones que desees y utiliza ese código en tus aplicaciones
para dotarlas de la mayor versatilidad posible.
Accede
a nuestra sección de Notas Técnicas, escritas por nuestro Staff y
por otros prestigiosos colaboradores. Notas sobre informática en
General, VB.NET, C#, y Hardware. Conviertete tu también en NOTERO de
VB-MUNDO y gánate tu propia sección y un link (no reciproco) hasta
tu sitio web. Deseas escribir para nosotros ?