Árboles binarios: definición, ejemplos

Actualizado por ultima vez el 21 de agosto de 2021, por Luis Benites.

Los árboles binarios son gráficos o estructuras de datos de árbol donde cada nodo (que se muestra como círculos en el gráfico de la izquierda) tiene hasta dos posibles ramas («hijos»). Estos se llaman la rama izquierda y la rama derecha o, a veces, el hijo izquierdo y el hijo derecho.
Aunque son estructuras relativamente simples, los árboles binarios son extremadamente útiles para modelar datos. Por ejemplo, los números racionales se pueden representar con una variante del árbol binario, llamada árbol de Calkin-Wilf . También se pueden utilizar para representar jerarquías y reflejar relaciones estructurales en los datos. Son flexibles; podemos mover ‘subárboles’ fácilmente dentro de un árbol según sea necesario. También se pueden buscar y analizar de manera muy eficiente por computadora.

Definiciones importantes para árboles binarios

El nodo superior de un árbol (8 en la imagen de arriba) se llama nodo raíz .

Árbol binario que muestra los nodos internos (azul) y los nodos externos (rojo).

Un nodo externo es uno sin ramas secundarias, mientras que un nodo interno tiene al menos una rama secundaria.

El tamaño de un árbol binario se refiere a la cantidad de nodos que tiene.

La distancia desde un nodo B hasta el nodo raíz es el nivel de B. La raíz está en el nivel 0, los hijos de la raíz están en el nivel 1, y así sucesivamente.

La suma de los niveles de cada uno de los nodos internos de un árbol se denomina longitud de ruta interna de ese árbol.

La suma de los niveles de cada uno de los nodos externos en un árbol se denomina longitud del camino externo .

El nivel máximo, entre todos los nodos externos, se denomina altura del árbol .

Más terminología de árboles binarios

Un árbol que tiene un nodo raíz se llama árbol enraizado. Si cada nodo tiene como máximo dos ramas, se convierte en un árbol binario y es un árbol binario enraizado .

Un árbol binario completo

Un árbol donde cada nodo (excepto las hojas) tiene 2 ramas se llama árbol binario completo . Los árboles binarios completos a veces también se denominan árboles binarios propios o planos.

Un árbol en el que todos los nodos interiores tienen dos ramas y todos los nodos con 0 ramas (nodos hoja) están al mismo nivel o tienen la misma profundidad se denomina árbol binario perfecto .

Un árbol binario que está completamente lleno, excepto potencialmente el nivel inferior, que se llena de izquierda a derecha, se denomina árbol binario completo . Los árboles binarios completos son importantes porque proporcionan la mejor relación entre la altura de un árbol y el número de nodos.

Referencias

Sedgewick y Flajolet. Una introducción al análisis de algoritmos. Recuperado el 24 de noviembre de 2017 de:
recuperado de http://aofa.cs.princeton.edu/60trees/.
Parlante, N. Árboles binarios. Recuperado el 24 de noviembre de 2017 de:
recuperado de http://cslibrary.stanford.edu/110/BinaryTrees.html

Tengo una Maestría en Ciencias en Estadística Aplicada y he trabajado en algoritmos de aprendizaje automático para empresas profesionales tanto en el sector de la salud como en el comercio minorista.

Deja un comentario

¿Qué es la prueba Tau de Thompson modificada? La prueba modificada de Thompson Tau es una forma de encontrar valores…
statologos comunidad-2

Compartimos información EXCLUSIVA y GRATUITA solo para suscriptores (cursos privados, programas, consejos y mucho más)

You have Successfully Subscribed!