Diferencia entre árboles ordenados y desordenados (rooteados)

Question

Estoy leyendo algoritmos de Robert Sedwick. Algunas definiciones del libro se muestran a continuación.

Un árbol (también un árbol ordenado) es un nodo (llamado raíz) conectado a una secuencia de árboles disjuntos. Tal secuencia se llama bosque.

Un árbol enraizado (o árbol desordenado) es un nodo (llamado raíz) conectado a un conjunto múltiple de árboles enraizados. (Un conjunto múltiple de este tipo se llama un bosque desordenada .

Mis preguntas sobre el texto anterior están

1. estoy teniendo difficutlty en la comprensión por encima de DEFINCIONES. ¿Puede alguien por favor explique con ejemplos.
2. ¿Qué quiere decir el autor de árboles disjuntos?
3. ¿Qué quiere decir el autor de árboles multiconjuntos arraigada?

Gracias por su tiempo y ayuda

Answer 1

1. Un árbol con esta definición es más o menos lo que normalmente entendemos por árbol: un nodo conectado a una secuencia ordenada de (sub) árboles. Es una definición recursiva: si la secuencia está vacía, el nodo se llama hoja, y si no, cada uno de los árboles en la secuencia también es "un nodo conectado a una secuencia ordenada de (sub) árboles".
2. Por disjuntos el autor significa que los subárboles no tienen nodos en común.
3. La definición significa que los subárboles de un árbol enraizado no están en un orden particular y que pueden repetirse. Un multiset es como un conjunto que permite múltiples.

Un árbol ordenado (un "árbol" de la primera definición) tiene los subárboles en un orden particular, y la secuencia del subárbol no puede contener el mismo árbol dos veces, porque los subárboles deben estar disjuntos. Un árbol enraizado no tiene estas restricciones; según esta definición, una raíz puede tener un subárbol dos veces, en una estructura que se asemeja a un ciclo.

No tengo el libro de Sedwick para verificar si esta definición tiene sentido o por qué; una definición más común o árbol enraizado usaría un conjunto normal para subárboles, en lugar de un conjunto múltiple. Tal vez la intención es permitir enlaces múltiples entre un nodo y sus hijos, mientras se rechazan otros tipos de ciclos, como los enlaces entre hermanos y primos.