Tema 7 y 8 - Árboles Binarios de Búsqueda ABB y Equilibrados AVL
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
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.
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
Si los nodos se añaden en un orden determinado el árbol degenerará en una lista ordenada
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// 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)// 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// 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].
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.
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).