Árbol binario
Keywords: Árbol binario, B-Árbol, Ciencias de la computación, Estructura de datos, Lenguaje de programación, Teoría de grafos, Árbol (programación), Árbol rojo-negro
- El árbol binario también es una composición poética. Véase árbol binario (poesía).
En ciencias de la computación, un árbol binario es una arbol ordenado estructura de datos en el cual cada nodo tiene como máximo dos hijos. Típicamente los nodos hijos son llamados izquierdo y derecho. Usos comunes de los árboles binarios son los árboles binarios de busqueda y los heaps binarios. right|192px|thumb|Ejemplo sencillo de árbol binario
Definicion de teoría de grafos
En teoría de grafos, se usa la siguiente definición: «Un árbol binario es un grafo conectado acíclico tal que el grado de cada vértice no es mayor a 3.»
Un arbol 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 reusamos el requirimiento de la conectividad, permitiendo múltiples componentes conectados en el grafo, llamaremos a esta última estructura un bosque.
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 completo es un árbol en el que cada nodo tiene cero o dos hijos.
- Un árbol binario perfecto es un árbol binario completo en el que todas las hojas (vertices con cero hijos) tienen la misma profundidad (distancia desde la raiz, tambien llamada altura)
- A veces un árbol binario perfecto es denominado árbol binario completo. Otros lo definen como un árbol binario lleno en el que todos los hijos son de profundidad n o n-1, para algún n.
Métodos para almacenar árboles binarios
Los árboles binarios pueden ser construidos desde lenguajes de programación primitivos en muchas formas. En un lenguaje con estructuras y referencias, los árboles binarios son típicamente implementados construyendo con una estructura de tres nodos que contiene algunos datos y referencias a su hijo izquierdo y a su hijo derecho.
Véase también: Árbol (programación), B-Árbol, Partición de espacio binario, Árbol rojo-negro
Arbol binario