Una digráfica \(T(V,E)\) es un árbol dirigido siempre que la gráfica no dirigida asociada a \(T\) sea un árbol.

Lo anterior nos dice también que si tenemos un árbol (no dirigido) y orientamos sus aristas, sin importar la forma en que lo hagamos, lo que obtendremos será un árbol dirigido.

Para los vértices de digráficas, en particular los de árboles dirigidos, podemos descomponer el grado en grado de entrada, que denotamos por \(\hbox{ge}(v)\) y grado de salida, que denotamos por \(\hbox{gs}(v)\). Así, el número total de aristas que concurren en un vértice será la suma de las aristas que entran mas las que salen, es decir, para todo \(v\in V\) tendremos que \(\hbox{grad}(v)=\hbox{ge}(v)+\hbox{gs}(v)\). Estos dos atributos nos permiten definir con precisión un nuevo tipo de árbol dirigido que de hecho incluye al árbol de búsqueda binario que utilizamos recientemente.

Así pues, un árbol con raíz es un árbol dirigido \(T(V,E)\) que tiene un vértice especial \(r\in V\), que llamaremos raíz, tal que \(\hbox{ge}(r)=0\), mientras que el resto de los vértices \(v\in V, v\neq r\), son tales que \(\hbox {ge}(v)=1\).

La siguiente figura muestra tres árboles dirigidos.

El arbol de nodos azules corresponde a la parte inicial del árbol binario de búsqueda, que ya hemos referido, en el que se encuentran marcados algunos vértices con los valores numéricos correspondientes a la búsqueda. La raíz de este árbol es el vértice superior. En todos los vértices restantes el grado de entrada es uno. Se trata de un árbol con raíz.

El árbol cuyos vértices están etiquetados con letras mayúsculas es un árbol con raíz, misma que está en el vértice \(C\).

Sin embargo, en el árbol de la parte inferior, con vértices etiquetados usando letras minúsculas, los vértices \(a,c,f,i,l\) y \(m\) son todos ellos candidatos a ser raíz, en tanto su grado de entrada es cero. Lo anterior es suficiente para descartarlo como árbol con raíz, ya que ésta no es única.

Los árboles con raíz son la base para generar las estructuras de datos de sistemas de archivos digitales y de sistemas de directorio de acceso rápido como LDAP (siglas del inglés Lightweight Directory Access Protocol). Son también una herramienta indispensable para la taxonomía y la genética.

En los árboles con raíz es posible cosiderar niveles, mismos que vienen dados por la distancia entre la raíz y los vértices, medida en número de aristas. Pertenecerán al mismo nivel los vértices que estén a la misma distancia de la raíz. También podemos interpretar a las aristas como relaciones de parentezco. No nos debe costar trabajo identificar a los vértices que son padres de otros, que serán los hijos de los primeros. Podemos hablar de hermanos, abuelos, nietos, tíos, primos y así sucesivamente. En general, dado un vértice \(v\) podemos asociarle los conjuntos de descendientes y ascendentes, donde los primeros componen el sub-árbol cuya raíz es \(v\), y los segundos el camino desde \(v\) hasta la raíz del árbol.

Árboles m-arios

Ya hemos ejemplificado un árbol binario que hemos referido en varias ocasiones. Este tipo de árboles está caracterizado por una acotación sobre el grado de salida de sus vértices. En un árbol binario \(T(V,E)\) tendremos siempre que \(\hbox{gs}(v)\leq2\) para todo \(v\in V\).

Los vértices del árbol binario en la parte derecha de la figura de arriba cumplen con la restricción \(\hbox{gs}(v)\leq2\), de hecho \(\hbox{gs}(v)=2\). Cuando se da esta igualdad decimos que el árbol está completo.

Como una generalización de lo anterior, dado un entero \(m\geq2\), un árbol \(m\)-ario \(T(V,E)\) es aquel en el que \(\hbox{gs}(v)\leq m\) para todo \(v\in V\). Si se da la igualdad el árbol será además completo.

Es importante no confundir el caso particular en el que todos los niveles están completos con que el árbol esté completo. Por ejemplo, si en el árbol derecho de la figura de arriba eliminamos una pareja de hermanos del último nivel, entonces el árbol permanece completo aunque el último nivel no lo esté.

En la misma figura de arriba el árbol cuyos vértices están etiquetados con letras mayúsculas es un árbol 7-ario (o heptal) incompleto con tres niveles (incluyendo el nivel de la raíz).

En el siguiente espacio puedes experimentar con árboles dirigidos hasta de 30 vértices generados aleatoriamente y modificarlos para obtener un árbol con raíz. Los puntos rojos pueden desplazarse de la misma forma que en la sección de Inicio y oprimiendo sobre los puntos grises se cambia el sentido de la arista. Recuerda que lo que define a este tipo de árboles es que hay un vértice, y solo uno, que tiene grado de entrada cero y el resto tienen todos grado de entrada uno. Puedes seleccionar el número de vértices en la parte inferior izquierda del espacio y también redibujar la gráfica presionando el botón correspondiente.

Al trabajar algunos ejemplos en la escena anterior, podemos notar que es posible escoger cualquiera de los vértices como raíz y entonces reorientar las aristas para obtener el árbol con la raíz escogida inicialmente.