arboles m.c. josé andrés vázquez fcc/buap 1 el tipo de dato arbol aparecen estructuras de tipo...

Arboles M.C. José Andrés Vázquez FCC/BUAP

1

El tipo de dato ArbolAparecen 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.


2

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)


3

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


4

Arboles. Implementación1.- 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"


5

Arboles. Implementación (II)

sigHermanoprimerHijo

null

nullnull

nullnull null null null

nullnull

nodoRaiz


6

Arbol N-arioNingún nodo puede tener más de N hijosEl 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


7

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


8

Arboles binarios: ExpresionesUn nodo terminal representa un operandoEl resto de los nodos representan operadores

(binarios)+

6 + ((7 - 3) * 5)

6

Evaluación de la expresión:– Evaluación de los subárboles

(recursivamente)– Aplicación del operador a los

valores obtenidos

*

5-

37


9

El tipo árbol se define recursivamenteMuchas rutinas para manejo de árboles se

implementan fácilmente de forma recursivapublic class NodoBinario{ Object dato; NodoBinario left; NodoBinario right; public NodoBinario (Object elemento) { dato = elemento; left = null; right = null; } // Métodos...}

Arboles y recursividad

dato

rightleft


10

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;}

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);}

size left

size right

size = 1


11

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);}

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));}

altura Izquierda

altura Derecha

altura = 0

1 + ...1 + ...


12

Recorrido de árbolesRecorrido:

– Acceso a todos los nodos de un árbol– Ej: Para realizar una operación en cada nodo

Fácil implementación mediante recursividadTipos 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


13

Recorrido "Preorden"Recorrido preorder:

1.- Nodo raíz

2.- Subárbol left en preorden

3.- Subárbol right en preorden1

Preorden

2 3

64

5 7

// en la clase NodoBinario...public void mostrarPreorden(){ System.out.println(dato); if (left != null) left.mostrarPreorden(); if (right != null) right.mostrarPreorden();}


14

Recorrido "Inorden"Recorrido inorder:

1.- Subárbol left en inorden

2.- Nodo raíz

3.- Subárbol right en inorden2

Inorden

1 5

73

4 6

// ...NodoBinario...public void mostrarInorden(){ if (left != null) left.mostrarInorden(); System.out.println(dato); if (right != null) right.mostrarInorden();}


15

Recorrido "Postorden"Recorrido postorder:

1.- Subárbol left en postorden

2.- Subárbol right en postorden

3.- Nodo raíz7

Postorden

1 6

53

2 4

// ...NodoBinario...public void mostrarPostorden(){ if (left != null) left.mostrarPostorden(); if (right != null) right.mostrarPostorden(); System.out.println(dato);}


16

Recorrido de árboles. Ejercicio

Preorden: ...Inorden: ...Postorden: ...

A

B C

GF

KJ

ML

ED

IH


17

Recorrido por nivelesSe 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?


18

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); } }


19

Arboles binarios de búsquedaArboles 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


20

Arboles binarios de búsqueda (II)

Un recorrido inorder muestra los datos ordenados ¿Cuál es el coste de una búsqueda? (Ej. 9)

6

2 12

138

107

119

41

53


21

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


22

Búsqueda en ABBpublic 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) return buscar(claveBuscar, nodo.left); if (nodo.clave < claveBuscar) return buscar(claveBuscar, nodo.right); // Solo queda el caso (nodo.clave == claveBuscar) return nodo.dato; }...}

dato

rightleft

clave

NodoBinarioBusq


23

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) nodo = nodo.right; return nodo.dato; } else return null; }

2

41

53

raiz


24

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!


25

Inserción en ABB (II)

¿Es necesario devolver un "nodo"?Modificar para tratamiento de claves duplicadas

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;}

2

41

53

6

8

2

41

3

6

8

insertar (..., 5)


26

Borrado en ABBLa operación más compleja.

– Puede afectar otros nodosPosibilidades 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


27

Borrado en ABB (II)

Veamos un caso más sencillo:– Borrado del dato con clave mínima

2

41

3

6

8 2

41

3

6

8 2

41

3

6

8

borrar(8) ð ok

borrar(4) ð Su único subárbol hijo ocupa su posición borrar(2) ð ¿Cómo?


28

Borrado en ABB (III)Borrado del dato con clave mínima:

– Posición conocida (extremo izquierdo)– No tiene más de 1 hijo

// ... en la clase ArbolBinarioBusqpublic void borrarMin(){ raiz = (NodoBinarioBusq) borrarMin(raiz);}

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;}

2

41

3

6

8

borrarMin()

3

41

2

6

8

borrarMin()


29

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


30

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;}


31

Complejidad y eficienciaEl coste de las operaciones depende de la

profundidad del árbol– ...de la profundidad del nodo en que se realiza la

operaciónProfundidad del árbol: O(log N)

– ...si los nodos están "distribuidos uniformemente"Problemas:

– Algunas operaciones no contribuyen a mantener esa uniformidad (Ej: Borrado)


32

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 1 el tipo de dato arbol aparecen estructuras de tipo...

Documents