Árboles Binarios

En ciencias de la computación, un árbol binario es una estructura de datos en la cual cada nodo puede tener 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.

Definición de teoría de grafos

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 2». De esta forma solo 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'.

Tipos de árboles binarios

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.

Existen tipos de árboles binarios que suelen usarse para fines específicos, como:

• Árbol binario de búsqueda

• Árbol de Fibonacci

Complejidad

Insertar elementos en un árbol binario de búsqueda tiene una complejidad O(log n). Entonces, agregar n elementos a un árbol cualquiera da como resultado una complejidad O(n log n). Además, recorrer los elementos del árbol en inorden tiene complejidad O(n).

Búsqueda: para buscar el elemento 2, tenemos que atravesar todos los elementos (suponiendo que hacemos un recorrido primero en anchura). Por lo tanto, la búsqueda en el árbol binario tiene una complejidad en el peor de los casos de O(N).

Inserción: para insertar un elemento como hijo izquierdo de 2, tenemos que recorrer todos los elementos. Por lo tanto, la inserción en el árbol binario tiene una complejidad en el peor de los casos de O(N).

Eliminación: para eliminar el elemento 2, tenemos que atravesar todos los elementos para encontrar 2 (suponiendo que hacemos un recorrido primero en anchura). Por lo tanto, la eliminación en el árbol binario tiene una complejidad en el peor de los casos de O(N).