Ejemplo de incersion

Árbol AVL

Árbol AVL

El árbol AVL toma su nombre de las iniciales de los apellidos de sus inventores, Georgii Adelson-Velskii y Yevgeniy Landis. Lo dieron a conocer en la publicación de un artículo en 1962, «An algorithm for the organization of information» («Un algoritmo para la organización de la información»).

Los árboles AVL están siempre equilibrados de tal modo que para todos los nodos, la altura de la rama izquierda no difiere en más de una unidad de la altura de la rama derecha o viceversa. Gracias a esta forma de equilibrio (o balanceo), la complejidad de una búsqueda en uno de estos árboles se mantiene siempre en orden de complejidad O(log n). El factor de equilibrio puede ser almacenado directamente en cada nodo o ser computado a partir de las alturas de los subárboles.

Para conseguir esta propiedad de equilibrio, la inserción y el borrado de los nodos se ha de realizar de una forma especial. Si al realizar una operación de inserción o borrado se rompe la condición de equilibrio, hay que realizar una serie de rotaciones de los nodos.

Los árboles AVL más profundos son los árboles de Fibonacci.

Definición de la altura de un árbol

Sea  un árbol binario de búsqueda y sean  y  sus subárboles, su altura , es:

•  si el árbol  contiene solo la raíz
•  si contiene más nodos

Las operaciones básicas de un árbol AVL implican generalmente el realizar los mismos algoritmos que serían realizados en un árbol binario de búsqueda desequilibrado, pero precedido o seguido por una o más de las llamadas "rotaciones AVL".

Rotación simple a la derecha‎

De un árbol de raíz (r) y de hijos izquierdo (i) y derecho (d), lo que haremos será formar un nuevo árbol cuya raíz sea la raíz del hijo izquierdo, como hijo izquierdo colocamos el hijo izquierdo de i (nuestro i’) y como hijo derecho construimos un nuevo árbol que tendrá como raíz, la raíz del árbol (r), el hijo derecho de i (d’) será el hijo izquierdo y el hijo derecho será el hijo derecho del árbol (d).

Rotación a la izquierda

De un árbol de raíz (r) y de hijos izquierdo (i) y derecho (d), consiste en formar un nuevo árbol cuya raíz sea la raíz del hijo derecho, como hijo derecho colocamos el hijo derecho de d (nuestro d’) y como hijo izquierdo construimos un nuevo árbol que tendrá como raíz la raíz del árbol (r), el hijo izquierdo de d será el hijo derecho (i’) y el hijo izquierdo será el hijo izquierdo del árbol (i).

Precondición : Tiene que tener hijo derecho no vacío.

Rotación doble a la derecha

La Rotación doble a la Derecha son dos rotaciones simples, primero rotación simple izquierda y luego rotación simple derecha.

Rotación doble a la izquierda

La Rotación doble a la Izquierda son dos rotaciones simples, primero rotación simple derecha y luego rotación simple izquierda.

Inserción

La inserción en un árbol de AVL puede ser realizada insertando el valor dado en el árbol como si fuera un árbol de búsqueda binario desequilibrado y después retrocediendo hacia la raíz, rotando sobre cualquier nodo que pueda haberse desequilibrado durante la inserción.

Proceso de inserción:

1.buscar hasta encontrar la posición de inserción o modificación (proceso idéntico a inserción en árbol binario de búsqueda)

2.insertar el nuevo nodo con factor de equilibrio “equilibrado”

3.desandar el camino de búsqueda, verificando el equilibrio de los nodos, y re-equilibrando si es necesario

Árbol binario de búsqueda auto-balanceable

Árbol binario de búsqueda auto-balanceable

En ciencias de la computación, un árbol binario de búsqueda auto-balanceable o equilibrado es un árbol binario de búsqueda que intenta mantener su altura, o el número de niveles de nodos bajo la raíz, tan pequeños como sea posible en todo momento, automáticamente. Esto es importante, ya que muchas operaciones en un árbol de búsqueda binaria tardan un tiempo proporcional a la altura del árbol, y los árboles binarios de búsqueda ordinarios pueden tomar alturas muy grandes en situaciones normales, como cuando las claves son insertadas en orden. Mantener baja la altura se consigue habitualmente realizando transformaciones en el árbol, como la rotación de árboles, en momentos clave.

Tiempos para varias operaciones en términos del número de nodos en el árbol n:

Operación	Tiempo en cota superior asintótica
Búsqueda	O(log n)
Inserción	O(log n)
Eliminación	O(log n)
Iteración en orden	O(n)

Para algunas implementaciones estos tiempos son el peor caso, mientras que para otras están amortizados.

Estructuras de datos populares que implementan este tipo de árbol:

• Árbol AVL

Árbol binario

Árbol binario

En ciencias de la computación, un árbol binario es una estructura de datos en la cual cada nodo siempre tiene un hijo izquierdo y un hijo derecho. No pueden tener más de dos hijos (de ahí el nombre "binario"). Si algún hijo tiene como referencia a null, es decir que no almacena ningún dato, entonces este es llamado un nodo externo. En el caso contrario el hijo es llamado un nodo interno. Usos comunes de los árboles binarios son los árboles binarios de búsqueda, los montículos binarios y Codificación de Huffman.

Árbol (informática)

Árbol (informática)

En ciencias de la informática, un árbol es una estructura de datos amplia mente usada que imita la forma de un árbol (un conjunto de nodos conectados). Un nodo es la unidad sobre la que se construye el árbol y puede tener cero o más nodos hijos conectados a él. Se dice que un nodo  es padre de un nodo  si existe un enlace desde  hasta  (en ese caso, también decimos que  es hijo de ). Sólo puede haber un único nodo sin padres, que llamaremos raíz. Un nodo que no tiene hijos se conoce como hoja. Los demás nodos (tienen padre y uno o varios hijos) se les conoce como rama.

Recursividad

Recursividad 

Un algoritmo recursivo es un algoritmo que expresa la solución de un problema en términos de una llamada a sí mismo. La llamada a sí mismo se conoce como llamada recursiva o recurrente.

Generalmente, si la primera llamada al subprograma se plantea sobre un problema de tamaño u orden N, cada nueva ejecución recurrente del mismo se planteará sobre problemas, de igual naturaleza que el original, pero de un tamaño menor que N. De esta forma, al ir reduciendo progresivamente la complejidad del problema que resolver, llegará un momento en que su resolución sea más o menos trivial (o, al menos, suficientemente manejable como para resolverlo de forma no recursiva). En esa situación diremos que estamos ante un caso base de la recursividad.

Las claves para construir un subprograma recurrente son:

• Cada llamada recurrente se debería definir sobre un problema de menor complejidad (algo más fácil de resolver).
• Ha de existir al menos un caso base para evitar que la recurrencia sea infinita.

Es frecuente que los algoritmos recurrentes sean más ineficientes en tiempo que los iterativos aunque suelen ser mucho más breves en espacio.

- Definición : Propiedad de las funciones (Métodos) de auto llamarse, son una alternativa a los procesos iterativos.

- Utilidad : Cuando los procesos iterativos son muy complejos.

- Aplicación : Recorrido de estructuras no lineales, solución de ecuaciones matemáticas complejas.

- Implementacion : 

FUNCIÓN Factorial(n)
    VAR resultado: Entero
 
    SI (n<2) ENTONCES
        resultado = 1;
    SINO
        resultado = n * Factorial(n-1);
    FSI
 
    RETORNA resultado;
FFUNCIÓN

Cola Circular BICOLA

Bicola

La bicola o doble cola es un tipo de cola especial que permiten la inserción y eliminación de elementos de ambos extremos de la cola.

Puede representarse a partir de un vector y dos índices, siendo su representación más frecuente una lista circular doblemente enlazada.

Cola Circular

Cola Circular

Una cola circular o anillo es una estructura de datos en la que los elementos están de forma circular y cada elemento tiene un sucesor y un predecesor. Los elementos pueden consultarse  añadirse y eliminarse únicamente desde la cabeza del anillo que es una posición distinguida. Existen dos operaciones de rotaciones, una en cada sentido, de manera que la cabeza del anillo pasa a ser el elemento sucesor, o el predecesor, respectivamente, de la cabeza actual.

Invertir Extremos Pila

ColaLista

Cola Nodo

Cola Nodo

Cola vector

Cola Vector

Cola

Colas en JAVA

public void inserta(Elemento x) {
        Nodo Nuevo;
        Nuevo = new Nodo(x, null);
        if (NodoCabeza == null) {
            NodoCabeza = Nuevo;
        } else {
            NodoFinal.Siguiente = Nuevo;
        }
        NodoFinal = Nuevo;
    }
 
    public Elemento cabeza() throws IllegalArgumentException {
        if (NodoCabeza == null) {
            throw new IllegalArgumentException();
        } else {
            return NodoCabeza.Info;
        }
    }
 
    public Cola() {
    // Devuelve una Cola vacía
        NodoCabeza = null;
        NodoFinal = null;
    }

Cola

Cola

Una cola (también llamada fila) es una estructura de datos, caracterizada por ser una secuencia de elementos en la que la operación de inserción push se realiza por un extremo y la operación de extracción pop por el otro. También se le llama estructura FIFO (del inglés First In First Out), debido a que el primer elemento en entrar será también el primero en salir.

Las colas se utilizan en sistemas informáticos, transportes y operaciones de investigación (entre otros), dónde los objetos, personas o eventos son tomados como datos que se almacenan y se guardan mediante colas para su posterior procesamiento. Este tipo de estructura de datos abstracta se implementa en lenguajes orientados a objetos mediante clases, en forma de listas enlazadas.

Pila

Implementación en java <Pila>

public class Nodo<tipo> {
        public tipo dato;
        private Nodo<tipo> siguiente;
 
        public Nodo(tipo Dato) {
                dato = Dato;
                siguiente = null;
        }
 
        public void conectar(Nodo<tipo> elSiguiente) {
                siguiente = elSiguiente;
        }
 
        public Nodo<tipo> getSiguiente() {
                return siguiente;
        }
}
public class Pila<tipo> {
        Nodo<tipo> cima;
 
        public Pila() {
                cima = null;
        }
 
        public int tamano() {
                Nodo<tipo> lectorAuxiliar = cima;
                int contadorDeDatos = 0;
                while (lectorAuxiliar != null) {
                        contadorDeDatos++;
                        lectorAuxiliar = lectorAuxiliar.getSiguiente();
                }
                return contadorDeDatos;
        }
 
        public void apilar(tipo datoNuevo) {
                Nodo<tipo> nuevo = new Nodo<tipo>(datoNuevo);
                nuevo.conectar(cima);
                cima = nuevo;
        }
 
        public tipo desapilar() {
                tipo dato = cima.dato;
                cima = cima.getSiguiente();
                return dato;
        }
 
        public tipo getCima() {
                return cima.dato;
        }
 
        public boolean estaVacia() {
                return cima == null;
        }
 
        public String toString() {
                Nodo<tipo> lectorAuxiliar = cima;
                String respuesta = "IN/OUT <->";
                while (lectorAuxiliar != null) {
                        respuesta += " [" + lectorAuxiliar.dato.toString() + "] ";
                        lectorAuxiliar = lectorAuxiliar.getSiguiente();
                }
                return respuesta;
        }
}

Pila

Pila

Una pila (stack en inglés) es una lista ordenada o estructura de datos en la que el modo de acceso a sus elementos es de tipo LIFO (del inglés Last In First Out, último en entrar, primero en salir) que permite almacenar y recuperar datos. Esta estructura se aplica en multitud de ocasiones en el área de informática debido a su simplicidad y ordenación implícita de la propia estructura.

Para el manejo de los datos se cuenta con dos operaciones básicas: apilar (push), que coloca un objeto en la pila, y su operación inversa,retirar (o desapilar, pop), que retira el último elemento apilado.

En cada momento sólo se tiene acceso a la parte superior de la pila, es decir, al último objeto apilado (denominado TOS, Top of Stack en inglés). La operación retirar permite la obtención de este elemento, que es retirado de la pila permitiendo el acceso al siguiente (apilado con anterioridad), que pasa a ser el nuevo TOS.

Por analogía con objetos cotidianos, una operación apilar equivaldría a colocar un plato sobre una pila de platos, y una operación retirar a retirarlo.

Las pilas suelen emplearse en los siguientes contextos:

• Evaluación de expresiones en notación postfija (notación polaca inversa).
• Reconocedores sintácticos de lenguajes independientes del contexto
• Implementación de recursividad.

Listas

listas

En Ciencias de la Computación, una lista enlazada es una de las estructuras de datos fundamentales, y puede ser usada para implementar otras estructuras de datos. Consiste en una secuencia de nodos, en los que se guardan campos de datos arbitrarios y una o dos referencias, enlaces o punteros al nodo anterior o posterior. El principal beneficio de las listas enlazadas respecto a los vectores convencionales es que el orden de los elementos enlazados puede ser diferente al orden de almacenamiento en la memoria o el disco, permitiendo que el orden de recorrido de la lista sea diferente al de almacenamiento.

Una lista enlazada es un tipo de dato autorreferenciado porque contienen un puntero o enlace (en inglés link, del mismo significado) a otro dato del mismo tipo. Las listas enlazadas permiten inserciones y eliminación de nodos en cualquier punto de la lista en tiempo constante (suponiendo que dicho punto está previamente identificado o localizado), pero no permiten un acceso aleatorio. Existen diferentes tipos de listas enlazadas: listas enlazadas simples, listas doblemente enlazadas, listas enlazadas circulares y listas enlazadas doblemente circulares.

Las listas enlazadas pueden ser implementadas en muchos lenguajes. Lenguajes tales como Lisp y Scheme tiene estructuras de datos ya construidas, junto con operaciones para acceder a las listas enlazadas. Lenguajes imperativos u orientados a objetos tales como C o C++ y Java, respectivamente, disponen de referencias para crear listas enlazadas.

Listas simples enlazadas

La lista enlazada básica es la lista enlazada simple la cual tiene un enlace por nodo. Este enlace apunta al siguiente nodo (o indica que tiene la dirección en memoria del siguiente nodo) en la lista, o al valor NULL o a la lista vacía, si es el último nodo.

Listas doblemente enlazadas

Un tipo de lista enlazada más sofisticado es la lista doblemente enlazada o lista enlazadas de dos vías. Cada nodo tiene dos enlaces: uno apunta al nodo anterior, o apunta al valor NULL si es el primer nodo; y otro que apunta al nodo siguiente, o apunta al valor NULL si es el último nodo.

En algún lenguaje de muy bajo nivel, XOR-Linking ofrece una vía para implementar listas doblemente enlazadas, usando una sola palabra para ambos enlaces, aunque esta técnica no se suele utilizar.

Listas enlazadas circulares

En una lista enlazada circular, el primer y el último nodo están unidos juntos. Esto se puede hacer tanto para listas enlazadas simples como para las doblemente enlazadas. Para recorrer una lista enlazada circular podemos empezar por cualquier nodo y seguir la lista en cualquier dirección hasta que se regrese hasta el nodo original. Desde otro punto de vista, las listas enlazadas circulares pueden ser vistas como listas sin comienzo ni fin. Este tipo de listas es el más usado para dirigir buffers para “ingerir” datos, y para visitar todos los nodos de una lista a partir de uno dado.

Una lista enlazada circular que contiene tres valores enteros

Listas enlazadas circulares simples

Cada nodo tiene un enlace, similar al de las listas enlazadas simples, excepto que el siguiente nodo del último apunta al primero. Como en una lista enlazada simple, los nuevos nodos pueden ser solo eficientemente insertados después de uno que ya tengamos referenciado. Por esta razón, es usual quedarse con una referencia solamente al último elemento en una lista enlazada circular simple, esto nos permite rápidas inserciones al principio, y también permite accesos al primer nodo desde el puntero del último nodo. ¹

Listas enlazadas doblemente circulares

En una lista enlazada doblemente circular, cada nodo tiene dos enlaces, similares a los de la lista doblemente enlazada, excepto que el enlace anterior del primer nodo apunta al último y el enlace siguiente del último nodo, apunta al primero. Como en una lista doblemente enlazada, las inserciones y eliminaciones pueden ser hechas desde cualquier punto con acceso a algún nodo cercano. Aunque estructuralmente una lista circular doblemente enlazada no tiene ni principio ni fin, un puntero de acceso externo puede establecer el nodo apuntado que está en la cabeza o al nodo cola, y así mantener el orden tan bien como en una lista doblemente enlazada.

Incertar antes de - Nodo Simple - Nodo Doble

Premisa
"x = dato."
 "y = dato"

Incertar antes de - Nodo Simple

if(p!=null){
      if(s!=null){
            s.setsig(new Nodo (y, r));
      }else{
            p=new Nodo (y,p);
      }
}else{
      s.o.p("Lista vacia");
}

Incertar antes de - Nodo Simple

if(r!=null){
      r.getant.setsig( new NodoDoble (y.rgetant,r));
      r.setant(r.getant().getsig());
}

Incertar al final - Nodo Simple - Nodo Doble

Premisa
"x = dato."

Incertar al final - Nodo Simple

if(q!=null){
      q.setsig(new Nodo(x,null));
      q=q.getsig();
      }else{
            p=q= new Nodo (x,null);
      }

 Incertar al final - Nodo Doble


if(q!=null){
      q.setsig(new NodoDoble (x,q,null));
      q=q.getsig();
      }else{
            p=q= new NodoDoble (x,null);
      }

Insertar al inicio - Nodo Simple -Nodo Doble

Premisa
"x = dato."

Insertar al inicio - Nodo Simple

p = new Nodo (x,p);

Sirve para p = null.



Insertar al inicio - Nodo Doble

if(p != null){
      p.setant(new NodoDoble(x,null,p));
      p = p.getant();
      }else{
            p = new NodoDoble(x,null,p);
      }

Operaciones entre Nodos - Listas Enlasadas

Operaciones entre Nodos - Listas Enlazadas

En las listas enlazadas se pueden realizar siertos tipos de operaciones las cuales son:

1) Insertar - al inicio
                 - al final
                 - antes de
                 - después de

2) Buscar  - consultar
                 - modificar
                 - eliminar

3) Ordenar


Mas adelante veremos como se convierten estas operaciones en codigo y como se aplican.

Nodos

Nodo

En términos generales, un nodo es un espacio real o abstracto en el que confluyen parte de las conexiones de otros espacios reales o abstractos que comparten sus mismas características y que a su vez también son nodos. Todos se interrelacionan de una manera no jerárquica y conforman lo que en términos sociológicos o matemáticos se llama red. El concepto de red puede definirse como "conjunto de nodos interconectados.

En programación, concretamente en estructuras de datos, un nodo es uno de los elementos de una lista enlazada, de un árbol o de un grafo. Cada nodo será una estructura o registro que dispondrá de varios campos, y al menos uno de esos campos será un puntero o referencia a otro nodo, de forma que, conocido un nodo, a partir de esa referencia, será posible en teoría tener acceso a otros nodos de la estructura. Los nodos son herramientas esenciales para la construcción de estructuras de datos dinámicas.

Ya que el nodo es una clase que crea el programador esta puede ser modificada segun las nesesidades que tenga, estos son algunos de los tipos de nodos que se pueden presentar:

 

Nodo Simple

Este nodo esta compuesto por dos partes, una parte que es dato y una parte en la cual se encuentra la direccion del siguiente.

Nodo Doble

Este nodo esta compuesto por tres partes, una parte que es dato y dos partes de direccion las cuales guardan la direccion del nodo anterior y la del nodo siguiente.

Nodo Multiple

Este nodo esta formado por diversas partes las cuales son definidas por el programador y pueden ser de datos o de direccion, las cuales son definidas por el programador al momento de crearlos.

Tecnicas de Programacion

código spaghetti

El código spaghetti es un término peyorativo para los programas de computación que tienen una estructura de control de flujo compleja e incomprensible. Su nombre deriva del hecho que este tipo de código parece asemejarse a un plato de espaguetis, es decir, un montón de hilos intrincados y anudados.

Tradicionalmente suele asociarse este estilo de programación con lenguajes básicos y antiguos, donde el flujo se controlaba mediante sentencias de control muy primitivas como goto y utilizando números de línea. Un ejemplo de lenguaje que invitaba al uso de código spaghetti es el QBasic de Microsoft en sus primeras versiones.

Programación estructurada

La programación estructurada es un paradigma de programación orientado a mejorar la claridad, calidad y tiempo de desarrollo de un programa de computadora, utilizando únicamente subrutinas y tres estructuras: secuencia, selección (if y switch) e iteración (bucles for y while), considerando innecesario y contraproducente el uso de la instrucción de transferencia incondicional (GOTO), que podría conducir a "código espagueti", que es mucho más difícil de seguir y de mantener, y era la causa de muchos errores de programación.

Programación modular

Diagrama del funcionamiento de un subprograma.

La programación modular es un paradigma de programación que consiste en dividir un programa en módulos o subprogramas con el fin de hacerlo más legible y manejable.

Se presenta históricamente como una evolución de la programación estructurada para solucionar problemas de programación más grandes y complejos de lo que ésta puede resolver.

Al aplicar la programación modular, un problema complejo debe ser dividido en varios subproblemas más simples, y estos a su vez en otros subproblemas más simples. Esto debe hacerse hasta obtener subproblemas lo suficientemente simples como para poder ser resueltos fácilmente con algún lenguaje de programación. Ésta técnica se llama refinamiento sucesivo, divide y vencerás ó análisis descendente (Top-Down).

Programación orientada a objetos

La programación orientada a objetos o POO (OOP según sus siglas en inglés) es un paradigma de programación que usa los objetos en sus interacciones, para diseñar aplicaciones y programas informáticos. Está basado en varias técnicas, incluyendo herencia, cohesión, abstracción, polimorfismo, acoplamiento y encapsulamiento. Su uso se popularizó a principios de la década de los años 1990. En la actualidad, existe una gran variedad de lenguajes de programación que soportan la orientación a objetos.

Estructura de datos y analisis de algoritmos

En programación, una estructura de datos es una forma de organizar un conjunto de datos elementales con el objetivo de facilitar su manipulación. Un dato elemental es la mínima información que se tiene en un sistema.

Una estructura de datos define la organización e interrelación de estos y un conjunto de operaciones que se pueden realizar sobre ellos. Las operaciones básicas son:

• Alta, adicionar un nuevo valor a la estructura.

• Baja, borrar un valor de la estructura.

• Búsqueda, encontrar un determinado valor en la estructura para realizar una operación con este valor, en forma secuencial o binario (siempre y cuando los datos estén ordenados).

Otras operaciones que se pueden realizar son:

• Ordenamiento, de los elementos pertenecientes a la estructura.
• Apareo, dadas dos estructuras originar una nueva ordenada y que contenga a las apareadas.

Cada estructura ofrece ventajas y desventajas en relación a la simplicidad y eficiencia para la realización de cada operación. De esta forma, la elección de la estructura de datos apropiada para cada problema depende de factores como la frecuencia y el orden en que se realiza cada operación sobre los datos.

Estructura de datos y analisis de algoritmos

"La mayoría de los programadores profesionales que me he encontrado, no están bien preparados para atacar problemas de diseño de algoritmos. Esto es una lástima, ya que las técnicas de diseño de algoritmos son una de las tecnologías prácticas medulares de ciencias de la computación."

                                                                Steven S. Skiena, The Algorithm Design Manual, 1997 (Prefacio)