Tema 7 y 8 - Árboles Binarios de Búsqueda ABB y Equilibrados AVL

El TAD Árbol Binario de Búsqueda ABB y el TAD Árbol Binario de Búsqueda AVL, especificación informal, implementación y descripción gráfica. Operaciones explicadas de forma gráfica e implementadas. Rotaciones (LL, RR, LR y RL) y factor de equilibrio.

TAD Árbol Binario de Búsqueda ABB

Definición

Es un árbol binario.
Tiene asociada una clave de ordenación k.
Cumple para cualquier nodo T del árbol:
- los valores de los nodos del subárbol izquierdo de T son menores que el valor de T.
- los valores de los nodos del subárbol derecho son T mayores que el valor de T.
Mayor eficiencia frente a…
- estructuras estáticas en operaciones de inserción y eliminación.
- estructuras dinámicas en la operación de búsqueda.

---
title: Árbol binario de búsqueda (ABB)
---
flowchart TB
    k(((k))) --> A[/claves < k\] & B[/claves > k\]

Pros y contras

Eficiencia del proceso de búsqueda en árboles equilibrados

Si los nodos se añaden en un orden aleatorio habrá que equilibrarlo:

---
title: Árbol sin equilibrar
---
flowchart TB
    k[[6]] --> 1[[1]] & 8[[8]]
    1 --> 0[[0]] & 2[[2]]
    2 --> NULL[[NULL]] & 4[[4]]
    8 --> 7[[7]]

Si los nodos se añaden en un orden determinado el árbol degenerará en una lista ordenada:

---
title: Árbol degenerado en lista
---
flowchart TB
    k[[4]] -->  3[[3]] & NULL1[[NULL]]
    3 --> 2[[2]] & NULL2[[NULL]]
    2 --> 1[[1]] & NULL3[[NULL]]

Operaciones

Basándonos en el TAD Árbol definimos las operaciones del árbol de búsqueda a cambiar.

Generadoras

createEmptyTree → Tree

createEmptyTree \rightarrow Tree

insertKey(Tree, Key) → Tree, bool

insertKey(Tree, Key) \rightarrow Tree, bool

Objetivo: Insertar un nodo con información en el árbol, en su lugar correspondiente, de acuerdo al valor de una clave
Entrada:
- Tree: Árbol a modificar
- Key: Dato a insertar
Salida: Tree: Nuevo árbol que resulta de la inserción y verdadero si se ha podido insertar o si la clave existe, falso en caso contrario.
Poscondición: El árbol incorpora un nuevo nodo con los datos si éstos no existían en el árbol

flowchart TB
    Key(Key: 25)
    K[[30]] --> A[[20]] & B[[40]]
    A --> NULL[[NULL]] & C[[25]]
    K -. 25 < 30 .-> A -. 25 > 20 .-> C

Mostrar implementación

// EN CONSTRUCCIÓN
// COLABORA https://github.com/TeenBiscuits/Pasame-Codigo

Observadoras

leftChild(Tree) → Tree

leftChild(Tree) \rightarrow Tree

rightChild(Tree) → Tree

rightChild(Tree) \rightarrow Tree

root(Tree) → Item

root(Tree) \rightarrow Item

isEmptyTree(Tree) → bool

isEmptyTree(Tree) \rightarrow bool

findKey(Key, Tree) → Tree

findKey(Key, Tree) \rightarrow Tree

Objetivo: Devuelve el subárbol cuya raíz contiene la clave
Entrada:
- Key: Dato a buscar
- Tree: Árbol a manipular
Salida: Tree: Acceso al árbol cuya raíz contiene la clave, o nulo si éste no existe (el árbol está vacío o no contiene esa clave)

flowchart TB
    key(Key: 25)
    k[[30]] --> A[[20]] & B[[40]]
    A --> D[[15]] & E[[25]]
    B --> F[[35]] & G[[45]]
    k -. 25 < 30 .-> A -. 25 > 20 .-> E

Mostrar implementación

// EN CONSTRUCCIÓN
// COLABORA https://github.com/TeenBiscuits/Pasame-Codigo

Destructoras

removeKey(Key, Tree) → Tree

removeKey(Key, Tree) \rightarrow Tree

Objetivo: Eliminar el nodo cuyo contenido coincide con la clave
Entrada:
- Key: Clave del nodo a eliminar
- Tree: Árbol a modificar
Salida: Tree: Nuevo árbol sin el nodo eliminado
Precondición: La clave existe en el árbol

flowchart TB
    key(A eliminar: 87)
    A[[120]] --> B[[87]] & C[[140]]
    B --> D[[43]] & E[[93]]
    D --> NULL1(NULL) & F[[65]]
    F --> G[[56]] & NULL2(NULL)

flowchart TB
    key(A eliminar: 87)
    A[[120]] --> B[[87]] & C[[140]]
    B --> D[[43]] & E[[93]]
    subgraph Subárbol izquierdo
        D --> NULL1(NULL) & F[[65]]
        F --> G[[56]] & NULL2(NULL)
    end

flowchart TB
    key(A eliminar: 87)
    A[[120]] --> B[[87]] & C[[140]]
    B --> D[[43]] & E[[93]]
    subgraph Subárbol izquierdo
        D --> NULL1(NULL) & F[[65]]
        F --> G[[56]] & NULL2(NULL)
    end
    F -. el mayor .-> B

flowchart TB
    key(A eliminar: 87)
    A[[120]] --> B[[65]] & C[[140]]
    B --> D[[43]] & E[[93]]
    subgraph Subárbol izquierdo
        D --> NULL(NULL) & G[[56]]
    end

Mostrar implementación

// EN CONSTRUCCIÓN
// COLABORA https://github.com/TeenBiscuits/Pasame-Codigo

Árboles Binarios de Búsqueda Equilibrados (AVL)

Un árbol binario de búsqueda equilibrado es un árbol de búsqueda (redundante ya lo sé) en el que, para cada nodo, se cumple que la diferencia de altura de sus subárboles nunca es mayor que uno (las diferencias son en valor absoluto, intervalo [-1, 1]).

Estos árboles hacen búsquedas muy eficientes, ya que mantienen una altura mínima evitando así los árboles degenerados.

El factor de equilibrio (balance factor) de un nodo se define como la altura de su subárbol derecho menos altura de su subárbol izquierdo. Para ser un AVL debes tener un factor de equilibrio en cada nodo entre [-1, 1].

bf(N) = hNDch - hNIzq

---
title: Árbol AVL Equilibrado
---
flowchart TB
    k(((_-1_))) --> A((_1_)) & B((_0_))
    A --> C((_0_)) & D((_0_))
    D --> F((_0_)) & G((_0_))
    B --> H((_0_)) & I((_0_))

---
title: Árbol ABL No equilibrado
---
flowchart TB
    k(((_-2_))) --> A((_2_)) & B((_0_))
    A --> C(NULL) & D((_0_))
    D --> F((_0_)) & G((_0_))
    B --> H((_0_)) & I((_0_))

Operaciones

Respecto a la especificación del árbol binario de búsqueda ABB solo cambian las funciones de inserción y borrados, que también deben mantener equilibrado el árbol.

Si el árbol está en perfecto equilibrio una inserción o un borrado no romperá el equilibrio. De no estarlo, una inserción o un borrado podría romper el equilibrio.

EqInserción.png

Para solucionar esto debemos emplear rotaciones para restaurar el equilibrio.

Rotaciones para restaurar el equilibrio

Rotaciones simples
- Son aquellas que involucran a dos nodos.
- La rotación left-left (LL) y la rotación right-right (RR).
Rotaciones complejas
- Son aquellas que involucran a tres nodos.
- Tenemos la rotación right-left (RL) y la rotación left-right (LR).