¿Qué es un árbol binario?
Un árbol binario es un grafo especial en forma de árbol ramificado. Los árboles binarios tienen la particularidad de que sus nodos siempre tienen como máximo dos descendientes. Éstos se dividen sistemáticamente en un subárbol izquierdo y otro derecho.
Con este método, los archivos se almacenan en un Base de datos colocados y encontrados. El algoritmo encuentra los datos reduciendo repetidamente a la mitad el número de registros accesibles en última instancia hasta que sólo queda uno.
¿Cómo funciona un árbol binario?
En un árbol, los registros se almacenan en ubicaciones denominadas hojas. Este nombre deriva del hecho de que los registros siempre están presentes en los puntos finales; no hay nada más allá. Los puntos de ramificación se denominan nodos. El orden de un árbol resulta del número de ramas (llamadas hijos) por nodo. En un árbol binario siempre hay dos hijos por nodoEl número de hojas de un árbol binario es siempre una potencia de 2. El número de operaciones de acceso necesarias para alcanzar el conjunto de datos deseado se denomina profundidad del árbol.
En un árbol práctico, puede haber miles, millones o miles de millones de registros. No todas las hojas contienen necesariamente un registro, pero sí más de la mitad. Una hoja que no contiene ningún registro se denomina cero.
Uno de los lenguajes de programación más conocidos es Java. En Java, un árbol de búsqueda binario tiene una estructura de datos de árbol binario basada en nodos que tiene las siguientes propiedades: El subárbol izquierdo de un nodo contiene sólo nodos cuya clave es menor que la clave del nodo padre y el subárbol derecho, por otro lado, contiene sólo nodos con una clave mayor.
¿Cuáles son las aplicaciones de los árboles binarios?
Existen diferentes tipos de árboles binarios, con características únicas...:
- Árboles de búsqueda binarios representan los representantes más relevantes de los árboles binarios. Los nodos de estos árboles se ordenan linealmente en función de su clave. Con su ayuda se pueden realizar búsquedas más eficaces en la práctica.
- Árboles binarios completos son un tipo especial de árbol binario que no tiene hijos o tiene dos hijos. Esto significa que todos los nodos de este árbol o bien tienen dos nodos hijos del nodo padre o bien el propio nodo padre es el nodo hoja o el nodo externo. En otras palabras, un árbol binario completo es un árbol único en el que cada nodo tiene dos hijos, excepto el nodo externo. Aunque éste sólo tenga un hijo, dicho árbol binario no es un árbol binario completo. Aquí, el número de nodos hoja es igual al número de nodos internos +1. La ecuación es: L=I+1, donde L es el número de nodos hoja e I es el número de nodos internos.
- A árbol binario completo ha llenado completamente todos los niveles del árbol con nodos. Una excepción es el nivel más bajo del árbol. También en el último o más bajo nivel de este árbol, cada nodo debe estar en el lado izquierdo si es posible.
- Árboles binarios parcialmente ordenados se caracterizan porque sus raíces siempre representan un mínimo para el nodo del subárbol. En dirección a sus hojas, los valores de los nodos aumentan o, al menos, se mantienen en el mismo nivel.
- A El árbol binario se considera "perfecto denota cuando todos los nodos internos tienen exactamente dos hijos y cada nodo externo u hoja se encuentra en el mismo nivel o profundidad dentro de un árbol. Un árbol binario perfecto de altura 'h' tiene 2h - 1 nodos.
- Si la altura del árbol es O(logN), donde "N" es el número de nodos, de árboles binarios equilibrados hablado. En ellos, la altura del subárbol izquierdo y derecho de cada nodo debe variar como máximo en uno. Un árbol AVL y un árbol rojo-negro son algunos ejemplos comunes de estructuras de datos que pueden producir un árbol de búsqueda binario equilibrado.
- En árboles binarios degenerados o patológicos cada nodo interno sólo tiene un hijo. El rendimiento de estos árboles es similar al de una lista enlazada.
