Download Arbol ABB.
Document related concepts
Transcript
ÁRBOLES Prof. Nibaldo Rodriguez A. PONTIFICIA UNIVERSIDAD CATOLICA DE VALPARAISO Escuela de Ingeniería Informática ÁRBOLES Un árbol A es un conjunto finito de uno o más nodos tal que: 1. Existe un nodo especial denominado RAIZ(V1) del árbol. 2. Los nodos restantes (V2 ,...Vn) se dividen en m>=0 conjuntos disjuntos denominados A1, A2, A3,...Am, cada uno de los cuales es, a su vez, un árbol. Estos árboles se llaman Subárboles de la RAIZ. A B E C D F G K H I J L 1 PONTIFICIA UNIVERSIDAD CATOLICA DE VALPARAISO Escuela de Ingeniería Informática ÁRBOLES A Raíz: Nodo que no tiene antecesores Nodo: Vértices o elementos del árbol B C Nodo Terminal u hoja: Vértices o elementos del árbol que no contienen subárboles. E F Hermanos: Nodos de un mismo padre. Nodos Interiores: Nodos que no son hoja ni raíz. Bosque: Colección de dos o más árboles. K Arista: Enlace entre dos nodos consecutivos. Camino: Secuencia de aristas consecutivas. Rama: Camino que termina en hoja. Nivel: longitud del camino desde la raíz al nodo específico. D G H I J L Altura o profundidad: el número máximo de nodos de una rama. Equivale al nivel más alto de los nodos más uno. Peso: es el número de nodos terminales. Grado: el número de hijos que salen de un nodo PONTIFICIA UNIVERSIDAD CATOLICA DE VALPARAISO Escuela de Ingeniería Informática Arboles Binarios Un Árbol binario es un conjunto finito de cero o más nodos tal que: 1. Existe un nodo denominado raíz del árbol 2. Cada nodo tiene 0, 1 o 2 subárboles, •Llamado Subárbol Izquierdo y Subárbol Derecho. Dos Árboles Binarios son Similares si tienen la misma estructura A B A C R E 3 4 E 2 PONTIFICIA UNIVERSIDAD CATOLICA DE VALPARAISO Escuela de Ingeniería Informática Arboles Binarios A Se dice que dos Árboles Binarios son equivalentes si tienen la misma estructura y además la misma información A B C B C E D D E Se dice que un Árbol Binario es EQUILIBRADO si las alturas de los dos Subárboles de cada nodo del árbol se diferencian en una unidad como máximo. A A B T C N D F B E T S F C N PONTIFICIA UNIVERSIDAD CATOLICA DE VALPARAISO Escuela de Ingeniería Informática Arboles Binarios A Un árbol binario es Completo si todos sus nodos, excepto las hojas, tienen exactamente dos subárboles. B T C N E D F S A Un árbol binario es lleno si todas sus hojas están al mismo nivel y todos sus nodos interiores tienen cada uno 2 hijos. B T C N D E 3 PONTIFICIA UNIVERSIDAD CATOLICA DE VALPARAISO Escuela de Ingeniería Informática Arboles Binarios Un árbol binario es degenerado si todos sus nodos excepto el último tienen sólo un subárbol A A B B N T C D PROPIEDAD • Dado un árbol de grado g y altura h, el número máximo de nodo es igual a: h −1 N nodo = ∑ g i i =0 • Determinar el número de nodos para el caso g=2 (árbol binarios ) 4 PONTIFICIA UNIVERSIDAD CATOLICA DE VALPARAISO Escuela de Ingeniería Informática Estructuras de Datos para Arboles Binarios Data A B A IZQ C B DER C E T T E S S PONTIFICIA UNIVERSIDAD CATOLICA DE VALPARAISO Escuela de Ingeniería Informática DCLARACIÓN EN LENGUAJE C typedef struct nodo { int data; struct nodo *izq, *der; } Arbol; 5 PONTIFICIA UNIVERSIDAD CATOLICA DE VALPARAISO Escuela de Ingeniería Informática Recorrido de árboles binarios Se denomina recorrido de un árbol al proceso que permite acceder una sola vez a cada uno de los nodos del árbol. Cuando un árbol se recorre, el conjunto completo de nodos se examina. Recorrido pre-orden 1. Visitar nodo raíz 2. Recorrer el subárbol izquierdo en modo pre-orden 3. Recorrer el subárbol derecho en modo pre-orden Recorrido in-orden 1. Recorrer el subárbol izquierdo en modo in-orden 2. Visitar nodo raíz 3. Recorrer el subárbol derecho en modo in-orden Recorrido post-orden 1. Recorrer el subárbol izquierdo en modo post-orden 2. Recorrer el subárbol derecho en modo post-orden 3. Visitar nodo raíz PONTIFICIA UNIVERSIDAD CATOLICA DE VALPARAISO Escuela de Ingeniería Informática Recorrido Pre-Orden Recorrido Pre-Orden 1. Visitar nodo raíz 2. Recorrer el subárbol izquierdo en modo pre-orden 3. Recorrer el subárbol derecho en modo pre-orden ABDHIEJKCFLMGNO A B D H I C E J G F K L M N O 6 PONTIFICIA UNIVERSIDAD CATOLICA DE VALPARAISO Escuela de Ingeniería Informática Recorrido in-orden Recorrido In-Orden 1. Recorrer el subárbol izquierdo en modo in-orden 2. Visitar nodo raíz 3. Recorrer el subárbol derecho en modo in-orden HDIBJEKALFMCNGO A B D H I C E J G F L K M N O PONTIFICIA UNIVERSIDAD CATOLICA DE VALPARAISO Escuela de Ingeniería Informática Recorrido post-orden Recorrido Post-Orden 1. Recorrer el subárbol izquierdo en modo post-orden 2. Recorrer el subárbol derecho en modo post-orden 3. Visitar nodo raíz HIDJKEBLMFNOGCA A B D H I C E J G F K L M N O 7 EJERCICIOS • Dado un árbol binario de datos entero. Implementar las siguientes funciones Iterativas: • Recorrido: – Preorden, Inorden, Postorden • Recorrido: – Anchura Izquierdo-derecho – Anchura Derecho-Izquierdo PONTIFICIA UNIVERSIDAD CATOLICA DE VALPARAISO Escuela de Ingeniería Informática Arboles binarios de búsqueda Un árbol de búsqueda es un TDA árbol en el que para cada nodo todas las claves de cada subarbol satisfacen una y solo una condición de un conjunto de Condiciones mutuamente excluyentes Un árbol binario de búsqueda, es un árbol binario en el que dadas dos Condiciones mutuamente exluyentes, para cada nodo, todas las claves de su subárbol izquierdo satisfacen una condición y todas las de su subárbol Derecho la otra. Ki EJEMPLO DE NÚMEROS ENTEROS: Para cada nodo Ni con clave Ki, todas las claves en los nodos del subárbol izquierdo son menores que Ki y todas las claves en los nodos del subárbol derecho son mayores que Ki. Siempre existen 2 excluyentes (< ; >) relaciones <Ki >Ki mutuamente 8 PONTIFICIA UNIVERSIDAD CATOLICA DE VALPARAISO Escuela de Ingeniería Informática Arboles binarios de búsqueda Ki <Ki >Ki H D B A C L F E N J G I K M PONTIFICIA UNIVERSIDAD CATOLICA DE VALPARAISO O Escuela de Ingeniería Informática DECLARACIÓN EN LENGUAJE C typedef struct nodo { int dato; struct nodo *izq,*der; } Arbol; 9 IMPLEMENTACIÓN ITERATIVA ABB ¾INSERATAR ¾ELIMINAR DATO usando criterio del menor de los mayores 10