Árboles Binarios de Búsqueda (ABB)

 ABB = Árbol binario ordenado según uno o más criterios

 Cada nodo tiene dos hijos:

el subárbol izquierdo es el árbol vacío o es un subárbol que
contiene nodos cuya clave es menor que la suya
el subárbol izquierdo es el árbol vacío o es un subárbol que
contiene nodos cuya clave es mayor que la suya

 ¿Cuál de estos dos árboles binarios de enteros es un ABB?

7 7
4 9 4 9

8 8

Laboratorio
DEI 2003/04 Estructura de Datos Árboles - 1
 Árboles Binarios de Búsqueda (ABB)
 Utilidad
Almacenar estructuras lineales (que normalmente serían
listas) mejorando la complejidad de las búsquedas
 En el caso peor
 En el caso medio
 Motivación: AB no ordenados son de poco interés
La falta de ordenación en un AB hace injustificable una
estructura enlazada de árbol, prefiriéndose una lista

 Problema
un ABB puede llegar a degenerar en una lista
 Solución: equilibrio en ABB

Laboratorio
DEI 2003/04 Estructura de Datos Árboles - 2
 TAD ABB: Descripción
 El nodo se compone de clave, información y referencias a
los subárboles izquierdo y derecho

<arbol>::= <<nulo>> | <nodo>

<nodo>::= <clave> <info> <izq> <der>
<clave>::= <<dato>> {<<dato>>}
<info>::={<<dato>>}
<izq>::=<arbol>
<der>::=<arbol>

 El proceso de inserción es el encargado de garantizar que

se cumple la condición de ABB

Laboratorio
DEI 2003/04 Estructura de Datos Árboles - 3
 TAD ABB: Operaciones
Creación de un árbol crearArbol (nombreArbol)
arbolVacio(nombreArbol)  Booleano
Comprobación del estado
arbolVacio(referenciaNodo)  Booleano
Inserción de nodos insertar(nombreArbol, valorClave, valorInfo)

Borrado de nodos borrar(nombreArbol, valorClave)

Búsqueda de un nodo buscar(nombreArbol, valorClave)referenciaNodo

Recorrido del árbol recorrer(nombreArbol,tipoRecorrido)

clave(referenciaNodo)  Clave
Acceso a los nodos
info(referenciaNodo)  Informacion
izq(referenciaNodo)  enlace
der(referenciaNodo)  enlace
eshoja(referenciaNodo)  Booleano
Modificación de los nodos asignarClaver(referenciaNodo, valorClave)
asignarInfo(referenciaNodo, valorInformacion)
asignarIzq(referenciaNodo, valorEnlace)
Laboratorio asignarDer(referenciaNodo, valorEnlace

DEI 2003/04 Estructura de Datos Árboles - 4

 TAD ABB: ejemplo de inserción
 Insertar 8, 5, 1, 20, 12, 6, 4
8
 Insertar 8
 Insertar 5
5 20
 Insertar 1
 Insertar 20
1 6 12
 Insertar 12
 Insertar 6
4
 Insertar 4

Laboratorio
DEI 2003/04 Estructura de Datos Árboles - 6
 TAD ABB: ejemplo de inserción
 Insertar 1, 4, 5, 6, 8, 12, 20
1
 Insertar 1
 Insertar 4 4

 Insertar 5 5
 Insertar 6
6
 Insertar 8
 Insertar 12 8
 Insertar 20
12

20
Laboratorio
DEI 2003/04 Estructura de Datos Árboles - 7
 TAD ABB: Ejemplo de borrado
 Borrar 8

Sustituir por 6 Sustituir por 12

Laboratorio
DEI 2003/04 Estructura de Datos Árboles - 10
 TAD ABB: ejemplo de borrado
 Borrar 1
 Borrar 20
 Borrar 5

Borrar 1 Borrar 20 Borrar 5

Laboratorio
DEI 2003/04 Estructura de Datos Árboles - 11
 ABB Equilibrados
 Ejemplo de inserción
Insertar 8, 5, 1, 20, 12, 6, 4 Insertar 1, 4, 5, 6, 8, 12, 20

8 1

4
5 20
5
1 6 12
6

4 8

 Árboles degenerados 12
Empeora búsquedas en caso medio
20
Necesidad de equilibrio
Laboratorio
DEI 2003/04 Estructura de Datos Árboles - 12
 ABB equilibrados
 Características de ABB
Ventaja: inserción, borrado y búsqueda  O(n)
n = número de niveles del árbol

Desventaja: se pierde eficiencia cuando n  m y su complejidad se

iguala a la de las listas
m = número de nodos

 Hay que mantener el árbol equilibrado

Equilibrio perfecto
Otros tipos de equilibrio (AVL, árboles rojinegros...)

Laboratorio
DEI 2003/04 Estructura de Datos Árboles - 13
 ABB perfectamente equilibrados
 Equilibrio perfecto
Para cada nodo, el número de nodos del subárbol
izquierdo y el número de nodos del subárbol derecho
difieren como máximo en 1 unidad
con equilibrio perfecto sin equilibrio perfecto

Laboratorio
DEI 2003/04 Estructura de Datos Árboles - 14
 ABB perfectamente equilibrado
 Estudio de Wirth
Suponiendo que todas las claves se buscan con la
misma probabilidad
Cabe esperar una mejora en la longitud del camino
medio de un 39% si el ABB está perfectamente
equilibrado
La mejora puede ser mayor en el caso más
desfavorable
Coste alto de mantener un ABB perfectamente
equilibrado
 La mejora no es suficientemente buena salvo si:
El caso más desfavorable se presenta con asiduidad
Relación (nº accesos)/(nº inserciones) es muy grande
Laboratorio
DEI 2003/04 Estructura de Datos Árboles - 15
 ABB perfectamente equilibrados:
algoritmo
 Desplazar la mitad de los nodos que sobran de un lado al
otro del ABB
 Mantener la condición de ABB al desplazar nodos:
Desplazar a derechas:
1.Introducir la raíz en el subárbol derecho
2. Colocar como raíz el mayor del subárbol izquierdo
3. Repetir 1 y 2 tantas veces como número de nodos a desplazar
Desplazar a izquierdas: (simétrico)
 Operaciones auxiliares
equilibrar(NodoABB actual)
desplazarDerecha(NodoABB actual, int cuantos)
desplazarIzquierda(NodoABB actual, int cuantos)
 Modificar algoritmos de inserción/borrado
haciendo un re-equilibrado tras insertar/borrar, o bien
equilibrando en algún momento
 Re-equilibrado se hace desde arriba hacia abajo
Laboratorio
DEI 2003/04 Estructura de Datos Árboles - 16
 Ejemplo de equilibrado perfecto

Laboratorio
DEI 2003/04 Estructura de Datos Árboles - 17
 ABB equilibrados en altura (AVL)
 ABB equilibrado en altura (AVL)
Para cada uno de sus nodos, las alturas de sus subárboles
izquierdo y derecho difieren como máximo en 1 unidad
ABB AVL: ABB no AVL:

 AVL
Adelson, Velkii & Landis
Formulación menos estricta y costosa que equilibrio perfecto
Ligero deterioro del rendimiento medio de las búsquedas
{ABB perfectamente equilibrados}  {Árboles AVL}
Laboratorio
DEI 2003/04 Estructura de Datos Árboles - 18
 AVL: Definición
 Características de los AVL
Reequilibrado sencillo y eficiente
Longitud del camino medio de búsqueda similar a la de los
árboles perfectamente equilibrados
Búsqueda, inserción y borrado ~ O(log n)
n = número de nodos
 Altura máxima de un AVL
Un AVL de altura h con el mínimo número de nodos se genera
de manera similar a los números de Fibonacci
Árbol de fibonacci:
 El árbol vacío es árbol de fibonacci de altura 0 (A0)
 Un único nodo es árbol de fibonacci de altura 1 (A1)
 Si Ah-1 y Ah-2 son árboles de fibonnacci de alturas h-1 y h-2,
entonces Ah ::= < Ah-1, raíz, Ah-2 > es fibonacci de altura h
 No hay más árboles de fibonacci

Laboratorio
DEI 2003/04 Estructura de Datos Árboles - 19
 AVL: Árboles de Fibonacci

Laboratorio
DEI 2003/04 Estructura de Datos Árboles - 20
 TAD AVL
 Definición
<AVL> ::= <raiz> + {<nodo>}
<raiz> ::= <enlace>
<enlace> ::= (<<ReferenciaNodo>> | NULL)
<nodo> ::= <clave> + <info> + <factorEquilibrio> + <izdo>+<dcho>
<clave> ::= <<dato>>{<<dato>>}
<informacion> ::= {<<dato>>}
<factorEquilibrio> ::= (<<-1>> | <<0>> | <<1>>)

 Operaciones
Las mismas que un ABB, excepto inserción y borrado
 Factor de equilibrio (fe) de un nodo
fe = hd  hi
hd = altura del subárbol derecho
hi = altura del subárbol izquierdo
Laboratorio
DEI 2003/04 Estructura de Datos Árboles - 21
 AVL: el factor de equilibrio
 Valores del factor de equilibrio
Si fe = 0, los subárboles izquierdo y derecho tienen la
misma altura
Si fe = 1, el árbol está equilibrado en altura, pero el
subárbol derecho es un nivel más alto
Si fe = 1, el árbol está equilibrado en altura, pero el
subárbol izquierdo es un nivel más alto
 Cálculo del factor de equilibrio
Recalcular al insertar o borrar
Si fe>2 o fe<2, hay que reequilibrar
Re-equilibrio en inserción
Re-equilibrio en borrado

Laboratorio
DEI 2003/04 Estructura de Datos Árboles - 22
 TAD AVL: inserción
 Si árbol vacío, insertar como raíz con fe=0

 Si árbol no vacío, insertar ordenadamente y

modificar fe del padre:
Si ambas ramas tienen la misma altura (fe=0),
actualizar fe del padre y propagar la variación hacia
arriba

Laboratorio
DEI 2003/04 Estructura de Datos Árboles - 23
 TAD AVL: inserción
 Si árbol no vacío (cont.)
Si no tienen la misma altura y hemos insertado en la
más corta, hacer fe=0 en el padre

Si no tienen la misma altura y hemos insertado en la

más larga, hay que reequilibrar

Laboratorio
DEI 2003/04 Estructura de Datos Árboles - 24
 TAD AVL: rotaciones
 Rotación
I-I simple

 Rotación
D-D simple

Laboratorio
DEI 2003/04 Estructura de Datos Árboles - 25
 TAD AVL: rotaciones
 Rotación I-D doble

Laboratorio
DEI 2003/04 Estructura de Datos Árboles - 26
 TAD AVL: rotaciones
 Rotación D-I doble

Laboratorio
DEI 2003/04 Estructura de Datos Árboles - 27
 TAD AVL: ejemplos de reequilibrado
 Rotación I-I simple

 Rotación D-D
simple

Laboratorio
DEI 2003/04 Estructura de Datos Árboles - 28
 TAD AVL: ejemplos de reequilibrado
 Rotación I-D doble

 Rotación D-I doble

Laboratorio
DEI 2003/04 Estructura de Datos Árboles - 29
 TAD AVL: algoritmo de inserción
1. Insertar en orden en la posición adecuada
2. Variar el factor de equilibrio del padre
3. Si el subárbol correspondiente resulta haber
crecido un nivel, comprobar si hay que
reequilibrar con alguno de los 4 casos
4. Si no, aplicar el paso 2 al padre

Laboratorio
DEI 2003/04 Estructura de Datos Árboles - 30
 TAD AVL: ejercicios de inserción
36
 Insertar secuencia
38, 20, 57, 47, 46 25 50

en el AVL: 16
45

 Insertar 40, 33, 46, 6, 8, 24, 18, 22, 25, 60 en

un AVL vacío
10

8 12
 Aplicar equilibrio
7
perfecto al ABB:
5

3 6

1 4
Laboratorio
DEI 2003/04 Estructura de Datos Árboles - 31
 TAD AVL: borrado
 Localizar el nodo a borrar
Si es nodo terminal, se borra
Si no es terminal, se sustituye por el mayor del
subárbol izquierdo
 Recalcular el fe del padre del nodo borrado o
movido
 Si se produce desequilibrio al borrar un nodo
de...
...la rama izquierda  puede ser necesaria una rotación
D-D simple o D-I doble
...la rama derecha  puede ser necesaria una rotación
I-I simple o I-D doble
(Puede hacer falta más de una rotación en el
camino hasta la raíz)
Laboratorio
DEI 2003/04 Estructura de Datos Árboles - 32
 TAD AVL: borrado por la izquierda
 Borrar el 5
Rotación D-D simple

 Borrar el 6
Rotación D-I doble

Laboratorio
DEI 2003/04 Estructura de Datos Árboles - 33
 TAD AVL: borrado por la derecha
 Borrar el 96
Rotación I-I
simple

 Borrar el 65 Rotación I-D

doble

 Borrar el 67 Rotación I-I

simple

Laboratorio
DEI 2003/04 Estructura de Datos Árboles - 34