Pro2324 Help

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

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 estadísticas en operaciones de inserción y eliminación.

    • estructuras dinámicas en la operación de búsqueda.

Árbol binario de búsqueda (ABB)
k
claves < k
claves > k
Árbol binario de búsqueda (ABB)

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

    Árbol sin equilibrar
    0
    1
    2
    4
    7
    8
    6
    NULL
    Árbol sin equilibrar
  • Si los nodos se añaden en un orden determinado el árbol degenerará en una lista ordenada

    Árbol degenerado en lista
    1
    2
    3
    4
    NULL
    NULL
    NULL
    Árbol degenerado en lista

Operaciones

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

Generadoras



  • 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

    25 < 30
    25 > 20
    Key: 25
    30
    20
    40
    NULL
    25
    // EN CONSTRUCCIÓN // COLABORA https://github.com/TeenBiscuits/Pro2324

Observadoras





  • 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)

    25 < 30
    25 > 20
    Key: 25
    30
    20
    40
    15
    25
    35
    45
    // EN CONSTRUCCIÓN // COLABORA https://github.com/TeenBiscuits/Pro2324

Destructoras

  • 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

    A eliminar: 87
    120
    87
    140
    43
    93
    NULL
    65
    56
    NULL
    Subárbol izquierdo
    NULL
    65
    43
    56
    NULL
    A eliminar: 87
    120
    87
    140
    93
    Subárbol izquierdo
    el mayor
    NULL
    65
    43
    56
    NULL
    A eliminar: 87
    120
    87
    140
    93
    Subárbol izquierdo
    NULL
    56
    43
    A eliminar: 87
    120
    65
    140
    93
    // EN CONSTRUCCIÓN // COLABORA https://github.com/TeenBiscuits/Pro2324

Á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].

Árbol AVL Equilibrado
_-1_
_1_
_0_
_0_
_0_
_0_
_0_
_0_
_0_
Árbol AVL Equilibrado
Árbol ABL No equilibrado
_-2_
_2_
_0_
NULL
_0_
_0_
_0_
_0_
_0_
Árbol ABL No equilibrado

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 estó 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).

Last modified: 18 July 2024