Conceptos de árboles

    %%{ init: { 'flowchart': { 'curve': 'basis' } } }%%
graph
    classDef normal stroke:#f05,fill:#f05,color:black;
    classDef raiz stroke:#0ef,fill:#0ef,color:black;
    classDef hoja stroke:#0f5,fill:#0f5,color:black;

    A1((A)):::normal
    B1((B)):::normal
    C1((C)):::normal
    D1((D)):::normal
    E1((E)):::normal
    F1((F)):::normal
    G1((G)):::normal
    H1((H)):::normal

    A2((Raíz)):::raiz
    B2((Interno)):::normal
    C2((Interno)):::normal
    D2((Hoja)):::hoja
    E2((Hoja)):::hoja
    F2((Interno)):::normal
    G2((Hoja)):::hoja
    H2((Hoja)):::hoja

    subgraph Ascendientes
        A1 --- B1
    end

    subgraph nodo
        B1 --- C1
    end

    B1 --- D1

    subgraph D1escendientes
        C1 --- E1
        C1 --- F1
        F1 --- G1
        F1 --- H1
    end

    A2 --- B2
    B2 --- C2
    B2 --- D2
    C2 --- E2
    C2 --- F2
    F2 --- G2
    F2 --- H2

    %%{ init: { 'flowchart': { 'curve': 'basis' } } }%%
graph
    classDef normal stroke:#f05,fill:#f05,color:black;
    classDef padre stroke:#0ef,fill:#0ef,color:black;
    classDef hermano stroke:#fe0,fill:#fe0,color:black;
    classDef hijo stroke:#0f5,fill:#0f5,color:black;

    1(Padre):::padre
    2(Hermano):::hermano
    3(Hijo):::hijo

    A((A)):::normal
    B((B)):::padre
    C((C)):::hermano
    D((D)):::hermano
    E((E)):::hijo
    F((F)):::hijo
    G((G)):::normal
    H((H)):::normal

    A ~~~ 1
    B ~~~ 2
    C ~~~ 3
    A ~~~ D

    A --- B
    B --- C
    B --- D
    C --- E
    C --- F
    F --- G
    F --- H

Definición de árbol binario

• Árbol binario equilibrado: cuando la diferencia de altura entre los subárboles de cualquier nodo es como máximo una unidad.

• Árbol binario lleno: un árbol binario de altura es lleno si todos sus nodos tienen dos hijos y todas sus hojas están al mismo nivel.
  ==> Todo árbol lleno es equilibrado.

• Árbol binario completo: un árbol binario de altura $h$ es completo si está lleno hasta $h-1$, con el nivel $h$ relleno de izquierda a derecha.
  ==> Un árbol binario completo es equilibrado.
  ==> Si un árbol es lleno, también es completo.

TAD Árbol Binario

Los valores del TAD Árbol Binario (ABin) son árboles binarios donde cada nodo contiene un dato del tipo elem. Es un TAD mutable, dado que insizq/insder, supizq/supder y modificar; insertan, eliminan y modifican respecticamente los elementos del árbol.

//// Lectura ////
*crear() -> abin           Crea un abin vacío
es_vacio(A: abin) -> bool  true si A está vacío
leer(A: abin) -> elem      Contenido del nodo raíz de A.
izq(A: abin) -> abin
der(A: abin) -> abin       Subárbol izquierdo/derecho de A.
                           Si no existe, NULL.

//// Modificación ////
insizq(A: abin, E: elem)
insder(A: abin, E: elem)
    Requisitos: es_vacio(A) = false
                es_vacio(izq/der(A)) = true
    Inserta un nodo con contenido E a la izquierda/derecha

supizq(A: abin)
supder(A: abin)
    Requisitos: es_vacio(A) = false
    Elimina el subárbol izquierdo/derecho, incluyendo descendientes

modificar(A: abin, E: elem)
    Sobreescribe el nodo raíz de A con E

Recorridos

Anchura

Se recorre el árbol por niveles, de izquierda a derecha:

    flowchart
    classDef node stroke:#f05,fill:#f05,color:black;
    1((1)) --- 2((2))
    1 --- 3((3))
    2 --- 4((4))
    2 --- 5((5))
    3 --- 6((6))

Para realizarlo, se necesita una cola como estructura auxiliar:

1. Añadir la raíz a la cola.
2. Tomar el primer elemento de la cola, mostrarlo en la secuencia, y meter sus hijos izquierdo y derecho (en ese orden) en la cola.
3. Repetir el paso 2 hasta que la cola se vacíe.

Profundidad

Se recorre el árbol según sus ramas, descendiendo o subiendo niveles. Hay varios tipos dependiendo qué dato se muestra primero:

    flowchart
    classDef inorden stroke:#f05,fill:#f05,color:black;
    classDef preorden stroke:#0ef,fill:#0ef,color:black;
    classDef postorden stroke:#0f5,fill:#0f5,color:black;

    A(Inorden):::inorden ~~~ A5((5)):::inorden
    A5 --- A2((2)):::inorden
    A5 --- A7((7)):::inorden
    A2 --- A1((1)):::inorden
    A2 --- A4((4)):::inorden
    A4 --- A3((3)):::inorden
    A7 --- A6((6)):::inorden

    B(Preorden):::preorden ~~~ B1((1)):::preorden
    B1 --- B2((2)):::preorden
    B2 --- B3((3)):::preorden
    B2 --- B4((4)):::preorden
    B4 --- B5((5)):::preorden
    B1 --- B6((6)):::preorden
    B6 --- B7((7)):::preorden

    C(Postorden):::postorden ~~~ C7((7)):::postorden
    C7 --- C4((4)):::postorden
    C4 --- C1((1)):::postorden
    C4 --- C3((3)):::postorden
    C3 --- C2((2)):::postorden
    C7 --- C6((6)):::postorden
    C6 --- C5((5)):::postorden

1void inorden(abin A) {
2    if (es_vacio(A))
3        return;
4
5    inorden(izq(A));         // I
6    printf("%d\n", leer(A)); // R
7    inorden(der(A));         // D
8}

1void preorden(abin A) {
2    if (es_vacio(A))
3        return;
4
5    printf("%d\n", leer(A)); // R
6    preorden(izq(A));        // I
7    preorden(der(A));        // D
8}

1void postorden(abin A) {
2    if (es_vacio(A))
3        return;
4
5    postorden(izq(A));       // I
6    postorden(der(A));       // D
7    printf("%d\n", leer(A)); // R
8}

Árboles de expresión

• Se usan para almacenar expresiones como (6+7)*4-1 en memoria, lo que resulta muy útil para compiladores.
• Los paréntesis no se almacenan, pero están en la forma del árbol.
• Todos los operandos están en las hojas.
• Toda raíz de cada subárbol es un operador

La expresión (A+B)*C genera el siguiente árbol de expresión:

    flowchart
    classDef node stroke:#f05,fill:#f05,color:black;

    M((*)) --- S((+))
    S --- A((A))
    S --- B((B))
    M --- C((C))

Y se se realizan recorridos sobre dicho árbol:

• Inorden: A+B*C
• Preorden: *+ABC
• Postorden: AB+C* (A y B, suma. El resultado y C, multiplica)

Árboles para búsqueda

• Motivación: compatibilidad con algoritmos eficientes, si los datos están ordenados, se pueden tomar decisiones más inteligentes que hacer fuerza bruta.
• Ejemplo: búsqueda en una lista
  • Búsqueda lineal: $O(n)$
  • Búsqueda binaria: $O(\log{(n)})$

Árbol binario de búsqueda (ABB)

//// Lectura ////
*crear() -> abin
leer(A: abin) -> elem
izq(A: abin) -> abin
der(A: abin) -> abin
es_vacio(A: abin) -> bool
es_miembro(A: abin, E: elem) --> bool
buscar(A: abin, K: clave) --> elem

//// Modificación ////
insertar(A: abin, K: clave, E: elem) -> bool
    Inserta un nodo con contenido E
    Si el nodo ya existe, no hace nada
    true si se modificó A

suprimir(A: abin, K: elem) -> bool
    Requisitos: es_vacio(A) = false
    Elimina el nodo de clave K
    Si el nodo no existe, no hace nada
    true si se modificó A

modificar(A: abin, K: clave, E: elem) -> bool
    Sobreescribe el nodo de clave K con E
    Si el nodo no existe, no hace nada
    true si se modificó A

La ventaja principal es que el tiempo de ejecución promedio es $O(\log{(n)})$, siempre y cuando el árbol esté balanceado, de lo contrario, será como una lista, $O(n)$.

    flowchart
    classDef node stroke:#f05,fill:#f05,color:black;
    classDef hidden stroke:none,fill:none,color:none

    A((55)) --- B((30))
    B --- C((4))
    B --- D((41))
    A --- E((75))
    E ~~~ H1( ):::hidden
    E --- F((85))

    G((55)) --- I((41))
    G ~~~ H2( ):::hidden
    I --- J((30))
    I ~~~ H3( ):::hidden
    J --- K((4))
    J ~~~ H4( ):::hidden

El recorrido en inorden devuelve los datos ordenados: 4 30 41 55 75 85.

Montículo binario (Heap)

Implementación mediante arrays

La implementación más natural de un montículo binario es el árbol binario, pero se puede aprovechar su propiedad de completo:

• A[0]: nodo raíz
• A[2*k + 1]: hijo izquierdo de k
• A[2*k + 2]: hijo derecho de k
• A[(k - 1) / 2]: padre de k

Cola de prioridad con montículos binarios

void insertar(ColaPrio C, Elem E, Prio P)
void suprimir(ColaPrio C)

Estas operaciones se pueden completar en $O(\log{(n)})$, dado que la altura de un árbol binario completo de $n$ nodos es $\log{(n + 1)}$.

Monticulización / Heapify

Dado un array de datos, se construye un montículo:

1. Se crea un árbol a partir del array
2. Si el árbol tiene $L$ niveles, desde el nivel $L-1$ hasta 1 repetir:
   • Comprobar la condición de montículo, si no la cumple, intercambiar con el menor/mayor de sus hijos
   • Propagar ese cambio desde el nivel actual hasta $L-1$

Árbol equilibrado (AVL)

Se ha comentado que la eficiencia de un Árbol Binario de Búsqueda depende de su estructura, lo que viene dado por el orden de inserción de los datos.

• Datos en orden creciente: solo ramas derechas
• Datos en orden decreciente: solo ramas izquierdas

    flowchart
    classDef node stroke:#0f5,fill:#0f5,color:black;
    classDef hidden stroke:none,fill:none,color:none

    T(Equilibrado) ~~~ A((#45;1))
    A --- B((1))
    A --- C((1))
    B --- D((0))
    B --- E((#45;1))
    C ~~~ H1( ):::hidden
    C --- F((0))
    E --- G((0))
    E ~~~ H2( ):::hidden

    classDef other stroke:#f05,fill:#f05,color:black;

    T2(No equilibrado):::other ~~~ A2((#45;3)):::other
    A2 --- B2((#45;3)):::other
    A2 --- C2((0)):::other
    B2 --- D2((2)):::other
    B2 ~~~ H3( ):::hidden
    D2 ~~~ H4( ):::hidden
    D2 --- E2((#45;1)):::other
    E2 --- F2((0)):::other
    E2 ~~~ H5( ):::hidden

if Hrd == Hri:
    insertar en la rama izquierda o derecha
    no provocará desequilibrio

elif Hrd > Hri:
    insertar en izquierdo => Hrd == Hri (no hay desquilibrio)
    insertar en derecho   => Hay que reestructurar

elif Hrd < Hri:
    insertar en izquierdo => Hay que reestructurar
    insertar en derecho   => Hrd == Hri (no hay desquilibrio)

Árbol B

También se cumple que:

$$ \text{ramas} \not = 0 \implies \text{claves} = \text{ramas} - 1 $$

Árbol B+

typedef struct {
    elem nodos[MAX];
    int cuenta;
} PaginaHoja;

typedef struct {
    clave claves[MAX];
    ArbolBmas ramas[MAX+1];
    int cuenta;
} PaginaInterna;

Resumen