Tecnológico de estudios
superiores de Ecatepec
División de ingeniería en sistemas computacionales
Integrantes:
Nava Sánchez Leon Michell
Rangel Hernández Ricardo
Valencia Flores Oswaldo
Asignatura: Estructura de datos
Grupo: 5301 Profesora: M. en C. Xóchitl
Raquel Wong Cohén
ARBOLES
[Link] que es un árbol en programación.
Un árbol es un tipo abstracto de datos (TAD) ampliamente usado que imita la estructura jerárquica de
un árbol, con un valor en la raíz y subárboles con un nodo padre, representado como un conjunto
de nodos enlazados.
Una estructura de datos de árbol se puede definir de forma recursiva (localmente) como una colección
de nodos (a partir de un nodo raíz), donde cada nodo es una estructura de datos con un valor, junto con
una lista de referencias a los nodos (los hijos), con la condición de que ninguna referencia esté
duplicada ni que ningún nodo apunte a la raíz.
[Link] los tipos de árboles en la programación (Arboles binarios, arboles binarios completos,
arboles-b y arboles –b+)
Binario: Un árbol Binario puede tener cero nodos y este caso se dice que está vacío. Puede tener un
sólo nodo, y en este caso solamente existe la raíz del árbol o puede tener un número finito de nodos.
Cada nodo puede estar ramificado por la izquierda o por la derecha o puede no tener ninguna
ramificación.
Estructura
Arboles binarios completos: Un árbol binario completo es un árbol en el que cada nodo tiene cero o
dos hijos. Por ejemplo, el primero de los siguientes árboles es un árbol binario completo pero los otros
no lo son.
Arboles-b: En las ciencias de la computación, los árboles-B o B-árboles son estructuras de datos de
árbol que se encuentran comúnmente en las implementaciones de bases de datos y sistemas de
archivos. Al igual que los árboles binarios de búsqueda, son árboles balanceados de búsqueda, pero
cada nodo puede poseer más de dos hijos.1 Los árboles B mantienen los datos ordenados y las
inserciones y eliminaciones se realizan en tiempo logarítmico amortizado.
Los B-árboles son árboles cuyos nodos pueden tener un número múltiple de hijos tal como muestra el
esquema de uno de ellos en la figura.
Arbol-b+: Los árboles B+ constituyen otra mejora sobre los árboles B, pues conservan la propiedad de
acceso aleatorio rápido y permiten además un recorrido secuencial rápido. En un árbol B+ todas las
claves se encuentran en hojas, duplicándose en la raíz y nodos interiores aquellas que resulten
necesarias para definir los caminos de búsqueda. Para facilitar el recorrido secuencial rápido las hojas
se pueden vincular, obteniéndose, de esta forma, una trayectoria secuencial para recorrer las claves del
árbol.
Su principal característica es que todas las claves se encuentran en las hojas. Los árboles B+ ocupan
algo más de espacio que los árboles B, pues existe duplicidad en algunas claves. En los árboles B+ las
claves de las páginas raíz e interiores se utilizan únicamente como índices.
5.-Mencionar el recorrido de los árboles (in orden, post orden y pre orden).
Los recorridos son algoritmos que nos permiten recorrer un árbol en un orden específico, los
recorridos nos pueden ayudar encontrar un nodo en el árbol, o buscar una posición determinada para
insertar o eliminar un nodo.
Básicamente podemos catalogar la búsqueda en dos tipos, la búsqueda en profundidad y la búsqueda
en amplitud.
Recorrido Pre-orden: El recorrido inicia en la Raíz y luego se recorre en pre-orden cada uno de los
sub-árboles de izquierda a derecha.
Una imagen a continuación para comprender mejor.
Imagen de: (Blancarte, 2014
Recorrido Pos-orden: Se recorre el pos-orden cada uno de los sub-árboles y al final se recorre la
raíz. Imagen a continuación de como es este recorrido.
Imagen de: (Blancarte, 2014)
Recorrido in-orden: Se recorre en in-orden el primer sub-árbol, luego se recorre la raíz y al final se
recorre en in-orden el demás sub-árbol. Imagen a continuación.
Imagen de: (Blancarte, 2014)
