jueves, 23 de febrero de 2017

Programación del Sinclair QL (XXI): Estructura de datos. Arbol binario de Búsqueda balanceado



Como dije en la entrada anterior, el problema de los árboles binarios de búsqueda (ABB) es que si no están bien balanceados pierden mucha efectividad, el caso extremo es introducir los datos en orden, ya que estamos generando una lista pero con la ocupación y la mayor complejidad de un árbol.

Balancear el árbol significa que en cada nodo los elementos que cuelguen por su izquierda sean los mismos que los que cuelgan por su derecha, esta circunstancia ideal es compleja, por lo que se mira que la profundidad de las dos ramas sea la misma, un sistema un poco mas sencillo de conseguir y que sigue manteniendo el balanceo. Si una rama tiene elementos de mas profundidad que la otra, el árbol se balancea para compensarlo mediante lo que se denomina una rotación.

Aunque existen varias formas de montar los ABB balanceados, las formas mas utilizadas en general son los siguientes (aunque en general se usan solo los tres primeros):

  • Los árboles AVL son los ABB auto-balanceados mas antiguos y los que consiguen mantener el mejor balanceo.
  • Los montículos son ABB balanceados almacenados en forma de arreglo, mas adelante los usaremos en el conocido algoritmo de ordenación Heapsort.
  • Los árboles rojo-negro son menos estrictos en el balanceo, permitiendo ligeras descompensaciones, por lo que son un poco mas ágiles en inserciones.
  • Los árboles AA son una variación de los rojo-negro que simplifica mas las inserciones.
  • Los árboles biselados son ABB balanceados cuyos nodos recientemente visitados se rotan para que aparezcan lo antes posible en las búsquedas.
  • Los árboles de Fibonacci son una variante de los AVL.
Voy a modificar el árbol para que se comporte como un árbol AVL, llamado así por el nombre de sus creadores, los matemáticos rusos Gueorgui Adelsón-Velski y Yevgueni Landis, que lo definieron en un artículos publicado en 1962.

En una árbol AVL hay que conocer la profuncidad de cada rama del árbol, para poder mantenerlo siempre balanceado. Si la profundidad de la rama izquierda difiere en más de una unidad de la profundidad de la rama derecha, el árbol está desbalanceado y se procede a efectuar una rotación para equilibrarlo, se retrocede al padre de ese nodo y se repite la operación, subiendo hacia la raíz hasta que no se requieran mas balanceos. Para poder ir subiendo por las ramas del árbol debemos guardar el camino recorrido, lo que se consigue de forma sencilla usando recursividad en lugar de iteración, por eso cambiaremos el algoritmo de inserción para convertirlo en recursivo.

Para equilibrar un árbol hay que mover nodos, en lo que se denominan rotaciones, se basan en ver la diferencia de profundidad de un nodo entre sus ramas izquierda y derecha, y si la diferencia es mayor de 1 realizar una rotación en el nodo, intercambiándolo con su hijo. Depende del hijo que usemos para rotar se denominará rotación a la izquierda o rotación a la derecha, pero ambas son equivalentes. También dependiendo del nodo ocupado del elemento hijo se usará una rotación simple o una doble. Pongo un ejemplo sencillo de rotación simple a la derecha y otro de rotación doble izquierda-derecha:


Vemos que en primer caso el nodo 1 es el que usamos para rotar, ya que tiene cero hijos por su izquierda y dos por su derecha necesita una rotación derecha. Colgamos el nodo (1) a la izquierda de su nodo hijo (2), y luego colgamos el nodo hijo (2) en lugar del nodo seleccionado. Podemos imaginar que estiramos hacia arriba del nodo (2).

Si el nodo izquierdo está ocupado, no es posible poner allí el nodo seleccionado, por lo que necesitamos dos pasos, primero colgamos el nodo hijo (3) a la derecha de su sub-nodo izquierdo (2), y luego colgamos el sub-nodo izquierdo del nodo seleccionado (1). Ahora tenemos ya el caso anterior y usando el mismo sistema equilibramos el árbol.

Entendiendo bien esto es muy sencillo equilibrar los árboles en las altas y bajas, solo hay que ir subiendo por el árbol a partir del nodo seleccionado, ver las profundidades de ambos nodos, y actuar en consecuencia. Hay varios sistemas para mantener las alturas en el árbol, lo mas sencillo es guardar la altura de las sub-ramas izquierda y derecha pero necesitamos dos valores en cada nodo, la otra forma es mantener solo la diferencia de alturas y así usamos un solo valor en cada nodo.

lunes, 19 de diciembre de 2016

Traducciones en la Wikipedia

Estas son mis últimas traducciones:

  • La gama de computadores UNIVAC, separado del UNIVAC I a donde redirigía
  • Códigos de caracteres de 6 bits, que fueron muy usados en los UNIVAC y en los DEC por ejemplo, igual que en muchos de los primeros ordenadores.
  • Entrada sobre ordenadores decimales, en general los primeros ordenadores fueron casi todos decimales (con la excepción de los Zuse, el sistema mecánico que empleó en la Z1 para almacenar datos binarios fue una gran idea, y la fuente de sus principales problemas, luego pasó a los relés y se solucionaron) hasta que se impuso el binario.
  • Entrada sobre la empresa Remington Rand
  • Entrada sobre Herman Lukoff y entrada sobre John Grist Brainerd, pioneros poco conocidos de la informática.

viernes, 16 de diciembre de 2016

Programación del Sinclair QL (XX): Estructuras de datos. Presentar el árbol



La presentación de los datos que hacía del árbol no eran muy adecuadas, en las listas se ve mejor pero el árbol cuesta mas de ver presentando en forma lineal los valores de datos y enlaces, por lo que he desarrollado un proceso para ver de manera mas gráfica los árboles, en modo texto, pero queda bastante visible. Hay dos procesos, uno que presenta el árbol que es nuevo, y el que retorna la lista de elementos del árbol en una cadena que he simplificado la visualización.

4890 REMark --------------------------------------------------------------
4900 REMark -- ARBOL_VER_GR -- Presenta en pantalla un arbol            --
4910 REMark --------------------------------------------------------------
4920 DEFine PROCedure ARBOL_VER_GR
4930   LOCal lin,col,a$
4940   :
4950   lin = ARBOL_NIVELES - 1
4960   col = 1 : FOR i=2 TO lin+2 : col = (2 * col)
4970   OPEN#5,con : WINDOW#5, 448,200,32,16
4980   CLS#5 : BORDER#5, 2,2
4990   PRINT#5, "N:";!ARBOL_NIVELES;!"L:";lin;!"C:";col-2,
5000   PRINT #5,ARBOL_ELEMENTOS$
5010   montar 0,col/2-1,col/4,A_RAIZ
5020   INPUT a$
5030   CLOSE#5
5040 END DEFine 
5050 :
5060 DEFine PROCedure montar(l,c,s,nodo)
5070   LOCal i,t
5080   :
5090   IF nodo <> P_NULO THEN 
5100     imprime l+1,c+1, ArrArbol(nodo)
5110     IF ArrDer(nodo) <> P_NULO THEN 
5120       t = c+s+1
5130       FOR i=c+2 TO t-1 : imprime l+1,i,"-"
5140       imprime l+1, t, "\"
5150       imprime l+2, t, "|"
5160     END IF 
5170     IF ArrIzq(nodo) <> P_NULO THEN 
5180       t = c-s+1
5190       FOR i=c TO t+1 STEP -1 : imprime l+1,i,"-"
5200       imprime l+1, t, "/"
5210       imprime l+2, t, "|"
5220     END IF 
5230     montar l+2,c-s,s/2,ArrIzq(nodo)
5240     montar l+2,c+s,s/2,ArrDer(nodo)
5250   END IF 
5260 END DEFine 
5270 :
5280 DEFine PROCedure imprime(l,c,dato$)
5290   IF (l > 0) AND (l < 19) AND (c > 0) AND (c < 73) THEN 
5300     AT#5,l,c : PRINT#5, dato$
5310   END IF 
5320 END DEFine 
5330 :
5340 REMark --------------------------------------------------------------
5350 REMark -- v$ = ARBOL_ELEMENTOS$ -- Muestra la lista de elementos   --
5360 REMark -- RETORNA: Lista ordenada de elementos del arbol           --
5370 REMark --------------------------------------------------------------
5380 DEFine FuNction ARBOL_ELEMENTOS$
5390   LOCal lista$
5400   :
5410   lista$=""
5420   inorden lista$,A_RAIZ
5430   RETurn lista$
5440 END DEFine 
5450 :
5460 DEFine PROCedure inorden(cadena$,nodo)
5470   IF nodo <> P_NULO THEN 
5480     inorden cadena$, ArrIzq(nodo)
5490     IF LEN(cadena$) <> 0 THEN cadena$ = cadena$ & ","
5500     cadena$ = cadena$ & ArrArbol(nodo)
5510     inorden cadena$, ArrDer(nodo)
5520   END IF 
5530 END DEFine<0 hay="" libres="" no="">
 
El resultado es el siguiente, no es espectacular pero creo que se ve bien la estructura del árbol, y cuando entremos en los árboles AVL y las rotaciones se verá de forma mas clara como se van moviendo los datos.


Aquí los fuentes de todo lo desarrollado sobre estructuras de datos hasta el momento, la parte de ordenación no ha variado.

martes, 13 de diciembre de 2016

Programación del Sinclair QL (XIX): Estructura de datos. Arbol binario de Búsqueda



Los arboles son las estructuras mas usadas para almacenar datos, ya que permiten un muy rápido acceso a ellos. La estructura en sencilla, un registro se divide en dos partes, una con los datos que se necesitan guardar y otro con enlaces a los elementos hijos, que será un número mayor o igual a dos.

Ejemplo de arbol (Fuente: Monografias.com)


Si el número máximo de hijos es dos se denominan árboles binarios, y son los mas usados en programación en general, reservando los árboles de mas ramas para uso en ficheros indexados habitualmente. No voy a explicar mucho mas, hay suficiente información en la Web sobre arboles y su manejo.

Existe un tipo especial de árbol binario, en el que en cada nodo de cada rama, los valores de los elementos que cuelgan del nodo izquierdo son todos menores al valor del propio nodo, y los elementos que cuelgan del nodo derecho son todos valores mayores al del propio nodo, de forma que si recorremos el árbol primero la rama izquierda, luego el nodo, y luego la rama derecha, obtenemos una lista de elementos ordenados en orden creciente. Si la recorremos primero la rama derecha, luego el nodo y después la rama izquierda obtenemos la lista ordenada en forma decreciente. Este tipo de árboles se llaman "Árbol Binario de Búsqueda", y es lo que voy a implementar, ya que estamos hablando de algoritmos de ordenación. 

Voy a usar tres arreglos para almacenar los datos, en uno me guardo los datos del registro (en este caso será una lista de números, pero puede ser cambiado de manera sencilla a una lista de cadenas por ejemplo), otro arreglo numérico con los enlaces a los punteros de la rama izquierda, y un tercer arreglo con los enlaces a la rama derecha. Estos dos arreglos podrían ser uno solo, pero creo que así está un poco mas claro.

Usaré el arreglo de enlaces a nodos izquierdos para almacenar la lista de elementos libres, pero por que sea mas visual haré lo mismo con los derechos. Esto lo cambiaré mas adelante por algo un poco mejor, ya lo veremos. El manejo de los árboles requiere muchos procedimientos recursivos, aunque usaré iterativos cuando sea posible para que se vean varias técnicas de manejo.

Uso una variable para almacenar el nivel máximo de profundidad del árbol, no tiene uso mas que para enseñarlo en pantalla, pero me permite que se vea algo que deseo demostrar luego. No me voy a complicar mucho cuando compacto el árbol, ya que esta parte la voy a cambiar luego, solo lo pongo de momento para que se vea.

2000 REMark --------------------------------------------------------------
2010 REMark -- ESTRUCTURAS DE DATOS                                     --
2020 REMark --   Modulo....: Arbol binario                              --
2030 REMark --   Objetivo..: Arbol binario usando un arreglo de valores --
2040 REMark --               numericos y dos para los punteros          --
2050 REMark --   Autor.....: javu61, 12/2016                            --
2060 REMark --   Procesos..:                                            --
2070 REMark --     ARBOL_CREAR      -- Crear el arbol                   --
2080 REMark --     ARBOL_NUEVO(tam) -- Crea el arbol con un tama‰o      --
2090 REMark --     b=ARBOL_LEN      -- Nro de elementos del arbol       --
2100 REMark --     b=ARBOL_NIVELES  -- Nro de niveles del arbol         --
2110 REMark --     b=ARBOL_BUSCAR(n)-- Busca un elemento en el arbol    --
2120 REMark --     ARBOL_ADD(dato)  -- Introduce un dato en el arbol    --
2130 REMark --     ARBOL_DELETE(n)  -- Borra el elemento n del arbol    --
2140 REMark --     v$=ARBOL_VER$    -- Muestra los elementos del arbol  --
2150 REMark --     ARBOL_CAMBIA(tam)-- Cambia el tama‰o del arbol       --
2160 REMark --   Procesos de uso interno:                               --
2170 REMark --     ARBOL_INIT       -- Inicializa una arbol             --
2180 REMark --     b=ARBOL_EL_LIBRE -- Retorna elemento libre           --
2190 REMark --     n=ARBOL_NIVELES  -- Retorna nro de niveles del arbol --
2200 REMark --   Elementos.: Se usan los siguientes elementos globales  --
2210 REMark --     A_TAM           -- Tama‰o del arreglo                --
2220 REMark --     A_FACTOR        -- Factor de crecimiento             --
2230 REMark --     ArrArbol(tam)   -- Elementos del arbol               --
2240 REMark --     ArrIzq(tam)     -- Puntero al elemento izquierdo     --
2250 REMark --     ArrDer(tam)     -- Puntero al elemento derecho       --
2260 REMark --     P_NULO          -- Puntero nulo                      --
2270 REMark --     P_VACIO         -- Puntero vacio                     --
2280 REMark --     A_RAIZ          -- Puntero al nodo raiz              --
2290 REMark --     A_NRO           -- Nro de elementos del arbol        --
2300 REMark --     A_NIVELES       -- Nro de niveles del arbol          --
2310 REMark --------------------------------------------------------------
2320 :
2330 :
2340 REMark --------------------------------------------------------------
2350 REMark -- ARBOL_CREAR -- Crea el arbol                             --
2360 REMark --------------------------------------------------------------
2370 DEFine PROCedure ARBOL_CREAR
2380   REMark Espacio para 10 elementos, crece minimo 5
2390   ARBOL_NUEVO 9,5
2400 END DEFine 
2410 :
2420 REMark --------------------------------------------------------------
2430 REMark -- ARBOL_NUEVO(tam,fac) -- Crea el arbol con un tama‰o y un --
2440 REMark --                         factor de crecimiento            --
2450 REMark --------------------------------------------------------------
2460 DEFine PROCedure ARBOL_NUEVO(tam,fac)
2470   LOCal i
2480   :
2490   LET P_NULO   = -1        : REMark Puntero nulo
2500   LET P_VACIO  = -2        : REMark Puntero vacio
2510   LET A_RAIZ   = P_NULO    : REMark Puntero al nodo raiz
2520   LET A_NIVELES= 0         : REMark Nro de niveles del arbol
2530   LET A_NRO    = 0         : REMark Nro de elementos del arbol
2540   LET A_TAM    = tam       : REMark Tama‰o del arreglo
2550   LET A_FACTOR = fac       : REMark Factor de crecimiento
2560   DIM ArrIzq(tam)          : REMark Punteros al elemento izquierdo
2570   DIM ArrDer(tam)          : REMark Punteros al elemento derecho
2580   DIM ArrArbol(tam)        : REMark Elementos del arbol
2590   :
2600   REMark Inicializa arbol de elementos libres
2610   FOR i=0 TO A_TAM : ArrIzq(i) = P_VACIO : ArrDer(i) = P_VACIO
2620 END DEFine 
2630 :
2640 REMark --------------------------------------------------------------
2650 REMark -- b = ARBOL_LEN -- Retorna el nro de elementos del arbol --
2660 REMark -- RETORNA: 0 si vacio, >0 = nro de elementos               --
2670 REMark --------------------------------------------------------------
2680 DEFine FuNction ARBOL_LEN
2690   RETurn A_NRO
2700 END DEFine 
2710 :
2720 REMark --------------------------------------------------------------
2730 REMark -- b = ARBOL_NIVELES -- Retorna el nro de niveles del arbol --
2740 REMark -- RETORNA: 0 si vacio, >0 = nro de elementos               --
2750 REMark --------------------------------------------------------------
2760 DEFine FuNction ARBOL_NIVELES
2770   RETurn A_NIVELES
2780 END DEFine 
2790 :
2800 REMark --------------------------------------------------------------
2810 REMark -- b = ARBOL_EL_LIBRE -- Retorna elemento libre del arbol   --
2820 REMark -- RETORNA:  <0 hay="" libres="" no="">=0 nro del elemento         --
2830 REMark --------------------------------------------------------------
2840 DEFine FuNction ARBOL_EL_LIBRE
2850   LOCal i
2860   :
2870   FOR i=0 TO A_TAM
2880     IF ArrIzq(i) = P_VACIO THEN RETurn i
2890   END FOR i
2900   RETurn P_NULO
2910 END DEFine 
2920 :
2930 REMark --------------------------------------------------------------
2940 REMark -- b = ARBOL_BUSCAR(valor) -- Busca un elemento en el arbol --
2950 REMark -- RETORNA:  nro del elemento o NULO si no encontrado       --
2960 REMark --------------------------------------------------------------
2970 DEFine FuNction ARBOL_BUSCAR(valor)
2980   LOCal nro,repetir
2990   :
3000   nro = A_RAIZ
3010   REPeat repetir
3020     IF nro = P_NULO THEN EXIT repetir
3030     IF ArrArbol(nro) = valor THEN EXIT repetir
3040     IF ArrArbol(nro) < valor THEN 
3050       nro = ArrDer(nro)
3060     ELSE 
3070       nro = ArrDer(nro)
3080     END IF 
3090   END REPeat repetir
3100   RETurn nro
3110 END DEFine 
3120 :
3130 :
3140 REMark --------------------------------------------------------------
3150 REMark -- ARBOL_ADD(dato) -- Introduce un dato en el arbol, si     --
3160 REMark --                    esta llena crece al doble             --
3170 REMark --------------------------------------------------------------
3180 DEFine PROCedure ARBOL_ADD(dato)
3190   LOCal repetir,nro,pos,nivel
3200   :
3210   REMark Busco nodo libre, crece si hace falta y ubico el elemento
3220   REPeat repetir
3230     nro = ARBOL_EL_LIBRE
3240     IF nro <> P_NULO THEN EXIT repetir
3250     ARBOL_CAMBIA(A_TAM*2)
3260   END REPeat repetir
3270   ArrArbol(nro) = dato
3280   ArrIzq(nro) = P_NULO
3290   ArrDer(nro) = P_NULO
3300   nivel = 1
3310   :
3320   REMark Si es el primer nodo, lo ubico en la raiz
3330   IF A_RAIZ = P_NULO THEN 
3340     A_RAIZ = nro
3350   ELSE 
3360     REMark Si no es el primero, buscamos su posicion recorriendo
3370     pos = A_RAIZ
3380     REPeat repetir
3390       nivel = nivel + 1
3400       REMark Si es menor o igual pasamos a la izquierda
3410       IF (ArrArbol(pos) > dato) THEN 
3420         IF (ArrIzq(pos)=P_NULO) THEN 
3430           ArrIzq(pos) = nro
3440           EXIT repetir
3450         END IF 
3460         pos = ArrIzq(pos)
3470       ELSE 
3480         :
3490         REMark Si es mayor pasamos a la derecha
3500         IF (ArrDer(pos)=P_NULO) THEN 
3510           ArrDer(pos) = nro
3520           EXIT repetir
3530         END IF 
3540         pos = ArrDer(pos)
3550       END IF 
3560     END REPeat repetir
3570   END IF 
3580   :
3590   REMark Sumo un elemento al arbol y miro el nivel
3600   A_NRO = A_NRO + 1
3610   IF nivel > A_NIVELES THEN A_NIVELES = nivel
3620   :
3630 END DEFine 
3640 :
3650 REMark --------------------------------------------------------------
3660 REMark -- v$ = ARBOL_VER$ -- Muestra el arbol                      --
3670 REMark -- RETORNA: Lista de elementos del arbol                    --
3680 REMark --------------------------------------------------------------
3690 DEFine FuNction ARBOL_VER$(hastanivel)
3700   LOCal lista$
3710   :
3720   IF ARBOL_LEN = 0 THEN 
3730     PRINT "Error: Arbol vacio"
3740     STOP
3750   END IF 
3760   :
3770   lista$=""
3780   inorden A_RAIZ,hastanivel,lista$,1
3790   RETurn lista$
3800 END DEFine 
3810 :
3820 DEFine PROCedure inorden(nodo,nivel,cadena$,actual)
3830   IF nodo <> P_NULO THEN 
3840     inorden ArrIzq(nodo),nivel,cadena$,actual+1
3850     IF (nivel < 1) OR (nivel = actual) THEN 
3860       IF LEN(cadena$) <> 0 THEN cadena$ = cadena$ & ","
3870       cadena$ = cadena$ & "[" & actual & "]" & ArrArbol(nodo)
3880     END IF 
3890     inorden ArrDer(nodo),nivel,cadena$,actual+1
3900   END IF 
3910 END DEFine 
3920 :
3930 REMark --------------------------------------------------------------
3940 REMark -- ARBOL_DELETE(valor) -- Borra un elemento del arbol       --
3950 REMark --------------------------------------------------------------
3960 DEFine PROCedure ARBOL_DELETE(valor)
3970   LOCal nodo,padre,repetir
3980   :
3990   nodo = A_RAIZ
4000   padre = P_NULO
4010   REPeat repetir
4020     IF nodo = P_NULO THEN EXIT repetir
4030     IF ArrArbol(nodo) = valor THEN EXIT repetir
4040     padre = nodo
4050     IF ArrArbol(nodo) < valor THEN nodo = ArrDer(nodo)
4060     IF ArrArbol(nodo) > valor THEN nodo = ArrDer(nodo)
4070   END REPeat repetir
4080   :
4090   IF (nodo = P_NULO) THEN 
4100     PRINT "ERROR: Intenta eliminar un elemento que no existe"
4110     STOP
4120   END IF 
4130   :
4140   ARBOL_BORRAR_NODO nodo,padre : REMark Borrar el nodo
4150   A_NRO = A_NRO - 1            : REMark reducir elementos del arbol
4160   A_NIVELES = ARBOL_MAX_NIVEL  : REMark Recalcula niveles
4170 END DEFine 
4180 :
4190 REMark --------------------------------------------------------------
4200 :
4210 DEFine PROCedure ARBOL_BORRAR_NODO(nodo,padre)
4220   LOCal nuevo
4230   :
4240   :: ArrArbol(nodo) = 0
4250   :
4260   REMark Este elemento sera el que reemplace en el padre
4270   nuevo = P_NULO
4280   :
4290   REMark Si no tiene hijos, se desapunta el padre
4300   IF (ArrIzq(nodo)=P_NULO)  AND (ArrDer(nodo)=P_NULO) THEN 
4310     nuevo = P_NULO
4320   END IF 
4330   :
4340   REMark Solo tiene un hijo, se pasa al padre
4350   IF (ArrIzq(nodo)=P_NULO)  AND (ArrDer(nodo)<>P_NULO) THEN 
4360     nuevo = ArrDer(nodo)
4370   END IF 
4380   IF (ArrIzq(nodo)<>P_NULO) AND (ArrDer(nodo)=P_NULO)  THEN 
4390     nuevo =  ArrIzq(nodo)
4400   END IF 
4410   :
4420   REMark Tiene dos hijos, pasa al padre el derecho y lo borro
4430   IF (ArrIzq(nodo)<>P_NULO) AND (ArrDer(nodo)<>P_NULO) THEN 
4440     nuevo = ArrDer(nodo)
4450     ARBOL_BORRAR_NODO ArrDer(nodo),nodo
4460   END IF 
4470   :
4480   REMark Ahora apunto el padre de forma adecuada
4490   IF padre = P_NULO THEN 
4500     A_RAIZ = nuevo
4510   ELSE 
4520     IF ArrIzq(padre) = nodo THEN ArrIzq(padre) = nuevo
4530     IF ArrDer(padre) = nodo THEN ArrDer(padre) = nuevo
4540   END IF 
4550   ArrIzq(nodo) = P_VACIO
4560   ArrDer(nodo) = P_VACIO
4570 END DEFine 
4580 :
4590 REMark --------------------------------------------------------------
4600 REMark -- ARBOL_CAMBIA -- Cambia el tama‰o del arbol             --
4610 REMark --------------------------------------------------------------
4620 DEFine PROCedure ARBOL_CAMBIA(tam)
4630   LOCal tEle(A_TAM),tIzq(A_TAM),tDer(A_TAM),tTam,tRaiz,tNro,m1,m2,i
4640   :
4650   REMark Guardo el arbol en el auxiliar de forma compacta
4660   tRaiz = A_RAIZ
4670   tNro  = A_NRO
4680   tTam  = A_TAM
4690   m1    = 0      : REMark Ultimo elemento libre de la lista
4700   FOR i=A_TAM TO 0 STEP -1
4710     IF (m1 = 0) AND (tEle(i) <> P_VACIO) THEN 
4720       m1 = i + 1
4730     END IF 
4740     tEle(i)=ArrArbol(i)
4750     tIzq(i)=ArrIzq(i)
4760     tDer(i)=ArrDer(i)
4770   END FOR i
4780   :
4790   REMark calculo tama‰os m“nimos
4800   m2 = A_NRO + A_FACTOR
4810   IF tam < m2       THEN tam = m2
4820   IF tam < A_FACTOR THEN tam = tam + A_FACTOR
4830   IF tam < m1       THEN tam = m1 + A_FACTOR
4840   :
4850   REMark Creo el nuevo arbol y lo relleno
4860   ARBOL_NUEVO tam,A_FACTOR
4870   :
4880   A_RAIZ = tRaiz
4890   A_NRO  = tNro
4900   FOR i=0 TO m1-1
4910     ArrArbol(i) = tEle(i)
4920     ArrIzq(i)   = tIzq(i)
4930     ArrDer(i)   = tDer(i)
4940   END FOR i
4950 END DEFine 
4960 :
4970 :
4980 REMark --------------------------------------------------------------
4990 REMark -- n = ARBOL_NIVELES -- Retorna el nro de niveles del arbol --
5000 REMark -- RETORNA: Nivel maximo del arbol                          --
5010 REMark --------------------------------------------------------------
5020 DEFine FuNction ARBOL_MAX_NIVEL
5030   RETurn nivel_inorden(A_RAIZ, 0)
5040 END DEFine 
5050 :
5060 DEFine FuNction nivel_inorden(nodo,actual)
5070   LOCal n1,n2
5080   :
5090   IF nodo = P_NULO THEN 
5100     RETurn actual
5110   ELSE 
5120     n1 = nivel_inorden(ArrIzq(nodo),actual+1)
5130     n2 = nivel_inorden(ArrDer(nodo),actual+1)
5140     IF (n1 > n2) THEN RETurn n1 : ELSE RETurn n2
5150   END IF 
5160 END DEFine
 


Para poder verificar que el árbol funciona uso un pequeño programa de pruebas, en el se ve siempre el árbol y sus enlaces izquierdo y derecho, los punteros nulos, los elementos libres, etc. Tras cada prueba se presenta el árbol y la lista de elementos ordenados que se obtiene del mismo.

100 REMark ----------------------------------------
110 REMark -- Carga                              --
120 REMark ----------------------------------------
130 MODE 4: PAPER 0 : CLS
140 INPUT "Cual prefiere (1)=Simple",t$
150 IF t$<>"1" THEN GO TO 200
160 n$="mdv1_ed_arbol_arreglo" & t$
170 PRINT "Cargando ";n$
180 MERGE n$
190 REMark ----------------------------------------
200 REMark -- Rutinas de pruebas                 --
210 REMark ----------------------------------------
220 MODE 4: PAPER 0 : CLS : LET No=0 : LET Si=1
230 p2$=""
240 t1=DATE
250 :
260 PRINT "Creacion del arbol"
270 crear : ver : PRINT
280 :
290 PRINT "PRUEBA 1: Introduce elementos en orden, inversos y aleatorios"
300 crear : FOR i=1 TO 5         : mete(i)          : END FOR i : verarbol
310 crear : FOR i=5 TO 1 STEP -1 : mete(i)          : END FOR i : verarbol
320 crear : FOR i=1 TO 10        : mete(RND(1 TO 9)): END FOR i : verarbol
330 :
340 PRINT "PRUEBA 2: Introduce 9, elimina 5, introduce 3, elimina 4"
350 crear
360 FOR i=1 TO 9   : mete(i)
370 FOR i=1 TO 5   : borra(i)
380 FOR i=10 TO 12 : mete(i)
390 FOR i=9 TO 11   : borra(i)
400 verarbol
410 :
420 PRINT "PRUEBA 3: Introduce 9, Extrae 2, introduce 10 y reduce"
430 crear
440 FOR i=1 TO 9   : mete(i)
450 FOR i=1 TO 2   : borra(i)
460 FOR i=10 TO 19 : mete(i)
470 verarbol
480 PRINT "CM "; : ARBOL_CAMBIA 0 : ver : verarbol
490 :
500 PRINT "PRUEBA 4: Buscar algunos elementos"
510 crear
520 FOR i=1 TO 9   : mete(i)
530 FOR i= 0 TO 13 STEP 3
540   PRINT "BUSCO ";i;" = ";ARBOL_BUSCAR(i)
550 END FOR i
560 PRINT
570 :
580 PRINT "PRUEBA 5: Extrae elementos hasta error por vacia"
590 FOR i=1 TO ARBOL_LEN : borra(i)
600 t2 = DATE : PRINT "Tarda ";t2-t1;" segundos"
610 borra(0)
620 STOP
630 :
640 :
650 DEFine PROCedure crear
660   ARBOL_CREAR
670 END DEFine 
680 :
690 DEFine PROCedure mete(a)
700   PRINT "EN ";a;":";
710   ARBOL_ADD(a)
720   ver
730 END DEFine 
740 :
750 DEFine PROCedure borra(a)
760   PRINT "BO ";!a;"(";ARBOL_BUSCAR(a);"):";
770   ARBOL_DELETE(a) : ver
780 END DEFine 
790 :
800 DEFine PROCedure verarbol
810   PRINT "ARBOL: ";ARBOL_VER$(0) : PRINT
820 END DEFine 
830 :
840 DEFine PROCedure ver
850   LOCal xx
860   :
870   PRINT "[";ARBOL_LEN;"x";ARBOL_NIVELES;"]";
880   IF A_RAIZ=P_NULO THEN PRINT "*"; : ELSE PRINT A_RAIZ;":";
890   FOR xx=0 TO A_TAM
900     PRINT !"(";xx;")";ArrArbol(xx);
910     IF ArrIzq(xx)=-1 THEN PRINT "*";
920     IF ArrIzq(xx)=-2 THEN PRINT "v";
930     IF ArrIzq(xx)>0  THEN PRINT ArrIzq(xx);
940     IF ArrDer(xx)=-1 THEN PRINT "*";
950     IF ArrDer(xx)=-2 THEN PRINT "v";
960     IF ArrDer(xx)>0  THEN PRINT ArrDer(xx);
970   END FOR xx
980   PRINT
990 END DEFine 

Cuando ejecutéis las pruebas os daréis cuenta de que si introduzco los elementos de forma ordenada todos van a parar siempre a la rama derecha, quedando la izquierda vacía, por lo que tenemos una lista en lugar de un árbol. Cuando los introduzco de forma aleatoria se van llenando las ramas izquierda y derecha mas o menos a la par. Esto nos indica que un árbol binario de búsqueda solo será eficiente si los elemento se introducen al azar y producen un árbol en el que las ramas sean todas mas o menos del mismo tamaño, pues sin ese equilibrio pierde mucha efectividad en altas y bajas, peor lo que es peor, hace mas lentas las búsquedas, siendo nuestro objetivo que estas sean lo mas eficientes posibles. En la siguiente entrada montaremos arboles binarios de búsqueda equilibrados mediante las técnicas de rotación simple y doble, produciendo árboles AVR.

Como siempre aquí todo lo desarrollado sobre estructuras de datos hasta el momento, la parte de ordenación no ha variado.

lunes, 12 de diciembre de 2016

Variante del cable RGB de la SNES

Ha surgido una variante del cable RGB para las SNES, que no se si servirá para las Nintendo-64 con salida RGB o no. En esta entrada expliqué los cables de video existentes para las variedades de maquinas de nintendo con el mismo conector de salida, SNES/SNES 2/AV Famicom/N64/Game Cube, en ella explicaba que los cables deben no usar condensador para las SNES y si para las N64 y Cube, aunque esto hay que probarlo siempre ya que depende de la maquina y el televisor mas que de otra cosa.

Ahora ha surgido una variante del cable RGB para la SNES. Sabemos que la salida del euroconector o scart necesita cuatro señales para el manejo de vídeo, rojo, verde, azul y el sincronismo compuesto. Esta última señal se saca de la señal de vídeo compuesto habitualmente, pero se ha descubierto que es mejor obtener de la señal de luminancia, que también los incluye, y por las pruebas que he visto da un resultado mucho mejor (aunque no lo he podido probar todavía, pero las imágenes que se ven por Internet del cable que se ha denomiado Chekerboar dejan claro que la señal es mucho mejor. El cambio es muy sencillo, solo hay que sacar la señal  que va al pin 20 del SCART a través del pin 7 de la Nintendo, en lugar de a través del pin 5. Hay que mantener la resistencia entre el pin 7 y masa, que yo en mi imagen pongo entre los pines 18 y 20 del euroconector, pero que normalmente en los cables está en el conector de Nintendo.


No tengo constancia de si esta modificación serviría igualmente para las N64 (las que llevan soporte RGB que no son todas) y las Game Cube.

viernes, 9 de diciembre de 2016

Mas traducciones en la Wikipedia

He realizado algunas traducciones mas para la wikipedia, ya que considero que es un buen lugar para almacenar información que sea útil a todo el mundo, además siempre aprendo cosas nuevas.

  • Micromation fue una empresa americana de micro ordenadores, que fabricaba ordenadores multi usurio a base de montar un aplaca con un procesador para cada uno. Que yo sepa no llegaron a España, eran caros pero de lo mejor del momento.
  • Como me gusta mucho DEC y sus PDP (aunque no he tenido la suerte de usar nunca uno), he traducido la página sobre los DECmate, los microordenadores compatibles con los PDP-8.
  • Relacionado con lo anterior, el microprocesador Intersil 6100 era el corazón de los DECmate, una CPU de un PDP-8 en un solo chip, aunque mucho mas lento.
  • Relacionado con los PDP, las páginas para 12 bits y para 18 bits no estaban en español. También he añadido una plantilla para que enlace con todos los anchos de bits y la he ubicado en todas las páginas relacionadas.
Seguiré con otras traducciones que faltan muchas cosas de empresas y ordenadores antiguos que tanto me gustan.

miércoles, 7 de diciembre de 2016

Programación del Sinclair QL (XVIII): Ordenación por inserción usando una lista enlazada



Como ya tenemos las rutinas de manejo de las listas enlazadas con sus elementos ordenados, la voy a usar como algoritmo de ordenación general, simplemente tomo los algoritmos de lista enlazada y los simplifico al máximo, creo la lista con tamaño exacto para los elementos a ordenar, la relleno, y luego la recorro modificando el arreglo original, y al final resultando un algoritmo muy sencillo, aunque para ordenar una lista necesita otras dos adicionales, por lo que gasta bastante más memoria.

ALGORITMO Insercion_lista (arreglo, primero, ultimo)
 
  raiz ← null  
  tamaño ← ultimo - primero + 1
  CREAR_ARREGLO Datos(tamaño)
  CREAR_ARREGLO Enlaces(tamaño)

  BUCLE i DESDE primero HASTA ultimo
    LISTA_ORDENADA_INSERTAR(arreglo(i), Datos, Enlaces, raiz)
  FIN BUCLE
    
  pos ← raiz
  BUCLE i DESDE primero HASTA ultimo
    arreglo(nro) ← Datos(pos)
    pos ← Enlaces(pos)
  FIN BUCLE

ALGORITMO LISTA_ORDENADA_INSERTAR (valor, ListaDatos, ListaNodos, NodoRaiz)
 
   // Busco un nodo libre
   nro ← BUSCAR_ELEMENTO_LIBRE
   SI nro = NULL ENTONCES
      ERROR No hay espacio libre
      SALIR DEL ALGORITMO
   FIN SI

   // Ubico el elemento
   ListaDatos(nro) = Valor

   // Si es el primer nodo lo ubico en la raiz
   SI (NodoRaiz ES NULO) ENTONCES 
     ListaNodos(nro) ← NULL
     NodoRaiz ← nro
   FIN SI
 
   // Si no es el primero buscamos su posición
   SI (NodoRaiz NOES NULO) ENTONCES  
     pos ← NodoRaiz  // Nodo por el que vamos
     ant ← NULL      // Nodo anterior al que vamos
     REPETIR
       encontrado ← Falso 
       
       // Si he encontrado un elemento mayor o igual, debo ubicarlo antes
       SI (ListaDatos(pos) ≥ Valor) ENTONCES 
         // Si es el primer elemento, hay que ubicarlo en la raiz
         SI (ant ES NULO) ENTONCES 
           ListaNodos(nro) ← NodoRaiz
           NodoRaiz        ← nro
           encontrado      ← Cierto 
         FIN SI
  
         // Si no es el primer elemento, hay que ubicarlo tras el anterior
         SI (ant NOES NULO) ENTONCES 
           ListaNodos(nro) ← ListaNodos(ant)
           ListaNodos(ant) ← nro
           encontrado      ← Cierto 
         FIN SI
       FIN SI
       
       // Si se ha llegado al final se pone el último
       SI (ListaNodos(pos) ES NULO) ENTONCES 
         ListaNodos(pos) ← nro
         ListaNodos(nro) ← NULL
         encontrado      ← Cierto
      END IF 
      
      //No encontrado seguimos iterando
      SI (NO encontrado) ENTONCES 
        ant ← pos
        pos ← ListaNodos(pos)
      FIN SI
     HASTA QUE (encontrado)
   FIN SI 


Aquí el programa completo en SuperBASIC correspondiente, son las rutinas desarrolladas en el manejo de listas pero simplificadas al máximo dejando solo lo necesario. Para gastar un poco menos de memoria y optimizar algo las velocidades (aunque en SuperBASIC la velocidad no se nota por su forma de trabajar), habría que hacer que la lista de punteros sea de enteros en lugar de reales. De momento no lo voy a hacer así.

20000 REMark ---------------------------------------------
20010 REMark -- ALGORITMOS DE ORDENACION                --
20020 REMark --   Modulo....: Insercion con lista       --
20030 REMark --   Objetivo..: Ordena un arreglo usando  --
20040 REMark --               enlazada                  --
20050 REMark --   Autor.....: javu61, 12/2016           --
20060 REMark --   Parametros:                           --
20070 REMark --     arreglo -- Arreglo a ordenar        --
20080 REMark --     sentido -- FALSO = Ascendente       --
20090 REMark --     primero -- primer elemento          --
20100 REMark --     ultimo  -- ultimo elemento          --
20110 REMark --                Si ultimo=0 -- Todos     --
20120 REMark ---------------------------------------------
20130 DEFine PROCedure Insercion_Lista (arreglo,sentido,primero,ultimo)
20140   LOCal pos,nro
20150   :
20160   IF ultimo = 0 THEN ultimo=DIMN(arreglo)
20170   :
20180   REMark Crear los elementos de la lista
20190   LET L_NULO   = -1        : REMark Puntero nulo
20200   LET L_RAIZ   = L_NULO    : REMark Puntero al nodo raiz
20210   DIM ArrPuntero(ultimo-primero) : REMark Puntero siguiente elemento
20220   DIM ArrLista(ultimo-primero)   : REMark Elementos de la lista
20230   :
20240   REMark Rellenar la lista
20250   FOR pos = primero TO ultimo : LISTA_ADD pos,arreglo(pos),sentido
20260   :
20270   REMark A partir de la lista montar el arreglo ordenado
20290   FOR nro=primero TO ultimo
20300     MUEVE ArrLista(L_RAIZ), arreglo(nro)
20310     L_RAIZ= ArrPuntero(L_RAIZ)
20320   END FOR nro
20330 END DEFine 
20340 :
20350 REMark -------------------------------------------------------------
20360 REMark -- LISTA_ADD(dato) -- Introduce un dato en la lista        --
20370 REMark -------------------------------------------------------------
20380 DEFine PROCedure LISTA_ADD(nro,dato,sentido)
20390   LOCal repetir,pos,ant
20400   :
20410   REMark Ubico el elemento
20420   ArrLista(nro) = dato
20430   :
20440   REMark Si es el primer nodo, lo ubico en la raiz
20450   IF L_RAIZ = L_NULO THEN 
20460     ArrPuntero(nro) = L_NULO
20470     L_RAIZ = nro
20480   ELSE 
20490     REMark Si no es el primero, buscamos su posición recorriendo
20500     pos = L_RAIZ
20510     ant = L_NULO
20520     REPeat repetir
20530       REMark Si he econtrado su posición
20540       IF COMPARA(ArrLista(pos), dato, sentido) &gt;= 0 THEN 
20550         REMark Segun sea ahora el primer elemento o no
20560         IF ant = L_NULO THEN 
20570           ArrPuntero(nro) = L_RAIZ
20580           L_RAIZ = nro
20590         ELSE 
20600           ArrPuntero(nro) = ArrPuntero(ant)
20610           ArrPuntero(ant) = nro
20620         END IF 
20630         EXIT repetir
20640       END IF 
20650       REMark Si he llegado al final, lo añado como utimo elemento
20660       IF ArrPuntero(pos)=L_NULO THEN 
20670         ArrPuntero(pos) = nro
20680         ArrPuntero(nro) = L_NULO
20690         EXIT repetir
20700       END IF 
20710       ant = pos
20720       pos = ArrPuntero(pos)
20730     END REPeat repetir
20740   END IF 
20750 END DEFine 
20760 :
20770 :


Las pruebas de las rutinas de ordenación por inserción desarrolladas hasta el momento dan el siguiente resultado con 50 elementos, vemos que Shell es el mas rápido en el caso medio y es bastante bueno para listas ordenadas o en orden inverso, además no requiere mucha memoria. La inserción pura y la inserción con lista enlazada tardan mas o menos lo mismo en el caso medio, ya que son muy similares en cuanto a la cantidad de elementos a recorrer para insertar uno en su lugar, pero por su forma de trabajar la inserción pura es la mas rápida para listas ordenadas mientras la de lista enlazada es la peor, y para listas en orden inverso se cambian las tornas.



He dividido los programas en dos grupos, aquí todo lo desarrollado sobre estructuras de datos y sus pruebas hasta el momento, y aquí todo lo desarrollado sobre ordenación hasta el momento.