eda tema04 4
Post on 22-Dec-2015
27 Views
Preview:
DESCRIPTION
TRANSCRIPT
Estructuras de Datos y AlgoritmosTema 4. Árboles binarios
Iván CantadorDavid Vallet, José R. DorronsoroEscuela Politécnica Superior
Universidad Autónoma de Madrid
1Contenidos
• Árboles
• Árboles binarios
• Árboles binarios de búsqueda
• Árboles AVL
Estructura de Datos y AlgoritmosEscuela Politécnica Superior
Universidad Autónoma de Madrid
2Contenidos
• Árboles
• Árboles binarios
• Árboles binarios de búsqueda
• Árboles AVL
Estructura de Datos y AlgoritmosEscuela Politécnica Superior
Universidad Autónoma de Madrid
3
• Un grafo es una estructura de datos G = (V, R) compuesta de:
• Un conjunto V de vértices (nodos)
• Un conjunto R de ramas (arcos), conexiones entre los vértices
Grafos. Definición
• Un conjunto R de ramas (arcos), conexiones entre los vértices de V
• Ejemplo de grafo (dirigido)
1
32
6
4
Estructura de Datos y AlgoritmosEscuela Politécnica Superior
Universidad Autónoma de Madrid
• V= {1, 2, 3, 4, 5, 6}
• R= {(1,4), (1,5), (1,6), (2,3),…, (5,1), (6,2)}
• Un grafo es una EdD general, muy rica y flexible
5
4
• Un camino de un grafo G = (V, R) es una secuencia de nodos de V en los que cada nodo es adyacente al siguiente mediante un arco de R
Grafos. Caminos
siguiente mediante un arco de R
• Ejemplo
• V= {1, 2, 3, 4, 5, 6}
1
32
6
4
5
Estructura de Datos y AlgoritmosEscuela Politécnica Superior
Universidad Autónoma de Madrid
• V= {1, 2, 3, 4, 5, 6}
• R= {(1,4), (1,5), (1,6), (2,3),…, (5,1), (6,2)}
• Caminos: {1, 6, 2, 3}, {5, 1, 4}, …
5
• Un árbol ordenado con raíz es un grafo tal que:
• Tiene un único nodo, denominado raíz, sin ramas incidentes
• Cada nodo ≠ raíz recibe una sola rama
Árboles. Definición
Cada nodo ≠ raíz recibe una sola rama
• Cualquier nodo es accesible desde la raíz
• Ejemplo
raíz Nodos terminales
(hojas)1
32
45
6
71
2 3 4 5
Estructura de Datos y AlgoritmosEscuela Politécnica Superior
Universidad Autónoma de Madrid
Nodos intermedios
5
8
9
106
7 8
109
6
• Un sub-árbol de un árbol T es un subconjunto de nodos de T conectados mediante ramas de T
• Cada nodo de un árbol T junto con sus hijos da lugar a
Árboles. Sub-árboles
• Cada nodo de un árbol T junto con sus hijos da lugar a nuevo sub-árbol T’
1
2 3 4 5
6
109
2 3 4 5
6
7 8
109
6
7 8
1097 8
Estructura de Datos y AlgoritmosEscuela Politécnica Superior
Universidad Autónoma de Madrid
7 8
109
7
• La altura de un árbol es 1 más la longitud del camino más largo que conecta la raíz a una hoja
• La profundidad (nivel) de un nodo es el número de
Árboles. Altura y profundidad
• La profundidad (nivel) de un nodo es el número de ramas entre el nodo y la raíz
• La profundidad de un árbol es el máximo número de ramas entre la raíz una hoja del árbol (es -1 si el árbol está vacío)
• Ejemplo
T ≡ altura(T) = 1 + 3 = 41
2 3 4 5
Estructura de Datos y AlgoritmosEscuela Politécnica Superior
Universidad Autónoma de Madrid
profundidad(1) = 0
profundidad(5) = 1
profundidad(7) = 3
2 3 4 5
6
7 8
109
8
• Un árbol está equilibrado si para todo nodo el número de niveles de sus sub-árboles no difieren en más de una unidad
Árboles. Árboles equilibrados
unidad
• Un árbol con máximo número k de hijos por nodo está perfectamente equilibrado si todo nodo tiene k hijos
Estructura de Datos y AlgoritmosEscuela Politécnica Superior
Universidad Autónoma de Madrid
Árbol equilibrado Árbol perfectamente equilibrado
9Contenidos
• Árboles
• Árboles binarios
• Árboles binarios de búsqueda
• Árboles AVL
Estructura de Datos y AlgoritmosEscuela Politécnica Superior
Universidad Autónoma de Madrid
10
• Un árbol binario (AB) es un árbol ordenado con raíz tal que:
• cada nodo tiene a lo sumo 2 hijos
Árboles binarios. Definición
• Ejemploraíz raíz
Estructura de Datos y AlgoritmosEscuela Politécnica Superior
Universidad Autónoma de Madrid
hojas
nodos intermedios
hojas
11
• En un AB:
• Todo nodo excepto el raíz tiene un nodo padre
• Todo nodo tiene a lo sumo 2 nodos hijos: hijo izquierdo e hijo
Árboles binarios. Definición
• Todo nodo tiene a lo sumo 2 nodos hijos: hijo izquierdo e hijo derecho
padre de X
X
Estructura de Datos y AlgoritmosEscuela Politécnica Superior
Universidad Autónoma de Madrid
hijo izquierdo
de X
hijo derecho
de X
X
12
• Propiedad recursiva de los AB
• El hijo izquierdo de la raíz forma un nuevo árbol con dicho hijo como raíz
• El hijo derecho de la raíz forma un nuevo árbol con el dicho
Árboles binarios. Definición
El hijo derecho de la raíz forma un nuevo árbol con el dicho hijo como raíz
raíz
sub-árbol izquierdo sub-árbol
derecho sub-árbol derecho
sub-árbol izquierdo
raíz
Estructura de Datos y AlgoritmosEscuela Politécnica Superior
Universidad Autónoma de Madrid
13
• Un árbol se puede recorrer de distintas formas, pero siempre desde la raíz
• Para el recorrido normalmente se usa la propiedad recursiva de los árboles
Árboles binarios. Recorrido
recursiva de los árboles
• Cuando se aplica un algoritmo de visita de árboles se implementa la función "visitar" que puede realizar distintas operaciones sobre cada nodo
• Visitar un nodo puede ser p.e. imprimir el contenido del nodo o liberar su memoria 3
Estructura de Datos y AlgoritmosEscuela Politécnica Superior
Universidad Autónoma de Madrid
1 6
2 5 7
4
14
• Recorridos en profundidad
• preorden, postorden, inorden
Árboles binarios. Recorrido
• preorden, postorden, inorden
• Ejemplo de aplicación (en grafos): encontrar componentes conexas
• Recorrido en achura
• recorrido por nivel
• Ejemplos de aplicación (en grafos): camino más corto entre
Estructura de Datos y AlgoritmosEscuela Politécnica Superior
Universidad Autónoma de Madrid
• Ejemplos de aplicación (en grafos): camino más corto entre dos nodos, crawling Web
15
• Preorden = orden previo
• Desde la raíz y recursivamente:1. Visitamos un nodo n
Árboles binarios. Recorrido en profundidad: preorden
2. Recorremos en orden previo el hijo izquierdo de n
3. Recorremos en orden previo el hijo derecho de n
• Ejemplovisitar = printf del contenido de un nodo
resultado: C A B F E D G C
A F
Estructura de Datos y AlgoritmosEscuela Politécnica Superior
Universidad Autónoma de Madrid
A F
B E G
D
16
• Algoritmo recursivo• Caso base / condición de parada
• Caso general / llamada recursiva
• Pseudocódigo
Árboles binarios. Recorrido en profundidad: preorden
abPrerden(ArbolBinario T) {
3
1 6
2 5 7
4
abPrerden(ArbolBinario T) {
// árbol vacío
si abVacio(T) == TRUE
volver
else
visitar(T) // printf
abPreorden(izq(T))
abPreorden(der(T))
volver
}
Estructura de Datos y AlgoritmosEscuela Politécnica Superior
Universidad Autónoma de Madrid
• Observaciones• Árbol vacío ≡ no Nene nodos
• Árbol de un nodo ≡ un nodo raíz sin hijos
• Asociamos nodo ≡ raíz de un subárbol; úNl para la recursión
}
17
• Postorden = orden posterior
• Desde la raíz y recursivamente:1. Recorremos en orden posterior el hijo izquierdo de n
Árboles binarios. Recorrido en profundidad: postorden
2. Recorremos en orden posterior el hijo derecho de n
3. Visitamos un nodo n
• Ejemplovisitar = printf del contenido de un nodo
resultado: B A D E G F C C
A F
Estructura de Datos y AlgoritmosEscuela Politécnica Superior
Universidad Autónoma de Madrid
A F
B E G
D
18
• Pseudocódigo compacto
Árboles binarios. Recorrido en profundidad: postorden
abPostorden(ArbolBinario T) {
// árbol no vacío
si abVacio(T) == FALSE:
abPostorden(izq(T))
• Pseudocódigo más eficiente
abPostorden(izq(T))
abPostorden(der(T))
visitar(T)
}
abPostorden(ArbolBinario T) {
// árbol no vacío
si abVacio(T) == FALSE:
3
1 6
2 5 7
4
Estructura de Datos y AlgoritmosEscuela Politécnica Superior
Universidad Autónoma de Madrid
si abVacio(T) == FALSE:
si abVacio(izq(T)) == FALSE:
abPostorden(izq(T))
si abVacio(der(T)) == FALSE:
abPostorden(der(T))
visitar(T)
}
19
• Inorden = orden medio
• Desde la raíz y recursivamente:1. Recorremos en orden posterior el hijo izquierdo de n
Árboles binarios. Recorrido en profundidad: inorden
2. Visitamos un nodo n
3. Recorremos en orden posterior el hijo derecho de n
• Ejemplovisitar = printf del contenido de un nodo
resultado: A B C D E F G C
A F
Estructura de Datos y AlgoritmosEscuela Politécnica Superior
Universidad Autónoma de Madrid
A F
B E G
D
20
• Pseudocódigo compacto
Árboles binarios. Recorrido en profundidad: inorden
abInorden(ArbolBinario T) {
// árbol no vacío
si abVacio(T) == FALSE:
abInorden(izq(T)) 3
• Pseudocódigo más eficiente
abInorden(izq(T))
visitar(T)
abInorden(der(T))
}
abInorden(ArbolBinario T) {
// árbol no vacío
si abVacio(T) == FALSE:
3
1 6
2 5 7
4
Estructura de Datos y AlgoritmosEscuela Politécnica Superior
Universidad Autónoma de Madrid
si abVacio(izq(T)) == FALSE:
abInorden(izq(T))
visitar(T)
si abVacio(der(T)) == FALSE:
abInorden(der(T))
}
21
• Recorrido en anchura = recorrido por nivel
• Algoritmo
• Recorre de arriba abajo y de izquierda a derecha
• Nunca recorre un nodo de nivel i sin haber visitado los de nivel
Árboles binarios. Recorrido en anchura
• Nunca recorre un nodo de nivel i sin haber visitado los de nivel i-1
• Implementación mediante el TAD Cola, sin recursividad
• Ejemploresultado: C A F B E G D
C
A F
Estructura de Datos y AlgoritmosEscuela Politécnica Superior
Universidad Autónoma de Madrid
A F
B E G
D
22
• Pseudocódigo
• Recorre de arriba abajo y de izquierda a derecha
• Nunca recorre un nodo de nivel i sin haber visitado los de nivel
Árboles binarios. Recorrido en anchura
• Nunca recorre un nodo de nivel i sin haber visitado los de nivel i -1abAnchura(ArbolBinario T) {
colaInicializar(Q)
colaInsertar(Q, T)
mientras colaVacia(Q) == FALSE:
colaExtraer(Q, T’)
visitar(T’)
para cada hijo H de T’:
Estructura de Datos y AlgoritmosEscuela Politécnica Superior
Universidad Autónoma de Madrid
para cada hijo H de T’:
colaInsertar(Q, H)
}
23
• Ejemplo
Árboles binarios. Recorrido en anchura
abAnchura(ArbolBinario T) {
colaInicializar(Q)
colaInsertar(Q, T)
mientras colaVacia(Q) == FALSE:
C
A F
VISITAR Q
C
C A F
A F B
mientras colaVacia(Q) == FALSE:
colaExtraer(Q, T’)
visitar(T’)
para cada hijo H de T’:
colaInsertar(Q, H)
}
Estructura de Datos y AlgoritmosEscuela Politécnica Superior
Universidad Autónoma de Madrid
A F
B E G
D
F B E G
B E G
E 7 D
G D
D
24
• Un Árbol de Expresión (AdE) es un árbol binario donde:
• Los nodos tienen operadores
Árboles binarios. Árboles de expresión
• Las hojas tienen operandos
• (Todo nodo tiene 2 hijos, i.e. operador sobre dos valores)
*
+ -
B C /A
Estructura de Datos y AlgoritmosEscuela Politécnica Superior
Universidad Autónoma de Madrid
B C /
E
A
D
25
• Los sub-árboles de un AdE son AdE
Árboles binarios. Árboles de expresión
operador
AdEAdE
• Un AdE almacena una expresión (aritmética)*
+ -
B C /A
AdE2AdE1
*
(A+B) -
C (D/E)
*
(A+B) (C-(D/E))
Estructura de Datos y AlgoritmosEscuela Politécnica Superior
Universidad Autónoma de Madrid
EDC (D/E)
((A+B)*(C–(D/E)))
26
• Recorrido en orden previo (preorden)
• Salida: * + A B – C / D E
• Forma prefijo de la expresión
Árboles binarios. Árboles de expresión
*
+ -
B C /A
• Recorrido en orden posterior (postorden)
• Salida: A B + C D E / - *
• Forma posfijo/sufijo de la expresión
• Recorrido en orden medio (inorden)
• “Imprimiendo” paréntesis al comienzo y al final de la llamada
ED
Estructura de Datos y AlgoritmosEscuela Politécnica Superior
Universidad Autónoma de Madrid
• “Imprimiendo” paréntesis al comienzo y al final de la llamada
a cada sub-árbol
• Salida: ((A + B) * (C – (D / E)))
• Forma infija de la expresión
27
• Construcción de un AdE
• El paso de una expresión infija a un AdE es natural
Árboles binarios. Árboles de expresión
*
((A + B) * (C – (D / E)))*
(A + B) (C-(D / E))
*
(A + B) -
C (D / E)*
+ -
Estructura de Datos y AlgoritmosEscuela Politécnica Superior
Universidad Autónoma de Madrid
B C /
E
A
D
28
• Construcción de un AdE
• Basada en la evaluación de expresiones mediante el TAD Pila
• Consistente en la evaluación de una expresión guardando en
Árboles binarios. Árboles de expresión
• Consistente en la evaluación de una expresión guardando en una pila árboles generados para sub-expresiones
• El algoritmo de evaluación más sencillo es el de expresiones sufijo
• Si se tiene una expresión prefijo o infijo, ésta se pasa a sufijo para evaluarla
Estructura de Datos y AlgoritmosEscuela Politécnica Superior
Universidad Autónoma de Madrid
para evaluarla
- (A+B)*(C-D/E) � a sufijo � A B + C D E / - * � evaluación
29
• Ejemplo 1: A B + C D E / - *
Árboles binarios. Árboles de expresión
Símbolo Pila
A, BA B
+
A
+
BA
C, D, E +
BA
B
C D E
Estructura de Datos y AlgoritmosEscuela Politécnica Superior
Universidad Autónoma de Madrid
/ +
BA C
/
ED
30
• Ejemplo 1: A B + C D E / - *
Árboles binarios. Árboles de expresión
-
Símbolo Pila
- +
BA
-
C /
ED
*
+ -
Estructura de Datos y AlgoritmosEscuela Politécnica Superior
Universidad Autónoma de Madrid
*+ -
B C /
E
A
D
31
• Ejemplo 2: (A + B – C) * (D ^ (E / F)) ���� A B + C – D E F / ^ *
Árboles binarios. Árboles de expresión
A, B, +, C +
Símbolo Pila
BA C
+
BA
-
C-, D, E, F, /
D
/
FE
^
Estructura de Datos y AlgoritmosEscuela Politécnica Superior
Universidad Autónoma de Madrid
^
^
D /
E F
+
BA
-
C
32
• Ejemplo 2: (A + B – C) * (D ^ (E / F)) ���� A B + C – D E F / ^ *
Árboles binarios. Árboles de expresión
*
Símbolo Pila
*
+
BA
-
C
^
D /
E F
*
Estructura de Datos y AlgoritmosEscuela Politécnica Superior
Universidad Autónoma de Madrid
33Árboles binarios. Implementación en C
• Estructura de datos de un nodo de un árbol binariotypedef struct _NodoAB {
generic info;
struct _NodoAB *izq;
struct _NodoAB *der;struct _NodoAB *der;
} NodoAB;
#define izq(pnodo) ((pnodo)->izq)
#define der(pnodo) ((pnodo)->der)
#define info(pnodo) ((pnodo)->info)
info
Estructura de Datos y AlgoritmosEscuela Politécnica Superior
Universidad Autónoma de Madrid
derizq
34Árboles binarios. Implementación en C
• Estructura de datos de un árbol binariotypedef NodoAB *ArbolBinario;
// Arbol es el puntero a nodo raíz
// Se puede aplicar izq(pnodo) y der(pnodo) a un tipo árbol
// ArbolBinario* es NodoAB**
3arbolBinario
3
1 6
5
1 6
Estructura de Datos y AlgoritmosEscuela Politécnica Superior
Universidad Autónoma de Madrid
55
35Árboles binarios. Implementación en C
• Funciones de creación y liberación de un nodo de un • Funciones de creación y liberación de un nodo de un árbol binario• NodoAB *abCrearNodo();
// Crea un nuevo nodo e inicializa sus campos
• status abLiberarNodo(NodoAB *pn);
// Libera la memoria de un nodo tras llamar a liberarInfo
Estructura de Datos y AlgoritmosEscuela Politécnica Superior
Universidad Autónoma de Madrid
36Árboles binarios. Implementación en C
NodoAB *abCrearNodo() {
NodoAB *pn = NULL;
pn = malloc(sizeof(NodoAB));
if (!pn) return NULL; if (!pn) return NULL;
izq(pn) = der(pn) = NULL;
return OK;
}
status abLiberarNodo(NodoAB *pn) {
if (!pn) return ERROR;
liberarInfo(info(pn));
free(pn);
Estructura de Datos y AlgoritmosEscuela Politécnica Superior
Universidad Autónoma de Madrid
free(pn);
pn = NULL;
return OK;
}
37Árboles binarios. Implementación en C
• Primitivas del TAD árbol binario• Primitivas del TAD árbol binario• boolean abVacio(ArbolBinario *pa);
// Indica si un árbol está vacío
• status abInicializar(ArbolBinario *pa);
// Inicializa un árbol
• status abLiberar(ArbolBinario *pa);
// Libera la memoria de un árbol llamando a abLiberarNodo
Estructura de Datos y AlgoritmosEscuela Politécnica Superior
Universidad Autónoma de Madrid
38Árboles binarios. Implementación en C
status abInicializar(ArbolBinario *pa) {
if (pa == NULL) return ERROR;
*pa = NULL; *pa = NULL;
return OK;
}
boolean abVacio(ArbolBinario *pa) {
if (*pa == NULL) // Ojo: pa==NULL es ERROR
return TRUE;
else return FALSE;
}
Estructura de Datos y AlgoritmosEscuela Politécnica Superior
Universidad Autónoma de Madrid
status abLiberar(ArbolBinario *pa); // Recorrido postorden
39Árboles binarios. Implementación en Cstatus abLiberar(ArbolBinario *pa) { // Versión con macros
if (!pa) return ERROR;
if (!abVacio(&izq(*pa)) {
abLiberar(&izq(*pa));
}
if (!abVacio(&der(*pa)) {
abLiberar(&der(*pa));abLiberar(&der(*pa));
}
abLiberarNodo(*pa); // visitar es liberar el nodo
return OK;
}
status abLiberar(ArbolBinario *pa) { // Versión sin macros
if (!pa) return ERROR;
if (!abVacio(&((*pa)->izq)) {
abLiberar(&((*pa)->izq));
}
Estructura de Datos y AlgoritmosEscuela Politécnica Superior
Universidad Autónoma de Madrid
}
if (!abVacio(&((*pa)->der)) {
abLiberar(&((*pa)->der));
}
abLiberarNodo(*pa); // visitar es liberar el nodo
return OK;
}
40
25
• Profundidad de un árbol
• T ≡ ∅ profundidad(T)= -1
• T ≡ profundidad(T)= 0
Árboles binarios. Profundidad
25
25
43
T ≡ profundidad(T)= 0
• T ≡ profundidad(T)= 1
• T ≡ profundidad(T)= 3
(la mayor profundidad de todas
25
25
43
Estructura de Datos y AlgoritmosEscuela Politécnica Superior
Universidad Autónoma de Madrid
(la mayor profundidad de todas
las hojas)4312
7 32
29
41
• Cada nivel de profundidad d de un AB puede albergar 2d nodos
Árboles binarios. Profundidad
4
3 6
20= 1
21 = 2
• En total, un árbol de profundidad p completo puede albergar (2p+1–1) nodos
4
3 6
1= 21 – 13 = 22 – 1
7 = 23 – 1
2 5 71 22= 4
Estructura de Datos y AlgoritmosEscuela Politécnica Superior
Universidad Autónoma de Madrid
� profundidad mínima necesaria para albergar n nodos:p = prof(T) = ⌈log2(n + 1)) – 1⌉
3 6
2 5 71
42
• AB casi completo
• Todos los niveles con profundidad d < p están completos, i.e.tienen 2d nodos
• AB completo
Árboles binarios. Profundidad
• AB completo
• Todos los niveles con profundidad d ≤ p están completos, i.e.tienen 2d nodos
• (casi completo y tiene exactamente 2p hojas a profundidad p)
4
completo
4
casi completo
4
no completo
Estructura de Datos y AlgoritmosEscuela Politécnica Superior
Universidad Autónoma de Madrid
4
3 6
2 5 71
4
3 6
71
4
3
1 2
43Contenidos
• Árboles
• Árboles binarios
• Árboles binarios de búsqueda
• Árboles AVL
Estructura de Datos y AlgoritmosEscuela Politécnica Superior
Universidad Autónoma de Madrid
44
• Un Árbol Binario de Búsqueda (ABdB) es un árbol binario T tal que ∀ sub-árbol T’ de T se cumple que
Árboles binarios de búsqueda. Definición
info(izq(T’)) < info(T’) < info(der(T’))
∀
dado un criterio de ordenación de info(T)
info(izq(T’)) < info(T’) < info(der(T’))
3
1 6
2 5 7
Estructura de Datos y AlgoritmosEscuela Politécnica Superior
Universidad Autónoma de Madrid
• Cada subárbol de un ABdB es a su vez un ABdB
4
45
• Recorrido en orden medio de un ABdB
Árboles binarios de búsqueda. Orden medio
Recorrido en orden medio de un ABdB
• Salida => 1 2 3 4 5 6 7
• ¡Listado ordenado de los nodos!
3
1 6
2 5 7
Estructura de Datos y AlgoritmosEscuela Politécnica Superior
Universidad Autónoma de Madrid
2 5 7
4
46
• Creación de ABdB: inserción iterativa de valores en ABdB parciales
• Ejemplo
Árboles binarios de búsqueda. Creación
Ejemplo25 43 12 7 32 29
2525
43
25
4312
25
4312
7
25 25
Estructura de Datos y AlgoritmosEscuela Politécnica Superior
Universidad Autónoma de Madrid
4312
7 32
4312
7 32
29
47
• La función inserta(T, d) que introduce un dato d en un árbol T realiza lo siguiente:
Árboles binarios de búsqueda. Inserción
árbol T realiza lo siguiente:
• Si T está vacío, se crea un nodo con d y se inserta
• Si no, se hace una llamada recursiva a insertar
- Si d < info(a), entonces se ejecuta insertar (izq(T))
- Si d > info(a), entonces se ejecuta insertar (der(T))
- Caso excepcional: si dato d = info(T), se devuelve ERROR o
Estructura de Datos y AlgoritmosEscuela Politécnica Superior
Universidad Autónoma de Madrid
- Caso excepcional: si dato d = info(T), se devuelve ERROR o se ignora devolviendo OK
48
• Pseudocódigo
Árboles binarios de búsqueda. Inserción
status abdbInsertar(ArbolBinario T, dato d)
si abVacio(T) // Caso basesi abVacio(T) // Caso base
T = abCrearNodo()
si (T == NULL) devolver ERROR
info(T) = d
devolver OK
else // Caso general
si info(T) < d
devolver abdbInsertar(izq(T), d)
else
Estructura de Datos y AlgoritmosEscuela Politécnica Superior
Universidad Autónoma de Madrid
else
devolver abdbInsertar(der(t), d)
49
• Código C
Árboles binarios de búsqueda. Inserción
status abdbInsertar(ArbolBinario *pa, generic *d) {
if (pa == NULL) return ERROR;
if (abVacio(pa)) { // Caso base (condición de parada)if (abVacio(pa)) { // Caso base (condición de parada)
*pa = abCrearNodo();
if (*pa == NULL) return ERROR;
info(*pa) = *d;
return OK;
}
else { // Caso general (llamada recursiva)
if (compararInfo(d, info(*pa)) < 0)
return abdbInsertar(&izq(*pa), d);
Estructura de Datos y AlgoritmosEscuela Politécnica Superior
Universidad Autónoma de Madrid
return abdbInsertar(&izq(*pa), d);
else
return abdbInsertar(&der(*pa), d);
}
}
50Árboles binarios de búsqueda. Creación y búsqueda
• Dado un vector de valores representados en una lista, la construcción de su correspondiente ABdB es como sigue:status abdbCrear(ArbolBinario T, Lista L)
st = OK
mientras listaVacia(L) == FALSE && st == OK
• Una vez creado el ABdB
• Recorrer el árbol en orden medio recupera los datos ordenados
mientras listaVacia(L) == FALSE && st == OK
listaExtraerInicio(L, d)
st = abdbInsertar(T, d)
si st == ERROR
abLiberar(T) // Ojo: la lista L no se ha recuperado
devolver st
Estructura de Datos y AlgoritmosEscuela Politécnica Superior
Universidad Autónoma de Madrid
• Recorrer el árbol en orden medio recupera los datos ordenados
• Buscar un dato en el árbol es muy eficiente
- Buscar en una lista desordenada es menos eficiente, pues hay que recorrerla de forma secuencial
51Árboles binarios de búsqueda. Búsqueda
• Búsqueda de un dato, e.g. 32
1: comparar(25, 32)?
• ¿Búsqueda de 33?
25
4312
7 32
29
1: comparar(25, 32)?
2: comparar(43, 32)?
3: comparar(32, 32)!
Estructura de Datos y AlgoritmosEscuela Politécnica Superior
Universidad Autónoma de Madrid
• ¿Búsqueda de 33?
- Se hacen llamadas recursivas hasta llegar a un árbol vacío
52Árboles binarios de búsqueda. Búsqueda
• PseudocódigoArbol abdbBuscar(ArbolBinario T, dato d)
si abVacio(T) == TRUE
devolver NULLdevolver NULL
else si info(T) == d
devolver T
else si d < info(T)
devolver abdbBuscar(izq(T), d)
else
devolver abdbBuscar(der(T), d)
Estructura de Datos y AlgoritmosEscuela Politécnica Superior
Universidad Autónoma de Madrid
• ¿Cuántas comparaciones en promedio se tienen que hacer para encontrar un dato en un ABdB?
53
• Coste (número de accesos/comparaciones) de buscar un dato en un ABdB
• Para un ABdB (casi) completo con profundidad p:
– a lo sumo p accesos
Árboles binarios de búsqueda.Complejidad búsqueda
– a lo sumo p accesos
• Para un ABdB (casi) completo de n nodos:
– a lo sumo tantos accesos como la profundidad del árbol ≡ ⌈ log2(n + 1))–1⌉ ≡ Orden (log(n)) ≡ O(log(n))
Búsqueda secuencial en una lista desordenada de n nodos, a lo sumo n accesos: O(n)
Estructura de Datos y AlgoritmosEscuela Politécnica Superior
Universidad Autónoma de Madrid
O(n)
O(log(n))
54
• Para n elementos, hay que realizar n inserciones• Dado árbol (casi) completo, cada inserción es a lo sumo del orden de la
profundidad actual del árbol ≤ ⌈ log2(n + 1))–1⌉ ≡ orden (log(n)) ≡ O(log(n))
• La creación del árbol es O(n�log(n)), pues involucra n inserciones de orden
Árbolesbinariosdebúsqueda.Complejidad ordenación
⌈ ⌉
• La creación del árbol es O(n�log(n)), pues involucra n inserciones de orden O(log(n))
• Una vez creado el árbol, éste se puede usar para ordenar sus elementos recorriéndolo por orden medio ≡ O(n) � ordenación es O(n�log(n)) + O(n) ≡O(n����log(n))
Ordenación de una lista de nnodos mediante algoritmos como BubbleSort, InsertSort: O(n2)
Estructura de Datos y AlgoritmosEscuela Politécnica Superior
Universidad Autónoma de Madrid
O(n2)
O(n*log(n))
55Árboles binarios de búsqueda. Extracción
• Pseudocódigostatus abdbExtraer(ArbolBinario T, dato d)status abdbExtraer(ArbolBinario T, dato d)
si abVacio(T) == TRUE
devolver ERROR
T’ = abdbBuscar(T, d)
if T’ == NULL
devolver OK
else
devolver abdbReajustar(T’)
Estructura de Datos y AlgoritmosEscuela Politécnica Superior
Universidad Autónoma de Madrid
56Árboles binarios de búsqueda. Extracción
• Reajuste de un (sub-)árbol T’ por la extracción de su raíz
1. La raíz de T’ es hoja
2. La raíz de T’ tiene 1 hijo
3. La raíz de T’ tiene 2 hijos
Estructura de Datos y AlgoritmosEscuela Politécnica Superior
Universidad Autónoma de Madrid
57Árboles binarios de búsqueda. Extracción
• Reajuste de un (sub-)árbol T’ por la extracción de su raíz
1. La raíz de T’ es hoja: reajustar puntero del padre de (la raíz
de) T’ a NULL, eliminar T’
2. La raíz de T’ tiene 1 hijo
3. La raíz de T’ tiene 2 hijos
Ejemplo: abdbExtraer(T, 2)
3
1 6
3
1 6
T
Estructura de Datos y AlgoritmosEscuela Politécnica Superior
Universidad Autónoma de Madrid
1 6
2 5 7
4
T’
1 6
5 7
4
58Árboles binarios de búsqueda. Extracción
• Reajuste de un (sub-)árbol T’ por la extracción de su raíz
1. La raíz de T’ es hoja
2. La raíz de T’ tiene 1 hijo: reajustar puntero del padre de T’ al hijo de T’, eliminar de T’
3. La raíz de T’ tiene 2 hijos
Ejemplo: abdbExtraer(T, 1)
3
1 6
T
T’
3
2 6
Estructura de Datos y AlgoritmosEscuela Politécnica Superior
Universidad Autónoma de Madrid
1 6
2 5 7
4
2 6
5 7
4
59Árboles binarios de búsqueda. Extracción
• Reajuste de un (sub-)árbol T’ por la extracción de su raíz
1. La raíz de T’ es hoja
2. La raíz de T’ tiene 1 hijo
3. La raíz de T’ tiene 2 hijos: buscar “sucesor” de T’, guardar 3. La raíz de T’ tiene 2 hijos: buscar “sucesor” de T’, guardar info del sucesor en T’, extraer sucesor
Ejemplo: abdbExtraer(T, 3)
3
1 6
T’
3
1 6
T
4
1 6
El sucesor de T’ se obtiene:
1. Bajando a la derecha de T’ un nivel
2. Bajando a continuación a la izquierda
hasta el último nivel (nodo hoja)
Estructura de Datos y AlgoritmosEscuela Politécnica Superior
Universidad Autónoma de Madrid
1 6
2 5 7
4
1 6
5 7
4
1 6
5 7
sucesor de T’
2 2
60
• Problema de ABdB: árboles no equilibradosL = {1,2,3,4,5,6}
abdbCrear(T, L)
Árboles binarios de búsqueda.Árboles no equilibrados
1
2
3
4
5
6
Estructura de Datos y AlgoritmosEscuela Politécnica Superior
Universidad Autónoma de Madrid
• El acceso ya no es O(log(n)), sino O(n), por lo que:
• Coste de la búsqueda: O(n�log(n)) � O(n)
• Coste de la ordenación: O(n) � O(n2)
61Árboles binarios de búsqueda.Árboles no equilibrados
• ¿Cómo crear ABdB equilibrados?
• Mediante el algoritmo AVL
Estructura de Datos y AlgoritmosEscuela Politécnica Superior
Universidad Autónoma de Madrid
62Contenidos
• Árboles
• Árboles binarios
• Árboles binarios de búsqueda
• Árboles AVL
Estructura de Datos y AlgoritmosEscuela Politécnica Superior
Universidad Autónoma de Madrid
63Árboles AVL. Definición
• Factor de equilibrio de un árbol binario Tfe(T)=profundidad(izq(T))–profundidad(der(T))fe(T)=profundidad(izq(T))–profundidad(der(T))
2
1 5
4 6
fe(2)=-2
fe(5)=1
fe(6)=0
fe(4)=1
fe(1)=0
Estructura de Datos y AlgoritmosEscuela Politécnica Superior
Universidad Autónoma de Madrid
3fe(3)=0
fe(4)=1
64Árboles AVL. Definición
• Árbol AVL (Adelson-Velskii y Landis)
• Un árbol AVL es un ABdB* T en el que todo sub-árbol T’ cumple • Un árbol AVL es un ABdB* T en el que todo sub-árbol T’ cumple que:
• Proposición:
- Si T es un árbol AVL con N nodos, entonces:
fe(T’)=0, fe(T’)=1 ó fe(T’)=-1
Estructura de Datos y AlgoritmosEscuela Politécnica Superior
Universidad Autónoma de Madrid
- Si T es un árbol AVL con N nodos, entonces:
profundidad(T) = O(log2N)
* La definición de AVL se puede aplicar a cualquier árbol binario, pero en la asignatura seusará con árboles binarios de búsqueda
65Árboles AVL. Rotaciones
• El algoritmo AVL establece “rotaciones” de 2 nodos A y B en un árbol binario para tratar ciertos “desequilibrios”• RI = rotación izquierda
• RD = rotación derecha
• RID = rotación izquierda + rotación derecha• RID = rotación izquierda + rotación derecha
• RDI = rotación derecha + rotación izquierda
fe(A) fe(B) Rotación
-2 -1 RI(B)
2 1 RD(B)
A
A
B
B
-2
-1
2
1
A
A
B
B
-2
-1
2
1B
B
A
A
Estructura de Datos y AlgoritmosEscuela Politécnica Superior
Universidad Autónoma de Madrid
-2 1 RDI(izq(B))
2 -1 RID(der(B))
A
A
B
B
-2
1
2
-1
A
A
B
B
-2
1
2
-1
A
A
B
B
BA
BA
66Árboles AVL. Construcción
• Construcción de un AVL
• Tras realizar una inserción de ABdB, se comprueba la condición de AVL para realizar o no rotación
Estructura de Datos y AlgoritmosEscuela Politécnica Superior
Universidad Autónoma de Madrid
67Árboles AVL. Construcción
• Ejemplo: crear el árbol AVL para la lista[1, 2, 3, 4, 5, 6, 7, 15, 14, 13, 12, 11, 10, 9, 8]
1Inserción de 1 0
2
1Inserción de 2 -1
0
Estructura de Datos y AlgoritmosEscuela Politécnica Superior
Universidad Autónoma de Madrid
3
2
1Inserción de 3
RI(2)
-2
-1
01 3
2
00
0
68Árboles AVL. Construcción
• Ejemplo: crear el árbol AVL para la lista[1, 2, 3, 4, 5, 6, 7, 15, 14, 13, 12, 11, 10, 9, 8]
4
1 3
2Inserción de 4 -1
-10
04
4
5
1 3
2Inserción de 5
RI(4)
-2
-20
-1
03 5
1 4
2
-1
0
0
0
0
Estructura de Datos y AlgoritmosEscuela Politécnica Superior
Universidad Autónoma de Madrid
3 5
6
1 4
2Inserción de 6
RI(4)
-2
-1
0
0
-1
01 3 6
2 5
4
0
-10
0 00
69Árboles AVL. Construcción
• Ejemplo: crear el árbol AVL para la lista[1, 2, 3, 4, 5, 6, 7, 15, 14, 13, 12, 11, 10, 9, 8]
1 3 6
2 5
4Inserción de 7
RI(6)
-1
-20
0 -101 3 5 7
2 6
4
0
0
0
0
0 001 3 6 1 3 5 7
1 3 5 7
15
2 6
4Inserción de 15 -1
-1
0
0
0 -1
0
0
7
0
Inserción de 14 -2 -2 -1
Estructura de Datos y AlgoritmosEscuela Politécnica Superior
Universidad Autónoma de Madrid
1 3 5 7
15
2 6
4Inserción de 14
RDI(14)
-2
-2
0
0
0 -2
1
01 3 5 7
14
2 6
4
-2
-2
0
0
0 -2
-1
01 3 5 14
157
2 6
4
-1
-1
0
0
0 0
0 0
0
14
015
0
70Árboles AVL. Construcción
• Ejemplo: crear el árbol AVL para la lista[1, 2, 3, 4, 5, 6, 7, 15, 14, 13, 12, 11, 10, 9, 8]
1 3 5 14
2 6
4Inserción de 13
RDI(7)
-2
-2
0
0
0 1
1 0
01 3 5 7
2 6
4
-2
-2
0
0
0 -2
0
01 3 6 14
2 7
4
-1
0
1
0
0 0
0 0 0
01 3 5 14
157
1 01 3 5 7
14
01 3 6
5
14
1513
0 0 0
1 3 6 14
1513
2 7
4Inserción de 12
RI(7)
-2
-1
1
0
0 1
1 0
02
31
6 13
12
15
4 14
7
0
1
1
0
0
0
0
0 0
1
13
015
013
0
12
05
05
0
Estructura de Datos y AlgoritmosEscuela Politécnica Superior
Universidad Autónoma de Madrid
2
31
6
5
13
12
15
4 14
7Inserción de 11
RD(12)
-1
2
2
0
0
0
0
0 0 1
12
31
6
5
12
1311
15
4 14
7
0
-1
0
0
0
0
0
0 0 0 0
-1
12
11
0
71Árboles AVL. Construcción
• Ejemplo: crear el árbol AVL para la lista[1, 2, 3, 4, 5, 6, 7, 15, 14, 13, 12, 11, 10, 9, 8]
Inserción de 10
2 6 12 15
4 14
7
-1
2
1
0
0 01RD(12)
2 6 11 14
4 12
7
0
0
1
0
0 01
Inserción de 9
2
31
6
5
12
1311
15
0 0 0 1 0
10
0
2
31
6
5
11
10
14
0 0 0 015
013
0
2
31
6
5
11
10
14
4 12
7
-1
1
2
0
0
0
0
0 0 1
1
15
013
0
9
0
RD(10)
2
31
6
5
10
9
14
4 12
7
0
0
0
0
0
0
0
0 0 0
1
15
013
011
0
Estructura de Datos y AlgoritmosEscuela Politécnica Superior
Universidad Autónoma de Madrid
Inserción de 8
9
2
31
6
5
10
9
14
4 12
7
-1
1
1
0
0
0
0
0 0 1
1
15
013
011
0
8
0
top related