Download Arbol - Buap

El tipo de dato Arbol

Aparecen estructuras de tipo árbol en:
– Sist. Op: Sistema de ficheros (Arbol de directorios)
– Compiladores, proc. textos, algoritmos de búsqueda

Elementos:
– Nodos
– Conexiones (dirigidas) entre pares de nodos
– Un nodo particular: Raíz
– Cada nodo (excepto raíz) está conectado al menos
con otro (padre). Relación padre-hijo.
Arboles
M.C. José Andrés Vázquez
FCC/BUAP
1
Arboles. Conceptos





Un único camino conduce de la raíz a cada nodo
Longitud del camino: Número de conexiones a atravesar
Nodos sin hijos: Hojas (leaves)
Arbol con N nodos  N-1 conexiones entre nodos
Profundidad de un nodo:
– Longitud del camino raíz  nodo

Altura de un nodo:
– Longitud del camino desde el nodo a su hoja más profunda

Hermanos: Nodos con el mismo padre (siblings)
Arboles
M.C. José Andrés Vázquez
FCC/BUAP
2
Arboles. Conceptos (II)

Relación antepasado (u) / descendiente (v):
– Si hay camino de u a v.

Tamaño de un nodo:
– Número de descendientes (incluyendo al nodo)

Arbol (def. recursiva):
– o es vacío,
– o consiste en una raíz y cero o más (sub)árboles no
vacíos A1..Ak conectados a la raíz
Arboles
M.C. José Andrés Vázquez
FCC/BUAP
3
Arboles. Implementación
1.- Cada nodo contiene:
– Referencias a todos sus hijos
– Datos almacenados en el nodo
– Problema: Número de hijos desconocido
2.- Cada nodo:
– Lista con sus hijos
– Referencia a los datos contenidos
– Referencia a su nodo hermano
– Representación "first child / next sibling"
Arboles
M.C. José Andrés Vázquez
FCC/BUAP
4
Arboles. Implementación (II)
nodoRaiz
sigHermano null
primerHijo
null
null
null
Arboles
null
null
null
M.C. José Andrés Vázquez
FCC/BUAP
null
null
null
5
Arbol N-ario

Ningún nodo puede tener más de N hijos
 El más utilizado: Binario, 2 hijos (left, right)
 Def. recursiva (Arbol binario)
– ... o es vacío
– ... o tiene raíz, árbol derecho, árbol izquierdo

Implementación:
– Conocido el número de hijos. 2 referencias
Arboles
M.C. José Andrés Vázquez
FCC/BUAP
6
Arboles binarios

Arbol binario completo (complete binary tree)
– Todas las hojas tiene la misma profundidad
– El resto de nodos (no terminales) tienen 2 hijos

Arbol binario cuasi-completo (cusi-complete
binary tree)
– Cada nivel (excepto el más profundo) debe contener
todos sus posibles nodos
– En el nivel más profundo, los nodos están lo más a
la izquierda que sea posible
Arboles
M.C. José Andrés Vázquez
FCC/BUAP
7
Arboles binarios: Expresiones

Un nodo terminal representa un operando
 El resto de los nodos representan operadores
(binarios)
6 + ((7 - 3) * 5)
+
 Evaluación de la expresión:
– Evaluación de los subárboles
(recursivamente)
– Aplicación del operador a los
valores obtenidos
6
-
7
Arboles
M.C. José Andrés Vázquez
FCC/BUAP
*
5
3
8
Arboles y recursividad

El tipo árbol se define recursivamente
 Muchas rutinas para manejo de árboles se
implementan fácilmente de forma recursiva
public class NodoBinario
{
Object dato;
NodoBinario left;
NodoBinario right;
public NodoBinario (Object elemento)
{
dato = elemento;
left = null; right = null;
}
// Métodos...
}
Arboles
M.C. José Andrés Vázquez
FCC/BUAP
dato
left
right
9
Arboles y recursividad (II)
public NodoBinario duplicar()
{
NodoBinario root = new NodoBinario(dato);
if (left != null) root.left = left.duplicar();
if (right != null) root.right = right.duplicar();
return root;
}
size = 1
public static int size (NodoBinario nodo)
// Tamaño del árbol que tiene a ese nodo como raíz
{
if (nodo == null)
return 0;
else
return 1 + size(nodo.left) + size (nodo.right);
}
Arboles
M.C. José Andrés Vázquez
FCC/BUAP
size
left
size
right
10
Arboles y recursividad (III)
public static int altura(NodoBinario nodo)
// Un árbol con un único nodo tiene altura = 0
// El nodo tiene que ser != null. Si no, no está definida su altura
{
int altDerecha = (nodo.right == null ? 0 : 1+altura(nodo.right));
int altIzquierda = (nodo.left == null ? 0 : 1+altura(nodo.left));
return Math.max (altDerecha, altIzquierda);
}
altura = 0
public static int altura(NodoBinario nodo)
// Otra forma de hacer lo mismo...
{
if (nodo == null) return -1;
else
return 1 + Math.max(altura(nodo.left),
altura(nodo.right));
}
Arboles
M.C. José Andrés Vázquez
FCC/BUAP
1 + ...
1 + ...
altura
Izquierda
altura
Derecha
11
Recorrido de árboles

Recorrido:
– Acceso a todos los nodos de un árbol
– Ej: Para realizar una operación en cada nodo

Fácil implementación mediante recursividad
 Tipos de recorrido:
– Según el orden en que se "visitan" los nodos
– duplicar(): Recorrido preorder
– size(), altura(): Recorridos postorder
– Obtención de expresiones algebraicas: inorder
Arboles
M.C. José Andrés Vázquez
FCC/BUAP
12
Recorrido "Preorden"

Recorrido preorder:
1.- Nodo raíz
2.- Subárbol left en preorden
3.- Subárbol right en preorden
Preorden
1
// en la clase NodoBinario...
public void mostrarPreorden()
{
System.out.println(dato);
if (left != null)
left.mostrarPreorden();
if (right != null)
right.mostrarPreorden();
}
Arboles
2
M.C. José Andrés Vázquez
FCC/BUAP
3
4
6
5
7
13
Recorrido "Inorden"

Recorrido inorder:
1.- Subárbol left en inorden
2.- Nodo raíz
3.- Subárbol right en inorden
Inorden
2
// ...NodoBinario...
public void mostrarInorden()
{
if (left != null)
left.mostrarInorden();
System.out.println(dato);
if (right != null)
right.mostrarInorden();
}
Arboles
1
M.C. José Andrés Vázquez
FCC/BUAP
5
3
7
4
6
14
Recorrido "Postorden"

Recorrido postorder:
1.- Subárbol left en postorden
2.- Subárbol right en postorden
3.- Nodo raíz
Postorden
7
// ...NodoBinario...
public void mostrarPostorden()
{
if (left != null)
left.mostrarPostorden();
if (right != null)
right.mostrarPostorden();
System.out.println(dato);
}
Arboles
1
M.C. José Andrés Vázquez
FCC/BUAP
6
3
5
2
4
15
Recorrido de árboles. Ejercicio
A
B
C
D
F
E
H
Preorden: ...
Inorden: ...
Postorden: ...
I
G
J
K
L
Arboles
M.C. José Andrés Vázquez
FCC/BUAP
M
16
Recorrido por niveles

Se recorren los nodos por niveles de profundidad
– Dentro de cada nivel, de izquierda a derecha
– Recorrido en anchura (breadth-first)

Implementación: Utilizando una Cola
– Almaceno en la cola los nodos que deben ser visitados
– Al visitar un nodo, sus hijos se colocan en la cola
– La cola puede llegar a contener muchos nodos

¿Qué sucede usando Pila en lugar de Cola?
– ¿recorrido en preorden? ¿Algún cambio?
Arboles
M.C. José Andrés Vázquez
FCC/BUAP
17
Recorrido por niveles (II)
// ...NodoBinario...
public static void mostrarPorNiveles(NodoBinario n)
{
Cola q = new Cola();
q.ponerElemento(n);
while(!q.estaVacia())
{
NodoBinario elemento =
(NodoBinario) q.extraerElemento();
System.out.println(elemento.dato);
if (elemento.left != null)
q.ponerElemento(elemento.left);
if (elemento.right != null)
q.ponerElemento(elemento.right);
}
}
Arboles
M.C. José Andrés Vázquez
FCC/BUAP
18
Arboles binarios de búsqueda

Arboles binarios + Almacenan datos con clave
– Clave: Relación de orden total (...¿duplicados?)

Características:
– La raíz tiene un valor de clave mayor que la de
cualquier elemento del subárbol de la izquierda
– La raíz tiene una clave menor que cualquiera del
subárbol de la derecha
– Ambos subárboles (izquierda y derecha) son
igualmente Arboles Binarios de Búsqueda
Arboles
M.C. José Andrés Vázquez
FCC/BUAP
19
Arboles binarios de búsqueda
(II)
6
2
12
1
8
4
3
5
13
7
10
9
11

Un recorrido inorder muestra los datos ordenados
 ¿Cuál es el coste de una búsqueda? (Ej. 9)
Arboles
M.C. José Andrés Vázquez
FCC/BUAP
20
Arboles binarios de búsqueda
(III)

Operaciones de búsqueda:
– Como búsqueda dicotómica en vectores ordenados

Eficiencia en las operaciones:
– Estructuras lineales ð coste de operaciones: O(N)
– La mayor parte de las operaciones son O(log N)
– Algunas se comportan como O(N) en el peor caso

Permite las operaciones habituales:
– Inserción, búsqueda y borrado
Arboles
M.C. José Andrés Vázquez
FCC/BUAP
21
Búsqueda en ABB
public class ArbolBinarioBusq
{
protected NodoBinarioBusq raiz;
public Object buscar(int claveBuscar){
return buscar(claveBuscar, raiz);}
private static Object buscar(int claveBuscar, NodoBinario n)
// Devuelve: dato contenido en el nodo con esa clave, o null
{
NodoBinarioBusq nodo = (NodoBinarioBusq) n;
if (nodo == null) return null;
if (nodo.clave > claveBuscar)
NodoBinarioBusq
return buscar(claveBuscar, nodo.left);
clave
if (nodo.clave < claveBuscar)
dato
return buscar(claveBuscar, nodo.right);
// Solo queda el caso (nodo.clave == claveBuscar)
left
right
return nodo.dato;
}...
}
Arboles
M.C. José Andrés Vázquez
FCC/BUAP
22
Búsqueda en ABB (II)
// Dato almacenado con la clave menor. Recursivo.
public Object buscarMin(){return buscarMin(raiz);}
private static Object buscarMin(NodoBinario nodo)
{
if (nodo == null) return null;
if (nodo.left == null) return nodo.dato;
return buscarMin(nodo.left);
}
// Dato almacenado con la clave mayor. Iterativo.
public Object buscarMax()
{
NodoBinario nodo = raiz;
if (nodo != null)
{
while (nodo.right != null)
1
nodo = nodo.right;
return nodo.dato;
}
else return null;
}
Arboles
M.C. José Andrés Vázquez
FCC/BUAP
raiz
2
4
3
5
23
Inserción en ABB

Algoritmo recursivo muy simple:
– Si el árbol está vacío, colocar como nuevo elemento
– Si no está vacío: comparar con la clave de la raíz
 Insertar (recursividad) en el subárbol izquierdo o derecho
– Si ya hay un nodo con ese valor: ¡Error!

Ejercicio:
insertar(Object dato, int clave)

¡Cuidado con las modificaciones en los nodos!
Arboles
M.C. José Andrés Vázquez
FCC/BUAP
24
Inserción en ABB (II)
public void insertar(Object dato, int clave){
raiz = insertar(dato, clave, raiz);}
private static NodoBinarioBusq insertar(Object dato, int clave,
NodoBinarioBusq nodo)
// Devuelve el estado en que queda el nodo tras insertar
{
if (nodo == null) nodo = new NodoBinarioBusq(dato, clave);
else if (clave < nodo.clave)
nodo.left = insertar(dato, clave,
(NodoBinarioBusq) nodo.left);
else if (clave > nodo.clave)
nodo.right = insertar(dato, clave,
(NodoBinarioBusq) nodo.right);
else System.out.println("Duplicado. Error al insertar!");
return nodo;
}

6
2
8
1
4
3
insertar (..., 5)
6
2
1
8
4
3
¿Es necesario devolver un "nodo"?
 Modificar para tratamiento de claves duplicadas
Arboles
M.C. José Andrés Vázquez
FCC/BUAP
5
25
Borrado en ABB

La operación más compleja.
– Puede afectar otros nodos

Posibilidades según los hijos del nodo a borrar:
– Borrado de un nodo sin hijos
 Se pone a null la referencia de su padre.
– Nodo con un único hijo
 El subárbol hijo se cuelga del padre del nodo a borrar
– Nodo con 2 hijos
 Las modificaciones afectan a otros nodos. No trivial
Arboles
M.C. José Andrés Vázquez
FCC/BUAP
26
Borrado en ABB (II)
6
2
6
8
1
4
2
borrar(8)  ok

8
1
3
6
4
3
borrar(4)  Su único
subárbol hijo ocupa su
posición
2
8
1
4
3
borrar(2)  ¿Cómo?
Veamos un caso más sencillo:
– Borrado del dato con clave mínima
Arboles
M.C. José Andrés Vázquez
FCC/BUAP
27
Borrado en ABB (III)

Borrado del dato con clave mínima:
borrarMin()
– Posición conocida (extremo izquierdo)
– No tiene más de 1 hijo
6
2
8
1
4
// ... en la clase ArbolBinarioBusq
3
public void borrarMin(){
raiz = (NodoBinarioBusq) borrarMin(raiz);
}
borrarMin()
private static NodoBinario borrarMin(NodoBinario nodo)
{
if (nodo == null)
System.out.println("Arbol vacio. Error al borrar");
else if (nodo.left != null)
nodo.left = borrarMin(nodo.left);
else nodo = nodo.right;
return nodo;
}
Arboles
M.C. José Andrés Vázquez
FCC/BUAP
6
3
1
8
4
2
28
Borrado en ABB (IV)

Caso general de borrado:
– Como borrarMin(), salvo nodos con 2 hijos

La posición del nodo borrado la deberá ocupar
– El nodo mayor del subárbol izquierdo
– o el nodo menor del subárbol derecho

Operaciones de buscar y eliminar el nodo de
menor (o mayor) clave ya conocidas
Arboles
M.C. José Andrés Vázquez
FCC/BUAP
29
Borrado en ABB (V)
public void borrar(int claveBorrar){
raiz = (NodoBinarioBusq) borrar(claveBorrar, raiz);}
private static NodoBinario borrar(int claveBorrar, NodoBinario nodo)
{
if (nodo == null)
System.out.println("Arbol vacio. Error al borrar");
else if (claveBorrar < getClave(nodo))
nodo.left = borrar(claveBorrar, nodo.left);
else if (claveBorrar > getClave(nodo))
nodo.right = borrar(claveBorrar, nodo.right);
else if ((nodo.left != null) && (nodo.right != null))
{
nodo.clave = claveMin(nodo.right);
nodo.dato = buscarMin(nodo.right);
nodo.right = borrarMin(nodo.right);
}
else nodo = (nodo.left != null) ? nodo.left : nodo.right;
return nodo;
}
private static int getClave(NodoBinario nodo){
return ((NodoBinarioBusq) nodo).clave;}
Arboles
M.C. José Andrés Vázquez
FCC/BUAP
30
Complejidad y eficiencia

El coste de las operaciones depende de la
profundidad del árbol
– ...de la profundidad del nodo en que se realiza la
operación

Profundidad del árbol: O(log N)
– ...si los nodos están "distribuidos uniformemente"

Problemas:
– Algunas operaciones no contribuyen a mantener esa
uniformidad (Ej: Borrado)
Arboles
M.C. José Andrés Vázquez
FCC/BUAP
31
Complejidad y eficiencia (II)

Borrado (nodo con 2 hijos)
– Siempre elimina elementos del subárbol derecho
– Borrados en un subárbol aleatorio ¿Es una solución?

Casos particularmente malos:
– Inserción de datos preordenados...
– Todos los nodos sin rama izquierda (o derecha)

Mantener equilibrio:
– Impedir que se alcancen profundidades innecesarias
Arboles
M.C. José Andrés Vázquez
FCC/BUAP
32