¿Los árboles están organizados por una estructura de "primer hijo, siguiente hermano"? ¿Si no, porque no?

Por lo general, las estructuras de datos de árbol se organizan de manera que cada nodo contenga punteros a todos sus elementos secundarios.

       +-----------------------------------------+
       |        root                             | 
       | child1            child2         child3 |
       +--+------------------+----------------+--+
          |                  |                |
+---------------+    +---------------+    +---------------+
|    node1      |    |     node2     |    |     node3     |
| child1 child2 |    | child1 child2 |    | child1 child2 |
+--+---------+--+    +--+---------+--+    +--+---------+--+
   |         |          |         |          |         |

Esto parece natural, pero viene con algunos problemas. Por ejemplo, cuando la cantidad de nodos secundarios varía, necesita algo como una matriz o una lista para administrar los elementos secundarios.

Al usar solo (primero) punteros secundarios (y siguientes) en su lugar, obtenemos algo que se ve así:

       +-------------------+
       |        root       |
       | child    sibling  +--->NULL
       +--+----------------+
          |             
+----------------+    +----------------+    +----------------+
|    node1       |    |     node2      |    |     node3      |
| child  sibling +--->| child  sibling +--->| child  sibling +--->NULL
+--+-------------+    +--+-------------+    +--+-------------+
   |                     |                     |

Obviamente, este tipo de estructura también puede representar árboles, pero también ofrece algunas ventajas. Lo más importante es que ya no tenemos que preocuparnos por la cantidad de nodos secundarios. Cuando se usa para un árbol de análisis, ofrece una representación natural para un término como "a + b + c + d + e" sin convertirse en un árbol profundo.

¿Las bibliotecas de colecciones ofrecen estructuras de árbol como esa? ¿Los analizadores utilizan tal estructura? Si no, ¿cuáles son las razones?

Los árboles, como las listas, son "tipos de datos abstractos" que se pueden implementar de diferentes maneras. Cada camino tiene sus ventajas y desventajas.

En el primer ejemplo, la principal ventaja de esta estructura es que puede acceder a cualquier elemento secundario en O (1). La desventaja es que agregar un niño a veces puede ser un poco más costoso cuando la matriz tiene que expandirse. Sin embargo, este costo es relativamente pequeño. También es una de las implementaciones más simples.

En el segundo ejemplo, la principal ventaja es que siempre agrega un hijo en O (1). La principal desventaja es que el acceso aleatorio a un niño cuesta O (n). Además, puede ser menos interesante para árboles enormes por dos razones: tiene una sobrecarga de memoria de un encabezado de objeto y dos punteros por nodo, y los nodos se distribuyen aleatoriamente sobre la memoria, lo que puede causar un gran intercambio entre el caché de la CPU y el memoria cuando se atraviesa el árbol, lo que hace que esta implementación sea menos atractiva para ellos. Sin embargo, esto no es un problema para árboles y aplicaciones normales.

Una última posibilidad interesante que no se mencionó es almacenar todo el árbol en una sola matriz. Esto conduce a un código más complejo, pero a veces es una implementación muy ventajosa en casos específicos, especialmente para grandes árboles fijos, ya que puede ahorrar el costo del encabezado del objeto y asignar memoria contigua.

Casi todos los proyectos que tienen algún modelo o documento editable tendrán una estructura jerárquica. Puede ser útil implementar el 'nodo jerárquico' como una clase base para diferentes entidades. A menudo, la lista enlazada (hermano menor, segundo modelo) es la forma natural en que crecen muchas bibliotecas de clases, sin embargo, los niños pueden ser de diversos tipos, y probablemente un " modelo de objeto " no es lo que consideramos cuando hablamos de árboles en general.

Mi implementación favorita de un árbol (nodo) de su primer modelo es una línea (en C #):

public class node : List<node> { /* props go here */ }

Herede de una lista genérica de su propio tipo (o herede de cualquier otra colección genérica de su propio tipo). Caminar es posible en una dirección: formar la raíz hacia abajo (los artículos no conocen a sus padres).

Árbol solo para padres

Otro modelo que no mencionó es el que cada niño tiene una referencia a su padre:

               null
                 |
       +---------+---------------------------------+
       |       parent                              |
       | root                                      |
       +-------------------------------------------+
          |                   |                |
+---------+------+    +-------+--------+    +--+-------------+
|     parent     |    |     parent     |    |     parent     |
|     node 1     |    |     node 2     |    |     node 3     |
+----------------+    +----------------+    +----------------+

Recorrer este árbol solo es posible al revés, normalmente todos estos nodos se almacenarán en una colección (matriz, tabla hash, diccionario, etc.) y se ubicará un nodo buscando en la colección criterios distintos de la posición jerárquica en el árbol que normalmente no sería de importancia primordial.

Estos árboles solo para padres se ven generalmente en aplicaciones de bases de datos. Es bastante fácil encontrar los hijos de un nodo con las instrucciones "SELECT * WHERE ParentId = x". Sin embargo, rara vez los encontramos transformados en objetos de clase árbol-nodo como tales. En las aplicaciones con estado completo (de escritorio), pueden incluirse en controles existentes de nodo de árbol. En aplicaciones sin estado (web), incluso eso puede ser poco probable. He visto que las herramientas de generador de clases de mapeo ORM arrojan errores de desbordamiento de pila al generar clases para tablas que tienen una relación con ellos mismos (risas), por lo que tal vez estos árboles no son tan comunes después de todo.

árboles navegables bidireccionales

Sin embargo, en la mayoría de los casos prácticos, es conveniente tener lo mejor de ambos mundos. Nodos que tienen una lista de hijos y además conocen a sus padres: árboles navegables bidireccionales.

                          null
                            |
       +--------------------+--------------------+
       |                  parent                 |
       |        root                             | 
       | child1            child2         child3 |
       +--+------------------+----------------+--+
          |                  |                |
+---------+-----+    +-------+-------+    +---+-----------+
|      parent   |    |     parent    |    |  parent       |
|    node1      |    |     node2     |    |     node3     |
| child1 child2 |    | child1 child2 |    | child1 child2 |
+--+---------+--+    +--+---------+--+    +--+---------+--+
   |         |          |         |          |         |

Esto trae muchos más aspectos a considerar:

• ¿Dónde implementar la vinculación y desvinculación de los padres?
  • deje que la lógica de negocios se encargue y deje el aspecto fuera del nodo (¡lo olvidarán!)
  • los nodos tienen métodos para crear hijos (no permite reordenar) (elección de Microsofts en su implementación System.Xml.XmlDocument DOM, que casi me volvió loco cuando lo encontré por primera vez)
  • Los nodos toman un padre en su constructor (no permite reordenar)
  • en todos los métodos add (), insert () y remove () y sus sobrecargas de los nodos (generalmente mi elección)
• Persistencia
  • Cómo caminar por el árbol cuando persiste (omita los enlaces de los padres, por ejemplo)
  • Cómo reconstruir el enlace bidireccional después de la deserialización (configurar a todos los padres nuevamente como una acción posterior a la deserialización)
• Notificaciones
  • Mecanismos estáticos (IsDirty flag), ¿manejan recursivamente en propiedades?
  • Eventos, burbujean a través de los padres, a través de los niños, o en ambos sentidos (considere la bomba de mensajes de Windows, por ejemplo).

Ahora para responder a la pregunta , los árboles navegables bidireccionales tienden a ser (en mi carrera y campo hasta ahora) los más utilizados. Algunos ejemplos son la implementación de Microsoft System.Windows.Forms.Control o System.Web.UI.Control en el marco .Net, pero también cada implementación de DOM (Modelo de objetos de documento) tendrá nodos que conozcan a sus padres, así como una enumeración. de sus hijos. La razón: facilidad de uso sobre facilidad de implementación. Además, generalmente son clases base para clases más específicas (XmlNode puede ser la base de las clases Tag, Attribute y Text) y estas clases base son lugares naturales para colocar arquitecturas genéricas de serialización y manejo de eventos.

Los árboles se encuentran en el corazón de muchas arquitecturas, y poder navegar libremente significa poder implementar soluciones más rápido.

No conozco ninguna biblioteca de contenedores que admita directamente su segundo caso, pero la mayoría de las bibliotecas de contenedores pueden admitir fácilmente ese escenario. Por ejemplo, en C ++ podría tener:

class Node;  // forward reference to satisfy the compiler
typedef std::list<Node*> NodeList;
class Node : public NodeList { /* . . . */ };  // a node is also a list

Node* n = new Node;
n->push_back(new Node);
Node* tree = new Node;
tree->push_back(new Node);
tree->push_back(n);

Los analizadores probablemente usen una estructura similar a esta, porque admite de manera eficiente nodos con números variables de elementos y elementos secundarios. No lo sé con certeza porque generalmente no leo su código fuente.

Uno de los casos en los que es preferible tener una matriz de niños es cuando necesita acceso aleatorio a los niños. Y esto generalmente ocurre cuando se clasifica a los niños. Por ejemplo, el árbol de jerarquía similar a un archivo puede usar esto para una búsqueda de ruta más rápida. O árbol de etiquetas DOM cuando el acceso al índice es muy natural

Otro ejemplo es cuando tener los "punteros" para todos los niños permite un uso más conveniente. Por ejemplo, ambos tipos que describió se pueden usar al implementar relaciones de árbol con una base de datos relacional. Pero el primero (maestro-detalle de padre a hijo en este caso) permitirá consultar con SQL general para obtener datos útiles, mientras que el segundo lo limitará significativamente.