Scribd Logo
Cargar

¡Te damos la bienvenida a Scribd!

  • 25 vistas

    Presentacion Tutoria11 EPED

    Cargado por

    Agustito CM
    El documento resume los conceptos de árboles binarios de búsqueda (ABB) y árboles AVL. Explica las operaciones de inserción y eliminación en ABB e introduce el concepto de equilibrio en AVL. Detalla los cuatro casos de rotaciones simples y dobles que pueden ocurrir durante la inserción en un AVL para mantener su equilibrio. Finalmente, muestra un ejemplo paso a paso de la inserción de elementos en un AVL y las rotaciones necesarias.

    Copyright:

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

    Presentacion Tutoria11 EPED

    Cargado por

    Agustito CM
    25 vistas33 páginas
    El documento resume los conceptos de árboles binarios de búsqueda (ABB) y árboles AVL. Explica las operaciones de inserción y eliminación en ABB e introduce el concepto de equilibrio en AVL. Detalla los cuatro casos de rotaciones simples y dobles que pueden ocurrir durante la inserción en un AVL para mantener su equilibrio. Finalmente, muestra un ejemplo paso a paso de la inserción de elementos en un AVL y las rotaciones necesarias.

    Título original

    presentacion_tutoria11_EPED

    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 resume los conceptos de árboles binarios de búsqueda (ABB) y árboles AVL. Explica las operaciones de inserción y eliminación en ABB e introduce el concepto de equilibrio en AVL. Detalla los cuatro casos de rotaciones simples y dobles que pueden ocurrir durante la inserción en un AVL para mantener su equilibrio. Finalmente, muestra un ejemplo paso a paso de la inserción de elementos en un AVL y las rotaciones necesarias.

    Copyright:

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

    Presentacion Tutoria11 EPED

    Cargado por

    Agustito CM
    El documento resume los conceptos de árboles binarios de búsqueda (ABB) y árboles AVL. Explica las operaciones de inserción y eliminación en ABB e introduce el concepto de equilibrio en AVL. Detalla los cuatro casos de rotaciones simples y dobles que pueden ocurrir durante la inserción en un AVL para mantener su equilibrio. Finalmente, muestra un ejemplo paso a paso de la inserción de elementos en un AVL y las rotaciones necesarias.

    Copyright:

    © All Rights Reserved
    Descargue como PDF, TXT o lea en línea desde Scribd
    Descargar como pdf o txt
    de 33

    TUTORÍA 11/13 → Árboles 2/3

    1) ABB
    ➢ Definición.
    ➢ Operaciones:
    • Insert.
    • Remove.
    ➢ Implementación

    2) AVL
    ➢ Definición.
    ➢ Inserciones / Rotaciones

    3) Inserción / Rotación 2016 1º-Semana


    1) ABB

    ➢ Definición

    - Estructura que facilita la búsqueda ordenada. Valores de clave del SA izq son menores que los
    valores clave del SA der.

    a.
    b.
    c.

    Aquí les dejo unos ejemplos de ABB o …… ¿no?


    Sol:
    C no es ABB
    ➢ Operaciones:Insert

    ¿Dónde insertaríamos el nodo 5,7,10?


    Solución:
    ➢ Operaciones:Remove

    ¿Con que casos nos podemos encontrar?


    ➢ Nodo a eliminar tenga 0 hijos. (Desconectar 4)

    ➢ Nodo a eliminar tenga 1 hijo (Desconectar 3)


    • Conectamos padre de eliminado con el hijo del eliminado.

    ➢ Nodo a eliminar tenga 2 hijos (Desconectar 2)


    • Reemplazamos el nodo a eliminar por el más pequeño del subárbol derecho. (el 2 x el 3)
    • Acondicionamos hijos del reemplazado. (el 4 pasa a la izquierda del 5)
    ➢ Implementación
    BN<T> find (T x, BN<T> t)
    public class BN <T> {
    {
    private BN HijoIzq;
    ///Iterativo
    private BN HijoDer;
    private <T> element;
    public Nodo ( <T> dato, BN<T> I, BN<T> D) {
    this.element = dato; }

    this.HijoIzq = I;
    this.HijoDer = D;
    }
    public BN<T> insert (T x, BN<T> t)
    public class BST <T> {
    private BN<T> root; {

    public BST (<T> x ) {


    this.root = new ///Recursivo
    BN<T>(x,NULL,NULL);
    }
    }
    }
    Solución:
    BN<T> find (T x, BN<T> t)
    {
    while (t!=NULL) {
    if (t.element < x) {
    t=t.Hijoder;
    } else if (t.element > x ) {
    t=t.Hijoizq;
    } else {
    return t;
    }
    }
    }
    Solución:
    public BN<T> insert (T x, BN <T> t)
    {
    If (t == NULL)
    t = new BN <T>(x);
    else if (t.elem < x)
    t.hijoDer = insert(x,t.hijoDer);
    else if (t.elem > x)
    t.hijoIzq = insert(x,t.hijoIzq);
    else
    new Exception…
    return t;
    }
    2) AVL
    ➢ Definición
    - ABB con condición de equilibrio. El SAizq y el SAder pueden diferir en altura como máximo en 1.
    ➢ Inserciones/Rotaciones.
    Objetivo: Reestablecer el factor de equilibrio.
    Caso 1: Rotación simple Izquierda.
    Ejemplo Caso 1:
    Caso 2: Rotación simple Hijo derecho.
    Ejemplo Caso 2:
    Solución:
    Caso 3: Rotación doble izquierda-derecha.
    Ejemplo Caso 3:
    Solución:
    Caso 4: Rotación doble derecha – izquierda
    Inserciones/Rotaciones. 2016 Examen 2ºSemana
    Solución:

    Paso 1 → Inserción de primeros cuatro elementos de la serie. Sin incidencias.


    Paso 2: Se introduce el nodo 1. Árbol desequilibrado FE(3) = 2 → Rotación simple izquierda-izquierda
    Resultado Rotación izquierda. K2 = 3, K1=2, SA = 1
    Paso 3: Se introduce el nodo 6. Árbol desequilibrado FE(7) = 2 → Rotación doble izquierda-derecha
    Resultado Rotación doble izquierda derecha. K3=7, K2 = 3, K1=2, SA = 1, SC=6, SD=9
    Paso 4 → Inserción de elementos 5 y 10. Sin incidencias.
    Paso 5 → Inserción de elemento 4
    Resultado: Rotación simple izquierda. K2 = 6, K1=5, SA = 4
    Paso 6: Inserción elemento 11. Hijo derecho de 10. →FE(9)=2 → Rotación simple derecha
    Paso 7: Inserción elemento 12. AVL Desequilibrado.
    Resultado: FE(3)=2 → K1=3, K2=7, SA=2-1, SB=5-4-6, SC=10-9-11-12 → Rotación simple a derecha.
    Paso 8: Insertamos elemento 13. Provoca desequilibrio FE(11) → Rotación simple a derecha.

    También podría gustarte