Arboles (2016)

Apunte Español
Universidad Universidad Autónoma de Barcelona (UAB)
Grado Ingeniería Informática - 2º curso
Asignatura Laboratori de Programació
Año del apunte 2016
Páginas 2
Fecha de subida 27/06/2017
Descargas 0
Subido por

Vista previa del texto

ÁRBOLES La organización de los datos en una estructura en forma jerárquica o de niveles se llama árbol.
Es un conjunto de datos conectados con ramas dónde cada elemento tiene un único predecesor y 0, 1 o varios sucesores.
COMPONENTES DE UN ÁRBOL Está compuesto por nodos y ramas que conectan los nodos, de forma que cada nodo contiene un único predecesor.
- Nodo => contiene la información.
- Ramas => contienen la conexión a otros nodos.
- Nodo raíz => es el nodo principal.
- Nodo hoja => nodo que no tiene hijos.
- Nodos hermanos => nodos que tienen el mismo padre.
- Ancestros => es el padre de un nodo (nodo raíz es ancestro de todos los nodos).
Subárboles ordenados => ordened tree Subárboles desordenados => oriented tree ALTURA DE UN ÁRBOL La altura de un nodo es la longitud del camino más largo desde el nodo a un nodo hoja (las hojas están a una altura 0).
La altura de un árbol es la altura de su nodo raíz.
ANCHURA / GRADO DE UN ÁRBOL - El número de subárboles de un nodo es el grado del nodo.
Grado => máximo grado de sus nodos.
o Árbol de grado 2 se denomina => árbol binario Anchura => es el grado del árbol.
RECORRER ARBOLES Dos formas de recorrer árboles: - En profundidad prioritaria (depth first transversal) o Preorden: se visita el nodo raíz, y se hace el recorrido en preorden de cada uno de los subárboles del nodo raíz dado.
- o Postorden: se hace un recorrido en postorden de cada uno de los subárboles del nodo raíz en el orden dado y visitar el nodo raíz.
o inorden (binarios): En amplitud prioritaria (Breath first transversal): se recorre el árbol por niveles, dónde en cada uno se visita los nodos de izquierda a derecha.
ÁRBOLES BINARIOS (AB) Un árbol binario es un árbol tal que cada nodo puede tener hasta dos ramas.
Número máximo de nodos en el nivel ‘i’ de un AB => 𝟐𝒊 AB COMPLETO Un árbol binario de altura h y n nodos es completo si 𝒏 = 𝟐𝒉+𝟏 − 𝟏.
Propiedad: - La altura h de un árbol binario completo de n nodos es => 𝐥𝐨𝐠 𝟐 (𝒏 + 𝟏) − 𝟏.
- Demostración: 𝑛 = 2ℎ+1 − 1 → 𝑛 + 1 = 2ℎ+1 → log 2 (𝑛 + 1) = log 2(2ℎ+1 ) → → log 2 (𝑛 + 1) = (ℎ + 1) ∗ log 2 (2) → ℎ = log 2(𝑛 + 1) − 1 Representación secuencial => óptima para árboles binarios completos Si el nodo raíz está en la posición 1 del vector, los hijos izquierdo y derecho de cada nodo de la posición ‘i’ estarán en la posición 2*i y 2*i+1.
El padre de cada nodo en la posición ‘i’ está en la posición i/2 (división entera).
Ventajas: - Fácil gestión - Fácil direccionamiento a los hijos y padres - Eficiente sólo para árboles binarios completos (o balanceados) Desventajas: - Si los árboles no son completos, se desperdicia memoria (huecos) Representación con enlaces => óptima respecto a la inserción y eliminación de nodos y no desperdicia memoria.
...

Comprar Previsualizar