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.
(La codificación de Huffman se utiliza a menudo en algún otro método de comprensión. Como la deflación y códec multimedia como JPEG y MP3 que tienen una cuantificación digital).
En teoría de grafos, se usa la siguiente definición: «Un árbol binario es un grafo conexo, acíclico y no dirigido tal que el grado de cada vértice no es mayor a 3». De esta forma sólo existe un camino entre un par de nodos.
Un árbol binario con enraizado es como un grafo que tiene uno de sus vértices, llamado raíz, de grado no mayor a 2. Con la raíz escogida, cada vértice tendrá un único padre, y nunca más de dos hijos. Si rehusamos el requerimiento de la conectividad, permitiendo múltiples componentes conectados en el grafo, llamaremos a esta última estructura un bosque.
Tienen una corta pero importante historia. A finales de los años 60, fabricantes de computadores y grupos de investigación independientes, compitieron en el desarrollo de sistemas de archivo de propósito general y los llamados "métodos de acceso" para sus máquinas. La Sperry Univac Corporation (junto con la Case Western Reserve University), H. Chiat, M. Schwartz y otros, desarrollaron e implementaron un sistema el cual llevaba a cabo las operaciones de
Independientemente, B. cole, S. Radcliffe, M. Kauffman y otros, desarrollaron un sistema similar al de Control Data Corporation (junto con la Stanford University). R. Bayer y E. McCreight, hasta entonces, en los Boeing Scientific Research Labs, propusieron un mecanismo externo para el ndice con un costo relativamente bajo para la mayoría de las operaciones de búsqueda, inserción, actualización y borrado de datos. Lo llamaron Árbol B1. De aquí nace el Árbol B que todos conocemos.
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.
Un árbol binario es un árbol en el que ningún nodo puede tener más de dos subárboles. En un árbol binario cada nodo puede tener cero, uno o dos hijos (subárboles). Se conoce el nodo de la izquierda como hijo izquierdo y el nodo de la derecha como hijo derecho.
se usan en una inmensa gama de sistemas informáticos. Y constituyen una herramienta muy eficiente para administrar grandes volúmenes de datos. Es por ésto, que los Arboles B constituyen el núcleo de los motores de Búsqueda de las Bases de Datos.
Veamos un ejemplo real. Si como Ingenieros en Computación se nos encarga administrar la Base de Datos de todos los sufragantes de Honduras (los cuales son cientos de miles), entonces eberíamos usar una Estructura de Datos adecuada a nuestra problemática. Sabiendo que se nos pide Buscar personas, Verificar domicilios, Inscribir un sufragante, Eliminar a un sufragante, etc. La manera más idónea de hacerlo es usar una estructura dinámica y capaz de almacenar grandes cantidades de datos. Es por eso que elegimos los Arboles B, porque nos entregan una eficaz administración de los datos de muchas personas.
Además se usan en aplicaciones de Administración de Memoria, los Sistemas Operativos deben realizar un manejo óptimo de los datos en memoria primaria. Los Arboles B+ son muy usados en este ámbito.
En mi opinion las aplicaciones de los arboles binarios son muy variadas ya que se les puede utilizar para representar una estructura en la cual es posible tomar decisiones con dos opciones en distintos puntos, pero siento qiue poder implementarlos es complicado y repsentan ciertas desventajas como: Pero este tipo de árboles tienen varias desventajas:
Es difícil construir un árbol binario de búsqueda perfectamente equilibrado.
El número de consultas en el árbol no equilibrado es impredecible.
Y además el número de consultas aumenta rápidamente con el número de registros a ordenar..
http://msdn.microsoft.com/en-us/library/bb397951.aspx
http://msdn.microsoft.com/es-es/library/bb882536(v=VS.90).aspxhttp://articulos.conclase.net/?tema=algoritmos&art=arbolesb&pag=000
http://usuarios.multimania.es/arbolesbpro/historia.htm
http://es.wikipedia.org/wiki/%C3%81rbol_binario
Muy buen post. y es cierto, los AB son árboles muy útiles pero su implementación suele ser algo compleja.
ResponderEliminar