data structures - complexity - ¿Qué es un "nodo interno" en un árbol de búsqueda binario?
binary tree online (13)
Estoy buscando en internet una definición del término "nodo interno". No puedo encontrar una definición sucinta Cada fuente que estoy viendo utiliza el término sin definirlo, y el uso no arroja una definición adecuada de lo que es realmente un nodo interno.
Aquí están los dos lugares que he estado buscando principalmente: http://planetmath.org/encyclopedia/ExternalNode.html supone que los nodos internos son nodos que tienen dos subárboles que no son nulos, pero no dice qué nodos en el el árbol original es interno vs. externo.
http://www.math.bas.bg/~nkirov/2008/NETB201/slides/ch06/ch06-2.html parece insinuar que los nodos internos solo existen en árboles binarios apropiados y no proporciona mucha información útil sobre ellos .
¿Qué es realmente un nodo interno?
Un nodo interno o nodo interno es cualquier nodo de un árbol que tiene nodos secundarios y, por lo tanto, no es un nodo hoja. Un nodo intermedio entre la raíz y los nodos hoja se denomina nodo interno.
De "Introducción a los algoritmos", editado por Thomas H Cormen:
Un nodo sin hijo se llama ''nodo de hoja''. Un nodo no hoja es un ''nodo interno''.
El nodo interno Ya no incluye la raíz. Y un árbol binario completo como la terminología le dice a cada nodo interno que debe tener 2 nodos exactos. Pero en un árbol binario simple cada nodo interno tiene casi 2 nodos, es decir, no puede contener más de 2 nodos, pero menos de 2 es permisible
Generalmente, un nodo interno es cualquier nodo que no es una hoja (un nodo sin hijos).
En los árboles binarios extendidos (también árboles de comparación), todos los nodos internos tienen dos hijos porque cada nodo interno corresponde a una comparación que debe hacerse [El arte de la programación de computadoras (TAoCP) vol.3 Ordenación y búsqueda, discusión y figura en la sección 5.3 .1, p.181 (ed.2). Por cierto, el uso de estos árboles para representar emparejamientos (y byes) para torneos de eliminación se aborda en la sección 5.4.1 de este material.]
El diagrama de Vinko refleja esta distinción, aunque el nodo raíz también es siempre un nodo interno o un nodo hoja, además de ser el único nodo sin padre.
Hay una discusión más amplia en el tratamiento de Knuth de las estructuras de información y las propiedades de los árboles [TAoCP vol.1 Algoritmos Fundamentales, discusión de longitudes de camino en árboles en la sección 2.3.4.5, pp 399-406 (ed.3) incluyendo ejercicios (muchos en la parte posterior del libro)].
Es útil observar que los árboles de búsqueda binarios (donde los nodos internos también tienen valores únicos y tienen hasta dos hijos) son algo diferentes [TAoCP vol.3, sección 6.2.2]. La nomenclatura aún funciona, sin embargo.
La respuesta más votada es incorrecta. Según las estructuras matemáticas para la informática de Judith Gersting, un nodo interno es "Un nodo sin hijos se llama una hoja del árbol, todas las no hojas se llaman nodos internos "
Entonces, por ejemplo (I = NODO INTERNO): I / / * I // * *
Nodo interno: un nodo con al menos un hijo. Nodo externo: un nodo sin hijos.
Nodo interno: un nodo que no es la raíz y tiene al menos un elemento secundario.
Por lo que yo entiendo, es un nodo que no es una hoja.
Un árbol binario puede tener cero, un nodo y puede tener un máximo de dos nodos. Un árbol binario tiene un nodo izquierdo y un nodo derecho en sí mismo.
Un nodo interno (también conocido como nodo interno, indo para abreviar o nodo de rama) es cualquier nodo de un árbol que tenga nodos secundarios. De manera similar, un nodo externo (también conocido como nodo externo, nodo hoja o nodo terminal) es cualquier nodo que no tiene nodos secundarios.
rápido y simple
Un nodo interno o nodo interno es cualquier nodo de un árbol que tiene nodos secundarios y, por lo tanto, no es un nodo hoja. Un nodo intermedio entre la raíz y los nodos hoja se denomina nodo interno.
Un nodo que tiene al menos un hijo.
I ROOT (root is also an INTERNAL NODE, unless it is leaf)
/ /
I I INTERNAL NODES
/ / /
o o o EXTERNAL NODES (or leaves)
Como muestra la maravillosa imagen, los nodos internos son nodos ubicados entre la raíz del árbol y las hojas. Tenga en cuenta que la raíz también es un nodo interno, excepto en el caso de que sea el único nodo del árbol.
Lo que se dice en uno de los sitios acerca de que un nodo interno debe tener dos hijos es que el árbol sea un árbol binario completo, no que el nodo sea interno.