Ing de sistemas

REPUBLICA BOLIVARIANA DE VENEZUELA
MINISTERIO DEL PODER POPULAR PARA LA DEFENSA
UNIVERSIDAD NACIONAL EXPERIMENTAL POLITECNICA DE LA
FUERZA ARMADA

INTEGRANTE:

MARIO REYES C.I: 16.899.411.

SECCIÓN:
6N3IS.

CÁTEDRA:
LENGUAJE DE PROGRAMACION II





BARQUISIMETO, ENERO 2010

DEFINICION DE ARBOLES
En ciencias de la computación, un árbol es una estructura de datoscomúnmente usada que emula la estructura de un árbol con un conjunto de nodos conectados. Cada nodo tiene cero o más nodos hijos, que están por debajo de él (en ciencias de la computación, al contrario que en la naturaleza, los árboles crecen hacia abajo, no hacia arriba), El nodo del cual uno nodo es hijo es llamado su nodo padre. Un hijo tiene como máximo un padre; un nodo sin padre es llamado nodo raíz(o simplemente raíz). Los nodos sin hijos son llamados hojas.
Formalmente, podemos definir un árbol de la siguiente forma:
* Caso base: un árbol con sólo un nodo (es a la vez raíz del árbol y hoja).
* Un nuevo árbol a partir de un nodo nr y k árboles de raíces con elementos cada uno, puede construirse estableciendo una relación padre-hijo entre nr y cada una de las raíces de los kárboles. El árbol resultante de nodos tiene como raíz el nodo nr, los nodos son los hijos de nr y el conjunto de nodos hoja está formado por la unión de los k conjuntos hojas iniciales. A cada uno de los árboles Ai se les denota ahora subárboles de la raíz.
OPERACIÓNES DE ARBOLES Y EJEMPLOS
Las operaciones comunes en árboles son:
* Enumerar todos los elementos.
* Buscar un elemento.
*Dado un nodo, listar los hijos (si los hay).
* Borrar un elemento.
* Eliminar un subárbol (algunas veces llamada podar).
* Añadir un subárbol (algunas veces llamada injertar).
* Encontrar la raíz de cualquier nodo.
Por su parte, la representación puede realizarse de diferentes formas. Las más utilizadas son:
* Representar cada nodo como una variable en el heap, con punterosa sus hijos y a su padre.
* Representar el árbol con un array donde cada elemento es un nodo y las relaciones padre-hijo vienen dadas por la posición del nodo en el array

TIPOS DE ARBOLES
Árbol binario: es una estructura de datos en la cual cada nodo siempre tiene un hijo izquierdo y un hijo derecho. No pueden tener más de dos hijos (de ahí el nombre "binario"). Si algún hijo tiene comoreferencia a null, es decir que no almacena ningún dato, entonces este es llamado un nodo externo

Árbol binario de búsqueda auto-balanceable o equilibrado: es un árbol binario de búsqueda que intenta mantener su altura, o el número de niveles de nodos bajo la raíz, tan pequeños como sea posible en todo momento, automáticamente. Esto es importante, ya que muchas operaciones en un árbol debúsqueda binaria tardan un tiempo proporcional a la altura del árbol, y los árboles binarios de búsqueda ordinarios pueden tomar alturas muy grandes en situaciones normales, como cuando las claves son insertadas en orden. Mantener baja la altura se consigue habitualmente realizando transformaciones en el árbol, como la rotación de árboles, en momentos clave.
Tiempos para varias operaciones en términosdel número de nodos en el árbol n:
Para algunas implementaciones estos tiempos son el peor caso, mientras que para otras están amortizados.
Estructuras de datos populares que implementan este tipo de árbol:
Árbol AVL: es un tipo especial de árbol binario ideado por los matemáticos rusos Adelson-Velskii y Landis. Fue el primer árbol de búsqueda binario auto-balanceable que se ideó.

Un ejemplode árbol binario equilibrado.

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 computación. 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....