Scribd Logo
Cargar

¡Te damos la bienvenida a Scribd!

  • 15 vistas

    Unidad 3 - Clase 8 - Arboles

    Cargado por

    Juan Manuel Desojo
    El documento define un árbol como una estructura de datos que puede definirse recursivamente como una estructura vacía o un nodo más un número finito de subárboles disjuntos. Explica que un árbol binario tiene como máximo dos subárboles por nodo y que también puede definirse como un grafo acíclico y conexo. Finalmente, introduce los árboles AVL como un tipo de árbol binario balanceado y explica algunos términos de nomenclatura relacionados con árboles como raíz, rama, nodo, ho

    Copyright:

    © All Rights Reserved
    Descargue como PDF, TXT o lea en línea desde Scribd

    Unidad 3 - Clase 8 - Arboles

    Cargado por

    Juan Manuel Desojo
    15 vistas15 páginas
    El documento define un árbol como una estructura de datos que puede definirse recursivamente como una estructura vacía o un nodo más un número finito de subárboles disjuntos. Explica que un árbol binario tiene como máximo dos subárboles por nodo y que también puede definirse como un grafo acíclico y conexo. Finalmente, introduce los árboles AVL como un tipo de árbol binario balanceado y explica algunos términos de nomenclatura relacionados con árboles como raíz, rama, nodo, ho

    Derechos de autor

    © © All Rights Reserved

    Formatos disponibles

    PDF, TXT o lea en línea desde Scribd

    ¿Le pareció útil este documento?

    ¿Este contenido es inapropiado?

    El documento define un árbol como una estructura de datos que puede definirse recursivamente como una estructura vacía o un nodo más un número finito de subárboles disjuntos. Explica que un árbol binario tiene como máximo dos subárboles por nodo y que también puede definirse como un grafo acíclico y conexo. Finalmente, introduce los árboles AVL como un tipo de árbol binario balanceado y explica algunos términos de nomenclatura relacionados con árboles como raíz, rama, nodo, ho

    Copyright:

    © All Rights Reserved
    Descargue como PDF, TXT o lea en línea desde Scribd
    Descargar como pdf o txt
    15 vistas15 páginas

    Unidad 3 - Clase 8 - Arboles

    Cargado por

    Juan Manuel Desojo
    El documento define un árbol como una estructura de datos que puede definirse recursivamente como una estructura vacía o un nodo más un número finito de subárboles disjuntos. Explica que un árbol binario tiene como máximo dos subárboles por nodo y que también puede definirse como un grafo acíclico y conexo. Finalmente, introduce los árboles AVL como un tipo de árbol binario balanceado y explica algunos términos de nomenclatura relacionados con árboles como raíz, rama, nodo, ho

    Copyright:

    © All Rights Reserved
    Descargue como PDF, TXT o lea en línea desde Scribd
    Descargar como pdf o txt
    Está en la página 1de 15

    01 – PROGRAMACIÓN 1

    MG. NICOLÁS BATTAGLIA


    UNIDAD 3
    ESTRUCTURAS DINÁMICAS 2 - CLASE 8 - ARBOLES
     Un árbol es una estructura de datos, que puede definirse de forma
    ARBOLES
    recursiva como
     Una estructura vacía
     Un elemento o clave de información (nodo) más un número finito de
    estructuras tipo árbol, disjuntos, llamados subárboles.
     Si dicho número de estructuras es inferior o igual a 2, se tiene un árbol
    binario.
     Un árbol es, por tanto, una estructura no secuencial.
     Otra definición nos da el árbol como un tipo de grafo acíclico, conexo y
    no dirigido.
     Es un grafo no dirigido en el que existe exactamente un camino entre todo
    par de nodos.
     Esta definición permite implementar un árbol y sus operaciones empleando
    las representaciones que se utilizan para los grafos.
    ARBOLES

    Grafo Árbol representado como grafo


    Árbol
    representado
    como un
    diagrama en
    columnas
    ARBOLES AVL
     Árbol binario balanceado (Árbol AVL – Por sus siglas Adelson,Velski y Landis, sus
    creadores)
     Un árbol balanceado simplifica en gran medida las operaciones de búsqueda
     Está balanceado cuando para todos sus nodos la altura de la rama izquierda no difiere más
    de una unidad de la altura de la rama derecha (o vicecersa)
     El factor de equilibrio es la diferencia entre las alturas de un subárbol con las del otro
    subárbol: FE=0, -1 o 1.
     FE=0 -> Nodo perfectamente equilibrado
     FE=1 -> Nodo derecho es un nivel más alto
     FE=-1 -> Nodo Izquierdo es un nivel más alto
     FE>=|2| -> Hay que equilibrar el árbol
     P ara equilibrar o balancear un árbol hay que aplcicar rotaciones
    ARBOLES – NOMENCLATURA
    • Raíz: es aquel elemento que no tiene antecesor; ejemplo: a.

    • Rama: arista entre dos nodos.

    • Antecesor: un nodo X es antecesor de un nodo Y si por alguna de las ramas de X se puede llegar a Y.

    • Sucesor: un nodo X es sucesor de un nodo Y si por alguna de las ramas de Y se puede llegar a X.

    • Grado de un nodo: el número de descendientes directos que tiene.

    • Hoja: nodo que no tiene descendientes: grado 0.

    • Nodo interno: aquel que tiene al menos un descendiente.

    • Nivel: número de ramas que hay que recorrer para llegar de la raíz a un nodo.

    • Altura: el nivel más alto del árbol.

    • Anchura: es el mayor valor del número de nodos que hay en un nivel.


    ARBOLES - NOMENCLATURA

     Raíz: es aquel elemento que no tiene antecesor; ejemplo: a.


    ARBOLES - NOMENCLATURA

     Rama: arista entre dos nodos.


    ARBOLES - NOMENCLATURA

     Antecesor: un nodo X es antecesor de un nodo Y si por alguna de las ramas de X se puede llegar a Y.
    ARBOLES - NOMENCLATURA

     Sucesor: un nodo X es sucesor de un nodo Y si por alguna de las ramas de Y se puede llegar a X.
    ARBOLES - NOMENCLATURA

     Grado de un nodo: el número de descendientes directos que tiene. Ejemplo: c tiene grado 2, d tiene grado 0, a
    tiene grado 2.
    ARBOLES - NOMENCLATURA

     Hoja: nodo que no tiene descendientes: grado 0. Ejemplo: d


    ARBOLES - NOMENCLATURA

     Nodo interno: aquel que tiene al menos un descendiente.


    ARBOLES - NOMENCLATURA

     Nivel: número de ramas que hay que recorrer para llegar de la raíz a un nodo. Ejemplo: el nivel del nodo a es 1
    (es un convenio), el nivel del nodo e es 3.
    ARBOLES - NOMENCLATURA

     Anchura: es el mayor valor del número de nodos que hay en un nivel. En la figura, la anchura es 3.

    También podría gustarte