listas dobles

Download LISTAS DOBLES

Post on 11-Jan-2016

9 views

Category:

Documents

0 download

Embed Size (px)

DESCRIPTION

Estructura de datos Listas Dobles

TRANSCRIPT

  • 5.1. Concepto de rbol.

    Los rboles representan las estructuras no-lineales y dinmicas de datos ms importantes en computacin. Dinmicas, puesto que la estructura rbol puede cambiar durante la ejecucin de un programa. No lineales, puesto que a cada elemento del rbol pueden seguirle varios elementos.

    Un rbol es una estructura jerrquica aplicada sobre una coleccin de elementos u objetos llamados nodos; uno de los cuales es conocido como raz. Adems se crea una relacin o parentesco entre los nodos dando lugar a trminos como padre, hijo, hermano, antecesor, sucesor, ancestro, etc.

    Formalmente se define un rbol de tipo T como una estructura homognea que es la concatenacin de un elemento de tipo T junto con un nmero finito de rboles disjuntos, llamados subrboles. Una forma particular de rbol puede ser la estructura vaca.

    Se utiliza la recursin para definir un rbol porque representa la forma ms apropiada y porque adems es una caracterstica inherente a los mismos.

    Los rboles tienen una gran variedad de aplicaciones. Por ejemplo, se pueden utilizar para representar frmulas matemticas, APRA organizar adecuadamente la informacin, para registrar la historia de un campeonato de tenis, para construir un rbol genealgico, para el anlisis de circuitos elctricos y para numerar los captulos y secciones de un libro.

    Caractersticas y propiedades de los rboles

    Las siguientes son caractersticas y propiedades ms importantes de los rboles en general:

    1. Todo rbol que no es vaco, tiene un nico nodo raz. 2. Un nodo X es descendiente directo de un nodo Y, si el nodo X es apuntado por el nodo Y.

    En este caso es comn utilizar la expresin X es hijo de Y. 3. Un nodo X es antecesor directo de un nodo Y, si el nodo X apunta al nodo Y. En este caso

    es comn utilizar la expresin X es padre de Y. 4. Se dice que todos los nodos que son descendientes directos (hijos) de un mismo nodo

    (padre), son hermanos. 5. Todo nodo que no tiene ramificaciones (hijos), se conoce con el nombre

    de terminal u hoja. 6. Todo nodo que no es raz, ni terminal u hoja se conoce con el nombre de interior. 7. Grado es el nmero de descendientes directos de un determinado nodo. Grado del

    rbol es el mximo grado de todos los nodos del rbol. 8. Nivel es el nmero de arcos que deben ser recorridos para llegar a un determinado nodo.

    Por definicin la raz tiene nivel 1. 9. Altura del rbol es el mximo nmero de niveles de todos los nodos del rbol.

    A continuacin se presenta un ejemplo para clarificar estos conceptos.

    Ejemplo 6.1

    Dado el rbol general de la figura 6.2, se hacen sobre l las siguientes consideraciones:

    MugwumpResaltado

    MugwumpResaltado

    MugwumpResaltado

    MugwumpResaltado

    MugwumpResaltado

    MugwumpResaltado

    MugwumpResaltado

    MugwumpResaltado

    MugwumpResaltado

    MugwumpResaltado

    MugwumpResaltado

    MugwumpResaltado

  • 1. A es la raz del rbol.

    1. B es hijo de A.

    C es hijo de A. D es hijo de B. E es hijo de B. e hijo de H.

    1. A es padre de B.

    B es padre de D. D es padre de I. C es padre de G. H es padre de L.

    1. B y C son hermanos.

    D, E y F son hermanos. G y H son hermanos. J y K son hermanos.

    1. I, E, J, K, G y L son nodos terminales u hojas.

    1. B, D, F, C y H son nodos interiores.

    1. El grado del nodo A es 2.

    El grado del nodo B es 3. El grado del nodo C es 2. El grado del nodo D es 1. El grado del nodo E es 0.

  • El grado del rbol es 3.

    1. El nivel del nodo A es 1.

    El nivel del nodo B es 2. El nivel del nodo D es 3. El nivel del nodo C es 2. El nivel del nodo L es 4.

    1. La altura del rbol es 4.

    5.1.1 Clasificacin de rboles.

    1. rboles Binarios 2. rboles Balanceados 3. rboles Multicaminos 4. rboles B 5. rboles B+

  • 5.2 Arboles Binarios

    Introduccin

    Un rbol ordenado es aquel en el que las ramas de los nodos del rbol estn ordenadas. Los rboles ordenados de grado 2 son de especial inters puesto que representan una de las estructuras de datos ms importantes en computacin, conocida como rboles binarios. En un rbol binario cada nodo puede tener como mximo dos subrboles y siempre es necesario distinguir entre el subrbol izquierdo y el subrbol derecho. Formalmente, se define un rbol binario de tipo T como una estructura homognea que es la concatenacin de un elemento de tipo T, llamada raz, con dos rboles binarios disjuntos, llamados subrbol izquierdo y derecho de la raz. Una forma particular de rbol binario puede ser la estructura vaca. Los rboles binarios tienen mltiples aplicaciones. Se los puede utilizar para representar una estructura en la cual es posible tomar decisiones con dos opciones en distintos puntos de un proceso, para representar un rbol genealgico (construido en forma ascendente y donde se muestran los ancestros de un individuo dado), para representar la historia de un campeonato de tenis (construido en forma ascendente y donde existe un ganador, 2 finalistas, 4 semifinalistas y as sucesivamente) y para representar expresiones algebraicas construidas con operadores binarios. Esto slo por citar algunos de sus mltiples usos.

    La figura 6.6 muestra tres diagramas correspondientes a una estructura de rbol binario. En la figura 6.6a) hay un rbol binario de bsqueda, en la figura 6.6b) el rbol binario que representa la expresin (A*B) + (C/D)^3.5 y en la figura 6.6c) el rbol genealgico correspondiente a uno de los autores de este libro.

    Los rboles ordenados de grado mayor a 2 representan tambin estructuras importantes. Se conocen con el nombre de rboles multicaminos.

    MugwumpResaltado

    MugwumpResaltado

    MugwumpResaltado

  • RBOLES BINARIOS DISTINTOS, SIMILARES Y EQUIVALENTES

    Dos rboles binarios son distintos cuando sus estructuras son diferentes. En la figura 6.7 se presentan dos ejemplos de rboles binarios distintos.

    Dos rboles binarios son similares cuando sus estructuras son idnticas, pero la informacin que contienen sus nodos difiere entre s. En la figura 6.8 se presentan dos ejemplos de rboles binarios similares.

    MugwumpResaltado

    MugwumpResaltado

    MugwumpResaltado

    MugwumpResaltado

  • Por ltimo, los rboles binarios equivalentes se definen como aquellos que son similares y adems los nodos contienen la misma informacin. La figura 6.9 contiene dos ejemplos de rboles binarios equivalentes.

    A fin de clarificar los conceptos anteriores, vase el siguiente ejemplo.

    Ejemplo 6.3

    Dados los rboles binarios de la figura 6.10 se realizan las siguientes consideraciones:

    MugwumpResaltado

    MugwumpResaltado

    MugwumpResaltado

    MugwumpResaltado

  • En el rbol de la figura 6.10c) es distinto de los rboles de la figura 6.10a), 6.10b) y 6.10a). Los rboles de la figura 6.10a), 6.10b) y 6.10d) son similares. Los rboles de la figura 6.10a) y 6.10d) son equivalentes.

    RBOLES BINARIOS COMPLETOS Se define un rbol binario completo como un rbol en el que todos sus nodos, excepto los del ltimo nivel, tienen dos hijos; el subrbol izquierdo y el subrbol derecho. En la figura 6.11 se presentan dos ejemplos de rboles binarios completos.

    Los nodos del rbol binario sern representados como registros, que contendrn como mnimo tres campos. En un campo se almacenar la informacin del nodo. Los dos restantes se utilizarn para apuntar los subrboles izquierdo y derecho respectivamente del nodo en cuestin. Dado el siguiente nodo T:

    ste tiene tres campos:

    IZQ: campo donde se almacena la direccin del subrbol izquierdo del nodo T. INFO: campo donde se almacena la informacin de inters del nodo. Normalmente en este campo y en el transcurso de este curso se almacenar un valor simple: nmero o carcter. Sin embargo, en la prctica es comn almacenar en este campo registros, arreglos y conjuntos. DER: campo donde se almacena la direccin del subrbol derecho del nodo T.

    La definicin de un rbol binario en lenguaje algortmico es como sigue:

    Enlace = ^nodo Nodo = registro

    MugwumpResaltado

    MugwumpResaltado

  • Izq: tipo enlace Info: tipo dato Der: tipo enlace { Fin de la definicin }

    Nota: se utiliza el smbolo ^ para representar el concepto de dato tipo puntero.

    Ejemplo 6.6

    Considrese el rbol binario de la figura 6.19a), que representa la expresin algebraica (A * B) + (C / D) ^ 3.5. Su representacin en memoria es como la presentada en la figura 6.19b). Note que en la figura 6.19b) se utiliza el trmino NIL para referirse al rbol vaco.

    5.2 Operaciones bsicas sobre Arboles binarios

    5.2.1 Creacin. Dar de alta el primer nodo del rbol con su liga derecha igual a nulo y liga izquierda igual a nulo.

    Algoritmo de creacin

    CREA(RAIZ) LEER RAIZ.INFO RAIZ.LIGAIZQ=NULL RAIZ.LIGADER=NULL

    MugwumpResaltado

    MugwumpResaltado

    MugwumpResaltado

  • 5.2.2 Insercin La insercin es una operacin que se puede realizar eficientemente en un rbol binario de bsqueda. La estructura crece conforme se inserten elementos al rbol. Los pasos que deben realizarse para insertar un elemento a un rbol binario de bsqueda son los siguientes:

    1. Debe compararse la clave a insertar con la raz del rbol. Si es mayor, debe avanzarse hacia el subrbol derecho. Si es menor, debe avanzarse hacia el subrbol izquierdo.

    2. Repetir sucesivamente el paso 1 hasta que se cumpla alguna de las siguientes condiciones: 3. El subrbol derecho es igual a vaco, o el subrbol izquierdo e