Arboles

República Bolivariana de Venezuela Ministerio del Poder Popular para la Defensa Universidad Nacional Experimental Politécnica de la Fuerza Armada. UNEFA- APURE

ÁRBOLES Tutor: Laryenso Gutiérrez

Autores: García Jasneyka C.I. 19.405.985 España Silvia C.I. 18.727.135

San Fernando de Apure, Julio de 2009.

CONTENIDO Definición de Arboles Operaciones Básicas Con Árboles

Añadir o insertar elementos. Buscar o localizar elementos. Borrar elementos. Moverse a través del árbol. Recorrer el árbol completo.

Tipos de arboles

Árboles Ordenados (ABB) Árboles Degenerados  Árbol-B+ Árbol Rojo-Negro  Árbol-B* Árbol KD Árboles-R Árbol Biselado.

Árboles Binarios de Búsqueda Árboles AVL Árboles binarios de búsqueda Árbol-B Árbol de Decisión Árboles BSP Árbol de Fibonacci

Funcionalidad del árbol AUTORAS: JASNEYKA GARCIA ESPAÑA SILVIA

Un árbol ordenado se define como un árbol en el que los subárboles de cada nodo forman un conjunto ordenado. En un árbol ordenado, podemos hablar del primero, segundo o último hijo de un nodo en

Un árbol es un conjunto finito no vacío de elementos, en el cual un elemento se denomina la raíz y los restantes se dividen en subconjuntos disjuntos, cada uno de los cuales es por sí mismo un árbol.

ÁRBOLES Un nodo sin subárboles es una hoja. El grado de un nodo es el número máximo de hijos que algún nodo tiene.

Cada elemento en un árbol se denomina un nodo del árbol. De igual manera se dice que, un árbol es una estructura no lineal en la que cada nodo puede apuntar a uno o varios nodos.

AUTORAS: JASNEYKA GARCIA ESPAÑA SILVIA

Recorrer el árbol completo.

Añadir o insertar elementos.

OPERACIONES BÁSICAS CON ÁRBOLES

Moverse a través del árbol.

Buscar o localizar elementos. Borrar elementos.

AUTORAS: JASNEYKA GARCIA ESPAÑA SILVIA

Un árbol ordenado, en general, es aquel a partir del cual se puede obtener una secuencia ordenada siguiendo uno de los recorridos posibles del árbol: inorden, preorden o postorden.

T I P O S D E A R B O L E S

ÁRBOLES ORDENADOS Existen varios tipos de árboles ordenados, que veremos a continuación Árboles Binarios Árboles AVL: de Búsqueda (ABB): Árboles Perfectamente Equilibrados Árboles 2-3:

En estos árboles es importante que la secuencia se mantenga ordenada aunque se añadan o se eliminen nodos.

Árboles-B: AUTORAS: JASNEYKA GARCIA ESPAÑA SILVIA

El valor de la clave de la raíz del subárbol izquierdo es menor que el valor de la clave del nodo y que el valor de la clave raíz del subárbol derecho es mayor que el

Se trata de árboles de orden 2 en los que se cumple que para cada nodo.

ÁRBOLES BINARIOS DE BÚSQUEDA (ABB)

OPERACIONES EN ABB

Moverse a través del árbol. Añadir o insertar elementos.

Buscar o localizar elementos.

Borrar elementos. AUTORAS: JASNEYKA GARCIA ESPAÑA SILVIA

Información .

ÁRBOLES DEGENERADOS  Los árboles binarios de búsqueda tienen un gran inconveniente. Por ejemplo, supongamos que creamos un ABB a partir de una lista de valores ordenada: 2, 4, 5, 8, 9, 12 Difícilmente podremos llamar a la estructura resultante un árbol: Esto es lo que llamamos un árbol binario de búsqueda degenerado.

AUTORAS: JASNEYKA GARCIA ESPAÑA SILVIA

El algoritmo para mantener un árbol AVL equilibrado se basa en reequilibrados locales, de modo que no es necesario explorar todo el árbol después de cada inserción o

Un árbol AVL (llamado así por las iniciales de sus inventores: Adelson-Velskii y Landis) es un árbol binario de búsqueda en el que para cada nodo, las alturas de sus subárboles izquierdo y derecho no difieren en más de 1.

Árboles AVL No se trata de árboles perfectamente equilibrados, pero sí son lo suficientemente equilibrados como para que su comportamiento sea lo bastante bueno como para usarlos donde los ABB no garantizan tiempos de búsqueda óptimos. AUTORAS: JASNEYKA GARCIA ESPAÑA SILVIA

ÁRBOL-B+

Todas las hojas se encuentran en el mi smo, más bajo nivel. Los nodos hoja se encuentran un idos entre sí como una l ista enlazada para permitir búsqueda secuencial .

En informática, un ár bol-B es un tipo de estructura de datos de árboles. Repr esenta una colección de datos ordenados de manera que se permi te un a inserción y borrado efi ci entes de elementos. Un á rbol-B+ es una variación de un árbol-B. En un árbol-B+, en contraste r especto un árbol-B, toda la infor mación se guarda en l as hojas. L os nodos i nter nos sólo contienen claves y

AUTORAS: JASNEYKA GARCIA ESPAÑA SILVIA

Lista Enlazada: Aquí se puede insertar y borrar elementos fácilmente, pero es costoso el buscar y encontrar un elemento, ya que se debe usar una búsqueda secuencial.

Esta sección discute una de las estructuras de datos más importantes de la informática, el árbol binario

ÁRBOLES BINARIOS DE BÚSQUEDA Esta estructura contrasta con las siguientes estructuras: Array Lineal Ordenado: Aquí se puede buscar y encontrar un elemento con un tiempo de ejecución f(n) = (log2n), pero es costoso el insertar y borrar elementos.

Esta estructura permite buscar y encontrar un elemento con una media de tiempo de ejecución f (n) = 0 ( log2 n), también permite insertar y borrar

AUTORAS: JASNEYKA GARCIA ESPAÑA SILVIA

En los árboles rojo-negro las hojas no son relevantes y no contienen datos. A la hora de implementarlo en un lenguaje de programación, para ahorrar memoria, un único nodo (nodo-centinela) hace de nodo hoja para todas las ramas.

Un árbol rojo negro es un tipo abstracto de datos, concretamente es un árbol binario de búsqueda equilibrado, una estructura de datos utilizada en informática y ciencias de la

Árbol Rojo Negro

Es complejo, pero tiene un buen caso peor de tiempo de ejecución para sus operaciones y es eficiente en la práctica. Puede buscar, insertar y borrar en un tiempo O(log n), donde n es el número de elementos del árbol.

La estructura original fue creada por Rudolf Bayer en 1972, que le dio el nombre de “árboles-B binarios simétricos”, pero tomó su nombre moderno en un trabajo de Leo J. Guibas y Robert Sedgewick realizado

AUTORAS: JASNEYKA GARCIA ESPAÑA SILVIA

ÁRBOL-B En las ciencias de la computación, los árboles-B ó B-árboles son estructuras de datos de árbol

se encuentran comúnmente en las implementaciones de bases de datos y sistemas de archivos. Los árboles B mantienen los datos ordenados y las inserciones y eliminaciones se realizan en tiempo logarítmico amortizado.

La idea tras los árboles-B es que los nodos internos deben tener un número variable de nodos hijo dentro de un rango predefinido Cuando se inserta o se elimina un dato de la estructura, la cantidad de nodos hijo varía dentro de un nodo. Para que siga manteniéndose el número de nodos dentro del rango AUTORAS: JASNEYKA GARCIA ESPAÑA SILVIA predefinido, los nodos

Dado que se permite un rango variable de nodos hijo, los árboles-B no necesitan rebalancearse tan frecuentemente como los árboles binarios de búsqueda auto-

ÁRBOL-B*

AUTORAS: JASNEYKA GARCIA ESPAÑA SILVIA

ÁRBOL DE DECISIÓ N Un árbol de decisión tiene unas entradas las cuales pueden ser un objeto o una situación descrita por medio de un conjunto de atributos y a partir de esto devuelve una respuesta la cual en últimas

Un árbol de decisión es un modelo de predicción utilizado en el ámbito de la inteligencia artificial, dada una base de datos se construyen diagramas de

Muy similares a los sistemas de predicción basados en reglas, que sirven para representar y categorizar una serie de condiciones que ocurren de forma sucesiva, para la resolución de un problema.

AUTORAS: JASNEYKA GARCIA ESPAÑA SILVIA

En ciencias de la computación, un Árbol kd (abreviatura de árbol k-dimensional) es una estructura de datos de particionado del espacio que organiza los puntos en un espacio euclídeo de k dimensiones.

ÁRBOL KD Técnicamente, la letra k se refiere al número de dimensiones. Un árbol kd tridimensional podría ser llamado un árbol 3d. Sin embargo se suele emplear la expresión "árbol kd tridimensional".

Un árbol kd emplea sólo planos perpendiculares a uno de los ejes del sistema de coordenadas. Esto difiere de los árboles BSP, donde los planos pueden ser arbitrarios.

AUTORAS: JASNEYKA GARCIA ESPAÑA SILVIA

Usos De Un Árbol Kd

Complejidad

Construir un árbol kd estático a partir de n puntos es de O(nlogn). Insertar un nuevo punto en un árbol kd balanceado es de O(logn). Eliminar un punto de un árbol kd balanceado es de O(logn).

Determinar Dónde Evaluar Una Superficie

En las regresiones locales es común evaluar la superficie contenida directamente sólo por los vértices del árbol kd e interpolar en algún punto.

Como los árboles kd se "adaptan" al espacio, este método puede suministrar una excelente aproximación a las verdaderas superficies de regresión local.

AUTORAS: JASNEYKA GARCIA ESPAÑA SILVIA

Búsqueda Ortogonal En Un Árbol Kd

Usar un árbol kd para encontrar todos los puntos que se encuentran en un rectángulo determinado (o análogo de más dimensiones).

dibujar primero lo más lejano y después lo más cercano. Sin embargo, este sistema es muy limitado ya que se pierde tiempo pintando objetos que más tarde serán tapados por otros.

Binary space partitioning o Partición Binaria del Espacio (BSP) es un método para subdividir recursivamente un espacio en elementos convexos empleando hiperplanos.

ÁRBOLES BSP En diseño por ordenador es deseable que el dibujo de una escena sea correcta y rápida. Una manera sencilla de dibujar una escena correctamente es el algoritmo del pintor:

Esta subdivisión da lugar a una representación de la escena por medio de una estructura de datos del árbol conocida como árbol de BSP.

AUTORAS: JASNEYKA GARCIA ESPAÑA SILVIA

Los árboles-R no garantizan un buen rendimiento en el peor caso, pero en general se comportan bien con datos del mundo real. Sin embargo, recientemente, en 2004, se publicó un nuevo algoritmo que define el árbol R-de prioridad, que parece ser tan eficiente como los métodos actuales más eficientes y, al mismo tiempo, óptimo en el caso

ÁRBOLES-R

Cada nodo de un árbol-R tiene un número variable de entradas (hasta un máximo predefinido). Cada entrada de un nodo interno almacena dos datos: una forma de identificar a un nodo hijo y el conjunto límite de todas las entradas de ese nodo hijo.

Los árboles-R o R-árboles son estructuras de datos de tipo árbol similares a los árboles-B, con la diferencia de que se utilizan para métodos de acceso espacial, es decir, para indexar información

AUTORAS: JASNEYKA GARCIA ESPAÑA SILVIA

ÁRBOL DE FIBONACCI

Una variante de árbol binario con la propiedad que el orden de un nodo Se calcula como la sucesión de Fibonacci. El árbol de Fibonacci se define de la siguiente manera El árbol nulo (no contiene ningún nodo) es de orden 0.

Para n > 1, el árbol de Fibonacci El árbol que consta de un único de orden n consta de un nodo es de orden 1. nodo raíz con el árbol de Fibonacci de orden n-1 como hijo izquierdo y el árbol de Fibonacci de orden n-2 como hijo derecho. AUTORAS: JASNEYKA GARCIA ESPAÑA SILVIA

ÁRBOL BISELADO Esta estructura de datos fue inventada por Robert Tarjan y Daniel Sleator. Realiza operaciones básicas como pueden ser la inserción, la búsqueda y el borrado en un tiempo del orden de O (log n). Para muchas secuencias no uniformes de operaciones, el árbol biselado se comporta mejor que otros árboles de búsqueda, incluso cuando el patrón específico de la secuencia es

Un árbol biselado o árbol splay es un árbol binario de búsqueda auto-balanceable, con la propiedad adicional de que a los elementos accedidos recientemente se accederá más rápidamente en accesos posteriores.

AUTORAS: JASNEYKA GARCIA ESPAÑA SILVIA

Por eso, es importante definir cuáles mecanismos existen para pasar de un valor almacenado en el árbol a otro, y cómo se usan esos mecanismos.

Lo más simple muchas veces es suficiente; afortunadamente, basta definir un sub-árbol como un objeto que contiene una referencia hacia el valor almacenado en la jerarquía que representa la raíz del sub-árbol.

FUNCIONALIDAD DEL ÁRBOL Los árboles son útiles porque, además de almacenar valores, lo hacen imponiendo una estructura que permite luego lograr eficiencia en muchos algoritmos.

La diferencia principal entre árboles y sub-árboles es que los primeros nunca tendrán en su raíz una indicación de quien es su padre, pues por definición la raíz un árbol no tiene padre alguno

AUTORAS: JASNEYKA GARCIA ESPAÑA SILVIA

Gracias por su atención Gracias por su

Graciasatención por su atención Gracias por su atención Gracias por su atención Gracias por su atención Gracias por su atención

“Para ser un miembro inmaculado de un rebaño de ovejas, uno debe, sobre todas las cosas, primero ser una oveja.” Albert Einstein

AUTORAS: JASNEYKA GARCIA ESPAÑA SILVIA