TIPOS DE ÁRBOLES

-Árbol binario

En ciencias de la computación, un á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 como referencia a null, es decir que no almacena ningún dato, entonces este es llamado un nodo externo. En el caso contrario el hijo es llamado un nodo interno. Usos comunes de los árboles binarios son los árboles binarios de búsqueda, los montículos binarios y Codificación de Huffman.

Tipos de árboles binarios
Un árbol binario es un árbol con raíz en el que cada nodo tiene como máximo dos hijos.
Un árbol binario lleno es un árbol en el que cada nodo tiene cero o dos hijos.
Un árbol binario perfecto es un árbol binario lleno en el que todas las hojas (vértices con cero hijos) están a la misma profundidad (distancia desde la raíz, también llamada altura).

A veces un árbol binario perfecto es denominado árbol binario completo. Otros definen un árbol binario completo como un árbol binario lleno en el que todas las hojas están a profundidad n o n-1, para alguna n.


-Árbol binario de búsqueda auto-balanceable

En ciencias de la computación, un á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 de bú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érminos del número de nodos en el árbol n:

Operación Tiempo en cota superior asintótica
Búsqueda O(log n)
Inserción O(log n)
Eliminación O(log n)
Iteración en orden O(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
Árbol rojo-negro

-Árbol-B
En las ciencias de la computación, los árboles-B ó B-árboles son estructuras de datos de árbol que 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.

B-árbol es un árbol de búsqueda que puede estar vacío o aquel cuyos nodos pueden tener varios hijos, existiendo una relación de orden entre ellos, tal como muestra el dibujo.

Un árbol-B de orden M (el máximo número de hijos que puede tener cada nodo) es un árbol que satisface las siguientes propiedades:

1.Cada nodo tiene como máximo M hijos.
2.Cada nodo (excepto raíz y hojas) tiene como mínimo M/2 hijos.
3.La raíz tiene al menos 2 hijos si no es un nodo hoja.
4.Todos los nodos hoja aparecen al mismo nivel.
5.Un nodo no hoja con k hijos contiene k-1 elementos almacenados.
6.Los hijos que cuelgan de la raíz (r1, ···, rm) tienen que cumplir ciertas condiciones:
1.El primero tiene valor menor que r1.
2.El segundo tiene valor mayor que r1 y menor que r2, etc.
3.El último hijo tiene valor mayor que rm.


-Árbol multicamino

Los árboles multicamino o árboles multirrama son estructuras de datos de tipo árbol usadas en computación.
Un árbol multicamino posee un grado g mayor a dos, donde cada nodo de información del árbol tiene un máximo de g hijos.

Sea un árbol de m-caminos A, es un árbol m-caminos si y solo si:

A está vacío
Cada nodo de A muestra la siguiente estructura: [nClaves,Enlace0,Clave1,...,ClavenClaves,EnlacenClaves]
nClaves es el número de valores de clave de un nodo, pudiendo ser: 0 <= nClaves <= g-1 Enlacei, son los enlaces a los subárboles de A, pudiendo ser: 0 <= i <= nClaves Clavei, son los valores de clave, pudiendo ser: 1 <= i <= nClaves Clavei < g =" (V,A,j" g1 =" (V1," v1 =" {1," a1 =" {(1," g2 =" (V2," v2 =" {1," a2 =" {(1," g3 =" (V3," v3 =" {1," a3 =" {">, <2,>, <2,> }

Gráficamente estas tres estructuras de vértices y arcos se pueden representar de la siguiente manera:


Algunos de los principales tipos de grafos son los que se muestran a continuación:

•Grafo regular: Aquel con el mismo grado en todos los vértices. Si ese grado es k lo llamaremos k-regular.

•Grafo bipartito: Es aquel con cuyos vértices pueden formarse dos conjuntos disjuntos de modo que no haya adyacencias entre vértices pertenecientes al mismo conjunto

•Grafo completo: Aquel con una arista entre cada par de vértices. Un grafo completo con n vértices se denota Kn.

•Un grafo bipartito regular: se denota Km,n donde m, n es el grado de cada conjunto disjunto de vértices.

•Grafo nulo: Se dice que un grafo es nulo cuando los vértices que lo componen no están conectados, esto es, que son vértices aislados.

•Grafos Isomorfos: Dos grafos son isomorfos cuando existe una correspondencia biunívoca (uno a uno), entre sus vértices de tal forma que dos de estos quedan unidos por una arista en común.

•Grafos Platónicos: Son los Grafos formados por los vértices y aristas de los cinco sólidos regulares (Sólidos Platónicos), a saber, el tetraedro, el cubo, el octaedro, el dodecaedro y el icosaedro.

(GUERRA, 2010)

GUERRA, J. (18 de 2 de 2010). MATEMATICAS DISCRETAS. Recuperado el 21 de 05 de 2014, de ARBOLES Y GRAFOS: http://matematicasdiscretasjota.blogspot.mx/2010/02/arboles-y-grafos_18.html