El dibujo que proporcionó anteriormente no es un árbol porque hay dos rutas desde el nodo superior en la primera capa del árbol (nodo raíz) hasta el nodo de la hoja central en la tercera capa. Eso viola la definición de un árbol en la teoría de grafos, que establece que un árbol debe tener solo una ruta entre dos vértices.
Google define un árbol binario como “una estructura de datos de árbol enraizada en la que un registro está vinculado a dos registros sucesores”.
- ¿Por qué el ensacado funciona tan bien para los árboles de decisión, pero no para los clasificadores lineales?
- Cómo comenzar a aprender o fortalecer mi conocimiento de estructuras de datos y algoritmos
- ¿Cuál es el algoritmo de clasificación más rápido para una matriz de números grandes (hasta 1,000,000,000,000)?
- ¿Cuáles son algunos de los buenos libros sobre Algoritmos de aprendizaje automático de árbol de decisión?
- ¿Abusaron los escritores de los límites de la ecuación 3.10 del CLRS?
En la práctica, se supone que un árbol binario tiene una raíz (por lo tanto, “enraizada”) y no podría tener ningún nodo con varios padres. Esto se debe a que en el caso de que tuviera un nodo con varios padres, uno o ambos de los siguientes dos casos que violan la definición de un árbol binario siempre serían ciertos:
Si hay un nodo con dos padres, ya sea:
1) Similar al dibujo anterior, siempre habrá dos caminos desde el nodo raíz al nodo con dos padres y, por lo tanto, no sería un árbol.
o
2) Termina con un gráfico que no es un árbol enraizado (ejemplo que se muestra en el dibujo a continuación), en cuyo caso no hay múltiples rutas al nodo con dos padres desde las raíces como antes, sino que terminamos con más de una raíz (naranja y amarilla), violando la propiedad de que debe ser un árbol enraizado.
Ambos casos no son mutuamente excluyentes. A continuación incluyo un ejemplo donde ocurren ambas violaciones: