CLASIFICACIÓN DE LAS REDES DE COMPUTADORAS

[pic 1]

INSTITUTO TECNOLÓGICO SUPERIOR DE LERDO

INGENIERÍA EN SISTEMAS COMPUTACIONALES

LENGUAJES Y AUTÓMATAS II

PRÁCTICA 1 UNIDAD 1

Ing. Roberto García Flores

Jesús Daniel Cisneros Ríos 182310632

CD. LERDO, DGO.

AGOSTO - DICIEMBRE 2021

ÁRBOLES DE EXPRESIONES

Un árbol es un conjunto finito de nodos y un conjunto finito de arcos dirigidos, llamados ramas, de modo que,

1. Existe un nodo especial llamado raíz.
2. Los nodos restantes se dividen en n >= 0 conjuntos disjuntos, T1 . . . Tn donde cada Ti es a su vez un árbol (subárboles de la raíz).
3. Las ramas conectan pares de nodos.

Un nodo está formado por la información que contiene y las ramas que lo unen con

otros nodos.

• Cada nodo es la raíz de un árbol.
• Cualquier árbol de n nodos tiene n-1 ramas.
• Si de un nodo n hay una rama hacia otro nodo h, entonces se dice que h es hijo de n y, por tanto, n es el padre de h.
• Cada nodo tiene un único padre, excepto la raíz que no tiene. Dos nodos son hermanos si tienen el mismo padre.
• Un nodo hoja es aquel que no tiene hijos.

Árboles binarios

Un árbol binario es un conjunto finito de nodos que puede estar vacío o está compuesto por un nodo raíz y dos subárboles binarios disjuntos llamados subárbol izquierdo y subárbol derecho.

[pic 2]

Árboles binarios distintos

La altura de un árbol binario vacío es 0.

Árbol binario equilibrado: para todos sus nodos, se cumple:

|altura(subarbolizquierdo)−altura(subarbolderecho)| ≤ 1

Árbol binario extendido: todos sus nodos tienen 0 o 2 hijos no vacíos.

Árbol binario completo de profundidad n: todos los nodos hojas están en el nivel n, y además el número de nodos es 2n −1 (número máximo de nodos para un árbol de profundidad n).

[pic 3]

Árboles de expresiones

Aplicación: Los árboles de expresiones representan las expresiones escritas en el programa. Los compiladores emplean estos árboles como representación intermedia entre el código fuente y el objeto.

[pic 4]

En un árbol de expresiones:

• Los nodos hojas contienen operandos: constantes o variables.

• Los nodos internos contienen operadores.

Una expresión aritmética representada mediante un árbol binario puede evaluarse mediante un recorrido en postorden. En cada nodo:

• Se evalúan su subárbol izquierdo y su subárbol derecho.

• Se aplica el operador de ese nodo a los resultados obtenidos en el paso anterior.

Montículos

Un montículo (heap) es un árbol binario que cumple las siguientes propiedades:

1. Es un árbol binario casi-completo
2. Para cada nodo de montículo, el valor que almacena es mayor o igual que el valor almacenado en sus nodos hijos.

[pic 5]

Propiedades de los montículos:

• Para un mismo conjunto de valores, podemos construir diferentes montículos, aunque la forma de todos ellos siempre será la misma.
• El nodo raíz contendrá siempre el elemento mayor del conjunto.
• Todo subárbol de un montículo es también un montículo.
• Puede haber valores repetidos.

Un montículo donde el elemento mayor está en la raíz es un max-heap.

Es posible implementar un min-heap, donde el elemento menor estará en la raíz y cada nodo tendrá un valor menor o igual que el de sus hijos.

Implementación

Los montículos se implementan sobre un vector, donde los elementos están guardados de forma secuencial del siguiente modo:

1. La raíz se guarda siempre en la posición 0 del vector.
2. Para cualquier nodo interno almacenado en la posición i del vector se cumple que su hijo izquierdo está en la posición 2 ∗ i+1 y su hijo derecho en la posición 2 ∗ i+2 (siempre y cuando dicho nodo tenga hijos). Por tanto,

➤ elementos [2 ∗ i+1] ≤ elementos[i] y ➤ elementos [2 ∗ i+2] ≤ elementos[i].

Esta implementación permite conocer cuál es el nodo padre de cualquier otro nodo (excepto la raíz).

[pic 6]

Árboles de Huffman

Para representar n caracteres en binario se necesitarían r bits tal que 2 r−1 < n ≤ 2 r.

Por ejemplo, el código ASCII utiliza 7 bits para codificar 128 caracteres. En general, utilizando códigos de bits de longitud variable, de manera que los caracteres más frecuentes tengan códigos más cortos mientras que los menos frecuentes tengan códigos más largos, se puede reducir el tamaño de los ficheros.

El algoritmo de Huffman construye un código binario para un conjunto de caracteres:

• La longitud de los códigos es la mínima.

• Cada carácter puede ser unívocamente decodificado.

Sea un árbol extendido con n nodos hoja donde a cada uno se le ha asignado un peso wi.

La longitud externa de caminos con peso se define como la suma de la longitud de cada camino desde la raíz a un nodo hoja por su peso: p = w1 L1 +w2 L2 +...+wn Ln donde wi y Li denotan respectivamente, el peso del nodo i y la longitud del camino hasta el nodo hoja i. Ejemplo: p = 2 ∗ 2+5 ∗ 3+1 ∗ 3+4 ∗ 1 = 26

Si se consideran todos los árboles binarios extendidos con n nodos hoja con iguales pesos asignados, el algoritmo de Huffman construye el árbol cuya longitud externa de caminos es mínima.

...