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.
Visita nuestra nueva página web con contenidos actualizados y mucho más.
Estos apuntes también están en: Pásame el Código
tip
Copyright © 2024 Pablo Portas López
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.
Eficiencia del proceso de búsqueda en árboles equilibrados
Si los nodos se añaden en un orden aleatorio habrá que equilibrarlo
Si los nodos se añaden en un orden determinado el árbol degenerará en una lista ordenada
Basándonos en el TAD Árbol definimos las operaciones del árbol de búsqueda a cambiar.
note
Para más información: TAD Árbol y Especificación de un TAD
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 árbolMostrar implementación{...}
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)Mostrar implementación{...}
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 árbolnote
Se deben tener en cuenta los hijos del nodo a borrar, ya que deben continuar en el árbol. Si el nodo tienen dos hijos, se sustituye por el mayor de los hijos menores (subárbol izquierdo).
Mostrar implementación{...}
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].
note
Se denominan AVL en honor a Adelson, Velskii y Landis, que fueron los primeros en proponer este TAD. Wikipedia
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.
Para solucionar estó debemos emplear 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).