Introducción
En general los árboles se utilizan para construir árboles genealógicos, pero en informática tienen gran aplicación para la creación de los directorios (carpetas) en los discos de las computadoras, para mostrar las relaciones lógicas entre los registros de una base de datos (colección de registros controlados por una computadora) y las búsquedas en los compiladores de los lenguajes de programación (véase árboles binarios).
Concepto de árbol
Un árbol T es un grafo simple que cumple que entre los vértices v, wT existe un único camino simple.
Observe que para ir de un vértice cualquiera a otro siempre se tiene un camino simple; por ejemplo, para ir del vértice d al vértice n, basta con recorrer el camino d — z — i — n.
Conceptos básicos de árboles
Vértice. También llamado nodo y, corresponde a cada uno de los elementos del árbol.
Ejemplo 12.1: según la figura 12.1, los vértices son: i, z, n, m, x, c, d, e, w.
Raíz. Es el vértice principal del árbol
Ejemplo 12.2: según la figura 12.1, la raíz es i.
Padre. Es el vértice que puede o no tener ramificaciones (subárboles).
Ejemplo 12.3: según la figura 12.1, z es padre de los nodos x, c, d.
Hijo. Es el vértice descendiente de un vértice raíz o padre.
Ejemplo 12.4: según la figura 12.1, los nodos x, c, d son hijos de z.
Hermanos. Son los vértices descendientes de un mismo vértice padre
Ejemplo 12.5: según la figura 12.1, los nodos x, c, d son hermanos.
Ejemplo 12.1: según la figura 12.1, los vértices son: i, z, n, m, x, c, d, e, w.
Raíz. Es el vértice principal del árbol
Ejemplo 12.2: según la figura 12.1, la raíz es i.
Padre. Es el vértice que puede o no tener ramificaciones (subárboles).
Ejemplo 12.3: según la figura 12.1, z es padre de los nodos x, c, d.
Hijo. Es el vértice descendiente de un vértice raíz o padre.
Ejemplo 12.4: según la figura 12.1, los nodos x, c, d son hijos de z.
Hermanos. Son los vértices descendientes de un mismo vértice padre
Ejemplo 12.5: según la figura 12.1, los nodos x, c, d son hermanos.
Descendiente. Siempre que exista camino para ir de un vértice v a otro w, se dice que, v es descendiente de w.
Ejemplo 12.6: según la figura 12.1, los nodos descendientes de i son entre otros z, x.
Ancestro. Si hay camino para ir de un vértice v a otro vértice w (máximo hasta la raíz) se dice que, w es ancestro de v.
Ejemplo 12.7: según la figura 12.1, los nodos x, c, d son i, z.
Hoja. Es un vértice que no tiene ramificaciones (uno o más hijos). También se llama nodo terminal.
Ejemplo 12.8: según la figura 12.1, los nodos del árbol x, c, d, e w son hojas
Nodo no Terminal. Es aquel que tiene por lo menos una ramificación.
Ejemplo 12.9: según la figura 12.1, los nodos no terminales son: i, z, m, n.
Camino. Es el conjunto de vértices por los que se pasa para ir de un vértice a otro.
Ejemplo 12.10: según la figura 12.1, el camino para ir del nodo x al nodo n es x, z, i, n.
Longitud de un camino. Es el número de vértices por los que se deben pasar o recorrer para ir de un vértice a otro.
Ejemplo 12.11: La longitud del camino para ir del nodo x al nodo n de la figura 12.1 es 4.
Nivel: es la longitud del camino simple de la raíz al vértice. Cada nodo tiene un nivel dentro de un árbol.
Ejemplo 12.12: según la figura 12.1, el nodo raíz i tiene el nivel 0, sus hijos ocupan el nivel 1; sus nietos ocupan el nivel 2 y, así sucesivamente
Altura de un árbol. Es el nivel de la hoja u hojas más distantes de la raíz.
Ejemplo 12.13: según la figura 12.1, la altura del árbol es 2.
Ejemplo 12.6: según la figura 12.1, los nodos descendientes de i son entre otros z, x.
Ancestro. Si hay camino para ir de un vértice v a otro vértice w (máximo hasta la raíz) se dice que, w es ancestro de v.
Ejemplo 12.7: según la figura 12.1, los nodos x, c, d son i, z.
Hoja. Es un vértice que no tiene ramificaciones (uno o más hijos). También se llama nodo terminal.
Ejemplo 12.8: según la figura 12.1, los nodos del árbol x, c, d, e w son hojas
Nodo no Terminal. Es aquel que tiene por lo menos una ramificación.
Ejemplo 12.9: según la figura 12.1, los nodos no terminales son: i, z, m, n.
Camino. Es el conjunto de vértices por los que se pasa para ir de un vértice a otro.
Ejemplo 12.10: según la figura 12.1, el camino para ir del nodo x al nodo n es x, z, i, n.
Longitud de un camino. Es el número de vértices por los que se deben pasar o recorrer para ir de un vértice a otro.
Ejemplo 12.11: La longitud del camino para ir del nodo x al nodo n de la figura 12.1 es 4.
Nivel: es la longitud del camino simple de la raíz al vértice. Cada nodo tiene un nivel dentro de un árbol.
Ejemplo 12.12: según la figura 12.1, el nodo raíz i tiene el nivel 0, sus hijos ocupan el nivel 1; sus nietos ocupan el nivel 2 y, así sucesivamente
Altura de un árbol. Es el nivel de la hoja u hojas más distantes de la raíz.
Ejemplo 12.13: según la figura 12.1, la altura del árbol es 2.
Concepto de árbol binario
Un árbol binario es un tipo de árbol en que cada vértice máximo puede tener dos hijos; su nodo raíz está enlazado a dos subárboles binarios disjuntos denominados subárbol izquierdo y subárbol derecho. Los árboles binarios no son vacíos ya que como mínimo tienen el nodo raíz.
Árbol binario lleno
Es aquel árbol en el que los nodos de cada nivel tienen sus dos hijos o ninguno (si es hoja). Ejemplo 12.15: el árbol de la figura 12.2 es lleno.
Árbol binario completo
Es aquel árbol binario lleno en que todas sus hojas están en el nivel n o n-1 considerando que para un hijo derecho hay siempre un hijo izquierdo. Estos árboles ocupan todas las posiciones del vector. Por lo tanto, todo árbol binario lleno es completo, pero no la viceversa.
Ejemplo 12.16: el árbol de la figura 12.3 es completo.
Propiedades de los árboles binarios
Representación de árboles binarios
Los árboles binarios pueden representarse en un vector o en una lista ligada. Nuestro interés se centrará en los vectores.
Para representar a un árbol binario en un vector se escriben por niveles los nodos del árbol de manera ordenada, de izquierda a derecha (hijo izquierdo — hijo derecho).
Esta representación es poco eficiente cuando el árbol no es completo, en vista del gran desperdicio de memoria que podría haber por las posiciones libres que quedarían en el vector.
Si k es la posición en un vector de un nodo de un árbol con n niveles, se tiene:
Para representar a un árbol binario en un vector se escriben por niveles los nodos del árbol de manera ordenada, de izquierda a derecha (hijo izquierdo — hijo derecho).
Esta representación es poco eficiente cuando el árbol no es completo, en vista del gran desperdicio de memoria que podría haber por las posiciones libres que quedarían en el vector.
Si k es la posición en un vector de un nodo de un árbol con n niveles, se tiene:
.El vector tendrá 2n+1 -1 posiciones.
. El padre estará en la posición k/2 (con k>1)
.El hijo izquierdo estará en la posición 2*I (con 2*k<n) y el hijo derecho en la posición 2*k+1.
Ejemplo 12.18: represente en un vector el árbol de la figura 12.4
El árbol de la figura 12.4 representado en un vector queda como sigue:
El árbol de la figura 12.4 representado en un vector queda como sigue:
¿En qué posiciones están: el hijo izquierdo de b, el hijo derecho de c. ¿Cómo podría verificarse que f y e son hojas?
Recorridos en un árbol binario
Un recorrido en un árbol binario es Una operación que consiste en visitar todos sus vértices o nodos, de tal manera que cada vértice se visite una sola vez.
Se distinguen tres tipos de recorrido: INORDEN, POSORDEN Y PREORDEN.
En cada recorrido se tiene en cuenta la posición de la raíz (de ahí su nombre) y que siempre se debe ejecutar primero el hijo izquierdo y luego el derecho.
Se distinguen tres tipos de recorrido: INORDEN, POSORDEN Y PREORDEN.
En cada recorrido se tiene en cuenta la posición de la raíz (de ahí su nombre) y que siempre se debe ejecutar primero el hijo izquierdo y luego el derecho.
Recorrido INORDEN. Este recorrido se realiza así: primero recorre el subárbol izquierdo, segundo visita la raíz y por último, va al subárbol derecho. En síntesis:
hijo izquierdo — raíz — hijo derecho
hijo izquierdo — raíz — hijo derecho
Recorrido PREORDEN. Este recorrido se realiza así: primero visita la raíz; segundo recorre el subárbol izquierdo y por último va a subárbol derecho. En síntesis:
raíz — hijo izquierdo — hijo derecho
raíz — hijo izquierdo — hijo derecho
Recorrido POSORDEN. Primero recorre el subárbol izquierdo; segundo, recorre el subárbol derecho y por último, visita la raíz. En síntesis:
hijo izquierdo– hijo derecho — raíz
Ejemplo 12.19: realice los diferentes recorridos sobre árboles de las figuras 12.5a, 12.5b y 12.5c.
hijo izquierdo– hijo derecho — raíz
Ejemplo 12.19: realice los diferentes recorridos sobre árboles de las figuras 12.5a, 12.5b y 12.5c.
Tipos de árboles binarios
Árboles de expresión
Son árboles binarios que se utilizan para almacenar en la memoria de una computadora expresiones lógicas, aritméticas o algebraicas. Este proceso lo realizan los compiladores de los lenguajes de programación. Los PC y las calculadoras comunes utilizan el recorrido INORDEN usando la notación infija para evaluar las expresiones, al igual que los seres humanos. El recorrido PREORDEN utiliza la notación infija o polaca.
Algunos compiladores y algunas calculadoras como por ejemplo, la Hewlet Packard evalúan las expresiones en POSORDEN usando la notación posfija (o notación polaca inversa) donde el operador aparece después de sus operandos; por ejemplo, AB/ indican que A debe dividirse por B. Observe que la notación posfija tiene ventajas sobre la notación infija debido a que la notación posfija no necesita paréntesis ni tiene que predeterminar un orden de prioridad para sus operadores (lógicos o aritméticos); es por tal razón que una expresión se evaluará sin ambigüedad.
Para evaluar una expresión con recorrido INORDEN pueden seguirse los siguientes pasos:
Algunos compiladores y algunas calculadoras como por ejemplo, la Hewlet Packard evalúan las expresiones en POSORDEN usando la notación posfija (o notación polaca inversa) donde el operador aparece después de sus operandos; por ejemplo, AB/ indican que A debe dividirse por B. Observe que la notación posfija tiene ventajas sobre la notación infija debido a que la notación posfija no necesita paréntesis ni tiene que predeterminar un orden de prioridad para sus operadores (lógicos o aritméticos); es por tal razón que una expresión se evaluará sin ambigüedad.
Para evaluar una expresión con recorrido INORDEN pueden seguirse los siguientes pasos:
- Trascriba la expresión con recorrido INORDEN a POSORDEN (o a PREORDEN). Para tal fin, debe parentizar completamente la expresión y luego, cambie el paréntesis derecho (o izquierdo) por el operador más próximo no utilizado.
2. Forme el árbol de expresión con recorrido POSORDEN (o PREORDEN) a partir de la expresión dada. En efecto, el árbol se forma escribiendo como raíz el operador principal de la expresión y se escriben los operandos como subárboles izquierdo y derecho. Observe que las hojas del árbol corresponderán a los operandos.
3. Evalúe la expresión utilizando el árbol, dándole valores aritméticos o lógicos a los operandos.
Ejemplo 12.20: la representación en un árbol binario de la expresión algebraica
Árbol binario de búsqueda
Un árbol binario de búsqueda es aquel que tiene sus nodos con un orden definido, de tal manera que los datos del subárbol izquierdo son menores y los del subárbol derecho son mayores. Estos árboles tienen como particularidad la permisión de que se puedan realizar búsquedas de nodos o datos determinados, utilizando el método de búsqueda binaria de manera similar al usado en arreglos.
Para crear un árbol binario de búsqueda a partir un listado de datos, asuma que el primer dato es la raíz del árbol; los demás se ubican en el árbol así: los menores como hijos izquierdos y los mayores como hijos derechos.
Para crear un árbol binario de búsqueda a partir un listado de datos, asuma que el primer dato es la raíz del árbol; los demás se ubican en el árbol así: los menores como hijos izquierdos y los mayores como hijos derechos.
Ejemplo 12.21: el grafico del árbol, según la siguiente lista: 43, 10, 8, 54, 15, 50, 53 está en la figura 12.7.
PROBLEMAS RESUELTOS
Distribuya los nodos -5,2,-11,4,-13,5,3,-14,1,6,10,-12,8 en el árbol binario de la figura 12.8 y determine ¿Cuáles son los nodos hoja? ¿Cuáles son nodos de 2 hijos?
Solución: Según la figura 12.9, los nodos hoja son:-14,-12, 1, 3, 8 y los nodos de grado 2 son: -13,-5, 2, 4.
No hay comentarios.:
Publicar un comentario