Árbol (estructura de datos)
En informática , un árbol es un tipo de datos abstractos ampliamente utilizado que simula una estructura de árbol jerárquico , con un valor raíz y subárboles de hijos con un nodo principal , representado como un conjunto de nodos vinculados .
Una estructura de datos de árbol se puede definir recursivamente como una colección de nodos, donde cada nodo es una estructura de datos que consta de un valor y una lista de referencias a nodos. El inicio del árbol es el "nodo raíz" y los nodos de referencia son los "hijos". No se duplica ninguna referencia y ninguna apunta a la raíz.
Alternativamente, un árbol se puede definir de forma abstracta como un todo (globalmente) como un árbol ordenado , con un valor asignado a cada nodo. Ambas perspectivas son útiles: si bien un árbol se puede analizar matemáticamente como un todo, cuando se representa como una estructura de datos, generalmente se representa y se trabaja con él por separado por nodo (en lugar de como un conjunto de nodos y una lista de adyacencia de bordes entre nodos) . , como se puede representar un dígrafo , por ejemplo). Por ejemplo, mirando un árbol como un todo, se puede hablar del "nodo padre" de un nodo dado, pero en general, como estructura de datos, un nodo dado solo contiene la lista de sus hijos pero no contiene una referencia. a su padre (si lo hay).
Un nodo es una estructura que puede contener un valor o condición, o representar una estructura de datos separada (que podría ser un árbol propio). Cada nodo en un árbol tiene cero o más nodos secundarios , que están debajo de él en el árbol (por convención, los árboles se dibujan creciendo hacia abajo). Un nodo que tiene un hijo se llama nodo padre del hijo (o superior ). Un nodo tiene como máximo un padre, pero posiblemente muchos nodos antepasados , como el padre del padre. Los nodos secundarios con el mismo padre son nodos hermanos .
Un nodo interno (también conocido como nodo interno , inodo para abreviar o nodo de rama ) es cualquier nodo de un árbol que tiene 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.
El nodo superior de un árbol se denomina nodo raíz . Dependiendo de la definición, se puede requerir que un árbol tenga un nodo raíz (en cuyo caso todos los árboles no están vacíos), o se le puede permitir que esté vacío, en cuyo caso no necesariamente tiene un nodo raíz. Al ser el nodo superior, el nodo raíz no tendrá un padre. Es el nodo en el que comienzan los algoritmos del árbol, ya que como estructura de datos solo se puede pasar de padres a hijos. Tenga en cuenta que algunos algoritmos (como la búsqueda posterior al orden en profundidad) comienzan en la raíz, pero primero visitan los nodos de hoja (acceden al valor de los nodos de hoja), solo para visitar la raíz en último lugar (es decir, primero acceden a los elementos secundarios de los nodos). root, pero solo acceda al último valor de la raíz). Se puede llegar a todos los demás nodos desde él siguiendo los bordes o enlaces. (En la definición formal, cada ruta también es única). En los diagramas, el nodo raíz se dibuja convencionalmente en la parte superior. En algunos árboles, como heaps , el nodo raíz tiene propiedades especiales. Cada nodo de un árbol puede verse como el nodo raíz del subárbol enraizado en ese nodo.
.svg)
