Árboles

Estructura de Datos. Árbol binario. Recorrido. Codificación. Algoritmos fundamentales

  • Enviado por: Jesús Alonso
  • Idioma: castellano
  • País: España España
  • 16 páginas

publicidad

TEMA 5

ÁRBOLES(*)

Una de las estructuras las datos más importantes y prominentes que existen es el árbol. No es un árbol en el sentido botánico de la palabra, sino uno de naturaleza más abstracta. Todos hemos visto usar tales árboles para describir conexiones familiares. Los dos tipos más comunes de árboles familiares son el `árbol de antecesores', que empieza en un individuo y va hacia atrás a través de padres, abuelos, etc., y el `árbol de descendientes', que va hacia delante a través de hijos, nietos, etc.

David Harel, `The Spirit of Computing'

(*)Con la colaboración de Gemma Morales de Paz (**)

OBJETIVOS DE ESTE CAPITULO:

• Descubrir los árboles como paradigma de los tipos Recursivos de Datos

• ¿Cúando utilizar un árbol para almacenar información?

• Diferenciar las formas de recorrer un árbol

INDICE TEMA - 5

Árboles. 9 horas.

Definición

Conceptos básicos

Árboles binarios

Árbol Binario de Búsqueda

Tipos de recorrido sobre árboles.

  • 3.2.1 Codificación

  • Características y Utilidades de los Recorridos.

  • Algoritmos fundamentales

    Inserción en un árbol Binario de Búsqueda.

    Borrado en un árbol binario de Búsqueda

    1. Definición.

    Definición de Árbol. Similitud con las Listas.

    Árbol Degenerado.

    ¿Cómo representarlos?

    • Mediante Grafos:

    1

    2 3 Figura - 1.

    Representación de un árbol

    mediante un grafo

    4 5 6 7

    • Mediante Conjuntos.

    1

    2 3 Figura - 2.

    Representación

    de un árbol mediante

    4 5 6 7 un grafo

    Una estructura árbol con tipo base T es:

    Bien la estructura vacía.

    O bien un nodo de tipo T junto con un número finito de estructuras árbol, de tipo base T, disjuntas, llamadas subárboles.

    Declaración:

    TArbol = ^TNodo;

    TNodo = Record

    Clave: TClave;

    Izq, Der: TArbol

    End;

    2. Conceptos

    Antecesor

    Antecesor Directo

    Sucesor

    Sucesor Directo

    Nodo Raíz.

    Nodo Hoja

    Nodo Interno

    Nivel de un Nodo

    Grado de un Nodo

    Grado de un Árbol

    Altura de un Árbol

    Longitud de Camino

    Longitud de Camino Interno

    Árbol de expansión

    Longitud de Camino Externo

    Tabla - 1. Conceptos diversos sobre árboles.


    Concepto

    Definiciones

    Ejemplo

    Observaciones

    Antecesor Directo

    La clave "X" está inmediatamente por encima de la clave "Y" en el árbol y además están unidas.

    El 2 es antecesor directo del 4, del 5 y del 6

    La clave "X" es antecesora directa de la clave "Y"

    Antecesor

    Existe una sucesión de claves antecesoras directas para llegar desde "Y" hasta "X".

    El 1 es antecesor del 4

    La clave "X" es antecesora de "Y"

    Sucesor Directo

    La clave "X" está inmediatamente por debajo de la clave "Y" en el árbol y además están unidas.

    El 5, el 4 y el 6 son sucesores directos del 2

    Una clave "X" es sucesora directa de otra clave "Y"

    Sucesor

    Existe una sucesión de claves sucesoras directas para llegar desde "X" hasta "Y".

    El 4 es sucesor del 1

    La clave "X" es sucesora de "Y")

    Nodo Raíz

    aquel que no tiene antecesores.

    El 1

    Tabla -2. Conceptos básicos. Los ejemplos hacen referencia a la Figura - 1 (I).

    Concepto

    Definiciones

    Ejemplo

    Observaciones

    Nodo Hoja

    Aquel que no tiene sucesores.

    El 4, el 5, el 6 y el 7

    Nodo Interno

    Aquel que no es ni raíz ni hoja.

    El 2 y el 3

    Nivel de un Nodo

    Nº de tramos que hay que recorrer desde el nodo raíz hasta el nodo del que quiero calcular su nivel.

    El nodo 7 tiene nivel 3.

    Se considera que la raíz está en el nivel 1.

    Grado de un Nodo

    Nº de descendientes directos que tiene.

    El 1 tiene grado 2.

    El 2 tiene grado tiene grado 3.

    Grado de un Árbol

    Mayor de los grados de los nodos que componen el árbol.

    Grado del árbol = 3.

    Un árbol de grado 1 ! Lista

    Un árbol de grado 2 ! Árbol Binario

    Altura de un Árbol

    Mayor de los niveles de los nodos que forman el árbol.

    Altura del árbol = 3.

    Tabla -3. Conceptos básicos. Los ejemplos hacen referencia a la Figura - 1 (II).

    Concepto

    Definiciones

    Ejemplo

    Observaciones

    Longitud de Camino

    Nº de arcos que hay que atravesar para ir desde la raíz hasta un nodo.

    Longitud de camino del nodo 7 = 3.

    La longitud de camino del nodo raíz se considera 1. Coincide con el NIVEL DE UN NODO.

    Longitud de camino Interno

    Nº de arcos que hay que atravesar para ir desde la raíz hasta un nodo. La longitud de camino del nodo raíz se considera 1.

    1+2+2+3+3+3+3 = 17

    n

    " i * nº de claves

    i = 1

    Árbol de expansión

    Resultante de hacer que todos los nodos del árbol tengan el mismo grado.

    Implica que hay que añadir una serie de Nodos Especiales que no pertenecen al árbol para conseguir esto (ver figura-3 ).

    Longitud de camino externo

    Suma de las longitudes de camino de los nodos especiales.

    4*12 + 2*3 + 2 = 56

    Tabla -4. Conceptos básicos. Los ejemplos hacen referencia a la Figura - 1 (III).


    1

    2 3

    4 5 6 7

    Nodo

    Especial

    Figura - 3. Árbol de expansión de uno dado.

    3. Árboles binarios

    Definición.

    Estructura tipo Árbol de grado dos:

    Bien una estructura vacía o bien un elemento del tipo base y como máximo 2 estructuras de tipo árbol.

    1

    2 3 Figura - 4

    Árbol binario

    4 5 6

    3.1. Árbol binario de Búsqueda

    Elementos Menores subárbol izquierdo

    Elementos Mayores subárbol derecho


    5

    Figura - 5.

    Árbol binario de búsqueda 3 8

    1 4 6 9

    3.2. Tipos de recorrido sobre Árboles.

    Recorridos en Profundidad: se alejan cuanto antes de la raíz.

    Tipo de Recorrido

    Secuencia de nodos

    Pre Orden

    { 5; 3; 1; 4; 8; 6; 9 }

    Post Orden

    { 1; 4; 3; 6; 9; 8; 5 }

    Orden Central

    { 1; 3; 4; 5; 6; 8; 9 }

    Recorridos en Amplitud: trata consecutivamente los nodos que se encuentran al mismo nivel

    Tipo de Recorrido

    Secuencia de nodos

    Amplitud

    { 5; 3; 8; 1; 4; 6; 9 }

  • 3.2.1. Codificación

  • Recorridos en Profundidad: Son todos recursivos y requieren una pila para su implementación.

    PREORDEN: procesar primero el subárbol izquierdo, luego el subárbol derecho y luego la raíz.

    Procedure PreOrden ( a: TArbol );

    begin

    if a <> nil then

    begin

    writeln ( a^.Clave ); (* Procesar Raíz *)

    PreOrden ( a^.Izq );

    PreOrden ( a^.Der )

    end

    end;

    POSTORDEN: procesar primero el subárbol izquierdo, luego el subárbol derecho y luego la raíz.

    Procedure PostOrden ( a: TArbol );

    begin

    if a<> nil then

    begin

    PostOrden ( a^.Izq );

    PostOrden ( a^.Der );

    writeln( a^.Clave ) (* Procesar Raíz *)

    end

    end;

    ORDEN CENTRAL: procesar primero el subárbol izquierdo, luego la raíz y luego el subárbol derecho.

    Procedure OrdenCentral ( a: TArbol );

    begin

    if a<> nil then

    begin

    OrdenCentral ( a^.Izq );

    writeln ( a^.Clave ); (* Procesar Raíz *)

    OrdenCentral ( a^.Der )

    end

    end;

    Recorridos en Amplitud: Es imprescindible la utilización de una cola y no está aconsejada la recursividad.

    Procedure Amplitud ( a: TArbol );

    (* Se utiliza una cola para efectuar un recorrido por niveles *)

    var Cola: TCola;

    Aux: TArbol;

    begin

    InicializarCola ( Cola );

    Encolar ( Cola, a ); (* raíz del árbol original*)

    while Not Vacia ( Cola ) do

    begin

    Desencolar ( Cola, Aux );

    if Aux<> NIL then

    begin

    writeln ( Aux^.Clave );

    Encolar ( Cola, Aux^.Izq ); (* subárbol izquierdo *)

    Encolar ( Cola, Aux^.Der ) (* subárbol derecho *)

    end

    end;

    3.3. Características y Utilidades de los Recorridos.

    PREORDEN: Se va a utilizar siempre que queramos comprobar alguna propiedad del árbol ( p.ej.: localizar elementos ).

    ORDENCENTRAL: Se utiliza siempre que nos pidan algo relativo a la posición relativa de las claves o algo que tenga que ver con el orden de las claves ( p.ej.: ¿Cuál es la 3ª clave?).

    POSTORDEN: Se utiliza poco. Su principal utilidad consiste en liberar la memoria ocupada por un árbol.

    AMPLITUD: Se utiliza siempre que nos pidan operaciones cuyo tratamiento se haga por niveles.

    4. ALGORITMOS FUNDAMENTALES

    4.1. Procedimiento de inserción en un árbol Binario de Búsqueda.

    Todas las inserciones de realizan en Nodos Hoja.

    CASOS

    ACCIONES

    No se permiten claves repetidas

    Claves menores a la izquierda

    Claves mayores a la derecha

    Sí se permiten claves repetidas

    Claves menores a la izquierda

    Claves mayores a la derecha

    Claves iguales a la izquierda

    CODIFICACIÓN

    INSERCIÓN SIN CLAVES REPETIDAS

    Pasos:

    - Recorrer el árbol buscando la clave a insertar:

    • Si no está Se inserta

    • Si está Mensaje de error

    Procedure Insertar ( var a: TArbol; Elem: TClave );

    begin

    if a = nil then (* búsqueda de la posición adecuada *)

    begin

    new ( a );

    a^.Clave := Elem;

    a^.Izq := nil;

    a^.Der := nil

    end

    if a^.Clave > Elem (* búsqueda en el subárbol izq. *)

    then Insertar ( a^.Izq, Elem )

    else if a^.Clave < Elem (* búsqueda en el subárbol der. *)

    then Insertar ( a^.Der, Elem )

    end;

    INSERCIÓN CON CLAVES REPETIDAS

    Pasos:

    - Recorrer el árbol buscando la clave a insertar:

    • Insertar la clave.

    Procedure Insertar ( var a: TArbol; Elem: TClave );

    begin

    if a= nil then (* búsqueda de la posición adecuada *)

    begin

    new ( a );

    a^.Clave := Elem;

    a^.Izq := nil;

    a^.Der := nil

    end

    else

    if a^.Clave >= Elem then (* inserción *)

    Insertar ( a^.Izq, Elem )

    end;

    4.2. Procedimiento de borrado en un árbol binario de Búsqueda.

    CASOS

    ACCIONES

    La clave no está

    Ninguna o mensaje de notificación

    La clave está

    • Es un nodo hoja (a := NIL)

    • Es un nodo interno (a^.Der , a^.Izq <> NIL)

    • Buscar la clave mayor de las menores ó Buscar la clave menor de las mayores.

    • Se cambia con la clave a borrar y se elimina la clave cambiada.

    Nodo con 1 sólo descendiente

    a:= a^.Izq a:= a^.Der

    ( ver Figura - 6 )

    a a

    a^.izq a^.der

    Figura - 6. Borrado en nodo con un sólo descendiente

    Procedure Borrar ( var a: TArbol; Elem: TClave );

    var Aux: TArbol;

    Procedure MayorMenores ( var b: TArbol );

    begin

    if b^.Der = nil then

    begin

    Aux^.Clave := b^.Clave;

    Aux := b;

    b := b^.Izq

    end

    else

    MayorMenores( b^.Der )

    end;

    begin (* Borrar *)

    if a = nil then

    writeln ( 'la clave no está' )

    else

    if a^.Clave > Clave then (* búsqueda de la clave *)

    Borrar ( a^.Izq, Clave )

    else

    if a^.Clave < Clave then (* búsqueda de la clave *)

    Borrar ( a^.Der, Clave )

    else begin (* 2 *)

    Aux := a;

    if a^.Izq = nil then

    a := a^.Der

    else

    if a^.Der = nil then

    a := a^.Izq

    else MayorMenores( a^.Izq );

    dispose ( Aux )

    end (* 2 *)

    end; (* Borrar *)

    (**) Fuentes : - N.Wirth, Algoritmos+ E.Datos = Programas, Ed. Castillo, 1983.

    - Dale y Lilly, Pascal y Estructuras de Datos, Ed. McGrawHill, 1989.

    Normalmente, la pila del sistema.

    Si el árbol es de búsqueda, puede comprobarse fácilmente que al realizar un recorrido en orden central, obtenemos un listado ordenado de los elementos del árbol.

    Cap. 5 ED-I. ÁRBOLES

    Jesús Alonso S. Dpt. OEI p-7-

    ESCUELA UNIVERSITARIA DE INFORMÁTICA ESTRUCTURAS DE DATOS-I

    Jesús Alonso S. Dpt. OEI

    Jesús Alonso S. Dpt. OEI p-16-

    ESCUELA UNIVERSITARIA DE INFORMÁTICA ESTRUCTURAS DE DATOS-I

    Jesús Alonso S. Dpt. OEI