¿Cuál es la forma más eficiente/elegante de analizar una mesa plana en un árbol?

Si usa conjuntos anidados (a veces denominados Traversal de Árbol de Pre-orden Modificado) puede extraer toda la estructura de árbol o cualquier subárbol dentro de ella en orden de árbol con una sola consulta, a costa de que las inserciones sean más caras, ya que necesita administrar columnas que describan una ruta en orden a través de la estructura de árbol.

Para django-mptt , utilicé una estructura como esta:

id  parent_id  tree_id  level  lft  rght
--  ---------  -------  -----  ---  ----
 1       null        1      0    1    14
 2          1        1      1    2     7
 3          2        1      2    3     4
 4          2        1      2    5     6
 5          1        1      1    8    13
 6          5        1      2    9    10
 7          5        1      2    11   12

Que describe un árbol que se ve así (con id representando cada item):

 1
 +-- 2
 |   +-- 3
 |   +-- 4
 |
 +-- 5
     +-- 6
     +-- 7

O, como un diagrama de conjuntos anidados que hace más obvio cómo funcionan los valores lft y rght:

 __________________________________________________________________________
|  Root 1                                                                  |
|   ________________________________    ________________________________   |
|  |  Child 1.1                     |  |  Child 1.2                     |  |
|  |   ___________    ___________   |  |   ___________    ___________   |  |
|  |  |  C 1.1.1  |  |  C 1.1.2  |  |  |  |  C 1.2.1  |  |  C 1.2.2  |  |  |
1  2  3___________4  5___________6  7  8  9___________10 11__________12 13 14
|  |________________________________|  |________________________________|  |
|__________________________________________________________________________|

Como puede ver, para obtener el subárbol completo para un nodo dado, en orden de árbol, simplemente tiene que seleccionar todas las filas que tienen valores lft y rght entre sus valores lft y rght. También es fácil recuperar el árbol de ancestros para un nodo dado.

La columna level es un poco de desnormalización por conveniencia más que nada y la {[11]]} column le permite reiniciar la numeración lft y rght para cada nodo de nivel superior, lo que reduce el número de columnas afectadas por inserciones, movimientos y eliminaciones, ya que las columnas lft y rght deben ajustarse en consecuencia cuando se realizan estas operaciones para crear o cerrar huecos. Hice algunas notas de desarrollo en el momento en que estaba tratando de envolver mi cabeza alrededor de las consultas necesarias para cada operación.

En términos de trabajar realmente con estos datos para mostrar un árbol, he creado un tree_item_iterator función de utilidad que, para cada nodo, debe darle suficiente información para generar cualquier tipo de pantalla que desea.

Más información sobre MPTT:

• Árboles en SQL
• Almacenamiento de Datos Jerárquicos en una Base de Datos
• Administración de Datos Jerárquicos en MySQL

A partir de Oracle 9i, puede usar CONNECT BY.

SELECT LPAD(' ', (LEVEL - 1) * 4) || "Name" AS "Name"
FROM (SELECT * FROM TMP_NODE ORDER BY "Order")
CONNECT BY PRIOR "Id" = "ParentId"
START WITH "Id" IN (SELECT "Id" FROM TMP_NODE WHERE "ParentId" = 0)

A partir de SQL Server 2005, puede usar una expresión recursiva de tabla común (CTE).

WITH [NodeList] (
  [Id]
  , [ParentId]
  , [Level]
  , [Order]
) AS (
  SELECT [Node].[Id]
    , [Node].[ParentId]
    , 0 AS [Level]
    , CONVERT([varchar](MAX), [Node].[Order]) AS [Order]
  FROM [Node]
  WHERE [Node].[ParentId] = 0
  UNION ALL
  SELECT [Node].[Id]
    , [Node].[ParentId]
    , [NodeList].[Level] + 1 AS [Level]
    , [NodeList].[Order] + '|'
      + CONVERT([varchar](MAX), [Node].[Order]) AS [Order]
  FROM [Node]
    INNER JOIN [NodeList] ON [NodeList].[Id] = [Node].[ParentId]
) SELECT REPLICATE(' ', [NodeList].[Level] * 4) + [Node].[Name] AS [Name]
FROM [Node]
  INNER JOIN [NodeList] ON [NodeList].[Id] = [Node].[Id]
ORDER BY [NodeList].[Order]

Ambos producirán los siguientes resultados.

Name
'Node 1'
'    Node 1.1'
'        Node 1.1.1'
'    Node 1.2'
'Node 2'
'    Node 2.1'

Es una pregunta bastante antigua, pero como tiene muchos puntos de vista, creo que vale la pena presentar una solución alternativa, y en mi opinión muy elegante.

Para leer una estructura de árbol puede usar Expresiones recursivas de Tabla Común (CTEs). Da la posibilidad de obtener toda la estructura del árbol a la vez, tener la información sobre el nivel del nodo, su nodo padre y el orden dentro de los hijos del nodo padre.

Déjame mostrarte cómo funcionaría esto en PostgreSQL 9.1.

1. Crear una estructura

   CREATE TABLE tree (
       id int  NOT NULL,
       name varchar(32)  NOT NULL,
       parent_id int  NULL,
       node_order int  NOT NULL,
       CONSTRAINT tree_pk PRIMARY KEY (id),
       CONSTRAINT tree_tree_fk FOREIGN KEY (parent_id) 
         REFERENCES tree (id) NOT DEFERRABLE
   );
   
   
   insert into tree values
     (0, 'ROOT', NULL, 0),
     (1, 'Node 1', 0, 10),
     (2, 'Node 1.1', 1, 10),
     (3, 'Node 2', 0, 20),
     (4, 'Node 1.1.1', 2, 10),
     (5, 'Node 2.1', 3, 10),
     (6, 'Node 1.2', 1, 20);
   

2. Escribir una consulta

   WITH RECURSIVE 
   tree_search (id, name, level, parent_id, node_order) AS (
     SELECT 
       id, 
       name,
       0,
       parent_id, 
       1 
     FROM tree
     WHERE parent_id is NULL
   
     UNION ALL 
     SELECT 
       t.id, 
       t.name,
       ts.level + 1, 
       ts.id, 
       t.node_order 
     FROM tree t, tree_search ts 
     WHERE t.parent_id = ts.id 
   ) 
   SELECT * FROM tree_search 
   WHERE level > 0 
   ORDER BY level, parent_id, node_order;
   

   Aquí están los resultados:

    id |    name    | level | parent_id | node_order 
   ----+------------+-------+-----------+------------
     1 | Node 1     |     1 |         0 |         10
     3 | Node 2     |     1 |         0 |         20
     2 | Node 1.1   |     2 |         1 |         10
     6 | Node 1.2   |     2 |         1 |         20
     5 | Node 2.1   |     2 |         3 |         10
     4 | Node 1.1.1 |     3 |         2 |         10
   (6 rows)
   

   Los nodos del árbol están ordenados por un nivel de profundidad. En la salida final los presentaríamos en las líneas siguientes.

   Para cada nivel, están ordenados por parent_id y node_order dentro del padre. Esto nos dice cómo presentarlos en el nodo output - link al padre en este orden.

   Tener tal estructura no sería difícil hacer una presentación realmente agradable en HTML.

   Los CTE recursivos están disponibles en PostgreSQL, IBM DB2, MS SQL Server y Oracle.

   Si desea leer más sobre consultas SQL recursivas, puede consultar la documentación de su DBMS favorito o leer mis dos artículos sobre este tema:

   • Hacerlo En SQL: Recorrido Recursivo Del Árbol
   • Conozca el poder de las consultas recursivas SQL

La respuesta de Bill es bastante buena, esta respuesta agrega algunas cosas que me hace desear respuestas roscadas TAN apoyadas.

De todos modos quería soportar la estructura de árbol y la propiedad Order. Incluí una sola propiedad en cada Nodo llamada leftSibling que hace lo mismo que Order está destinado a hacer en la pregunta original (mantener el orden de izquierda a derecha).

mysql> desc nodes ;
+-------------+--------------+------+-----+---------+----------------+
| Field       | Type         | Null | Key | Default | Extra          |
+-------------+--------------+------+-----+---------+----------------+
| id          | int(11)      | NO   | PRI | NULL    | auto_increment |
| name        | varchar(255) | YES  |     | NULL    |                |
| leftSibling | int(11)      | NO   |     | 0       |                |
+-------------+--------------+------+-----+---------+----------------+
3 rows in set (0.00 sec)

mysql> desc adjacencies;
+------------+---------+------+-----+---------+----------------+
| Field      | Type    | Null | Key | Default | Extra          |
+------------+---------+------+-----+---------+----------------+
| relationId | int(11) | NO   | PRI | NULL    | auto_increment |
| parent     | int(11) | NO   |     | NULL    |                |
| child      | int(11) | NO   |     | NULL    |                |
| pathLen    | int(11) | NO   |     | NULL    |                |
+------------+---------+------+-----+---------+----------------+
4 rows in set (0.00 sec)

Más detalles y código SQL en mi blog .

Gracias Bill su respuesta fue útil en conseguir ¡empezamos!

Bien dada la opción, estaría usando objetos. Crearía un objeto para cada registro donde cada objeto tiene una colección children y los almacenaría todos en una matriz assoc (/hashtable) donde el Id es la clave. Y blitz a través de la colección una vez, la adición de los niños a los campos de niños relevantes. Simple.

Pero debido a que no estás siendo divertido al restringir el uso de un buen OOP, probablemente iteraría basado en:

function PrintLine(int pID, int level)
    foreach record where ParentID == pID
        print level*tabs + record-data
        PrintLine(record.ID, level + 1)

PrintLine(0, 0)

Editar: esto es similar a un par de otras entradas, pero creo que es un poco más limpio. Una cosa que agregaré: esto es extremadamente intensivo en SQL. Es desagradable. Si tiene la opción, vaya a la ruta OOP.

Esto fue escrito rápidamente, y no es ni bonito ni eficiente (además de que autoboxes mucho, la conversión entre int y Integer es molesto!), pero funciona.

Probablemente rompa las reglas ya que estoy creando mis propios objetos, pero bueno, estoy haciendo esto como una distracción del trabajo real:)

Esto también asume que el ResultSet / table se lee completamente en algún tipo de estructura antes de comenzar a construir nodos, lo que no sería la mejor solución si tiene cientos de miles de filas.

public class Node {

    private Node parent = null;

    private List<Node> children;

    private String name;

    private int id = -1;

    public Node(Node parent, int id, String name) {
        this.parent = parent;
        this.children = new ArrayList<Node>();
        this.name = name;
        this.id = id;
    }

    public int getId() {
        return this.id;
    }

    public String getName() {
        return this.name;
    }

    public void addChild(Node child) {
        children.add(child);
    }

    public List<Node> getChildren() {
        return children;
    }

    public boolean isRoot() {
        return (this.parent == null);
    }

    @Override
    public String toString() {
        return "id=" + id + ", name=" + name + ", parent=" + parent;
    }
}

public class NodeBuilder {

    public static Node build(List<Map<String, String>> input) {

        // maps id of a node to it's Node object
        Map<Integer, Node> nodeMap = new HashMap<Integer, Node>();

        // maps id of a node to the id of it's parent
        Map<Integer, Integer> childParentMap = new HashMap<Integer, Integer>();

        // create special 'root' Node with id=0
        Node root = new Node(null, 0, "root");
        nodeMap.put(root.getId(), root);

        // iterate thru the input
        for (Map<String, String> map : input) {

            // expect each Map to have keys for "id", "name", "parent" ... a
            // real implementation would read from a SQL object or resultset
            int id = Integer.parseInt(map.get("id"));
            String name = map.get("name");
            int parent = Integer.parseInt(map.get("parent"));

            Node node = new Node(null, id, name);
            nodeMap.put(id, node);

            childParentMap.put(id, parent);
        }

        // now that each Node is created, setup the child-parent relationships
        for (Map.Entry<Integer, Integer> entry : childParentMap.entrySet()) {
            int nodeId = entry.getKey();
            int parentId = entry.getValue();

            Node child = nodeMap.get(nodeId);
            Node parent = nodeMap.get(parentId);
            parent.addChild(child);
        }

        return root;
    }
}

public class NodePrinter {

    static void printRootNode(Node root) {
        printNodes(root, 0);
    }

    static void printNodes(Node node, int indentLevel) {

        printNode(node, indentLevel);
        // recurse
        for (Node child : node.getChildren()) {
            printNodes(child, indentLevel + 1);
        }
    }

    static void printNode(Node node, int indentLevel) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < indentLevel; i++) {
            sb.append("\t");
        }
        sb.append(node);

        System.out.println(sb.toString());
    }

    public static void main(String[] args) {

        // setup dummy data
        List<Map<String, String>> resultSet = new ArrayList<Map<String, String>>();
        resultSet.add(newMap("1", "Node 1", "0"));
        resultSet.add(newMap("2", "Node 1.1", "1"));
        resultSet.add(newMap("3", "Node 2", "0"));
        resultSet.add(newMap("4", "Node 1.1.1", "2"));
        resultSet.add(newMap("5", "Node 2.1", "3"));
        resultSet.add(newMap("6", "Node 1.2", "1"));

        Node root = NodeBuilder.build(resultSet);
        printRootNode(root);

    }

    //convenience method for creating our dummy data
    private static Map<String, String> newMap(String id, String name, String parentId) {
        Map<String, String> row = new HashMap<String, String>();
        row.put("id", id);
        row.put("name", name);
        row.put("parent", parentId);
        return row;
    }
}

Asumiendo que usted sabe que los elementos raíz son cero, aquí está el pseudocódigo a la salida al texto:

function PrintLevel (int curr, int level)
    //print the indents
    for (i=1; i<=level; i++)
        print a tab
    print curr \n;
    for each child in the table with a parent of curr
        PrintLevel (child, level+1)


for each elementID where the parentid is zero
    PrintLevel(elementID, 0)

Puede emular cualquier otra estructura de datos con un hashmap, por lo que no es una limitación terrible. Al escanear de arriba a abajo, se crea un hashmap para cada fila de la base de datos, con una entrada para cada columna. Agregue cada uno de estos hashmaps a un hashmap "maestro", con la clave en el id. Si algún nodo tiene un "padre" que aún no haya visto, cree una entrada de marcador de posición para él en el hashmap maestro y rellénela cuando vea el nodo real.

Para imprimirlo, primero haga una simple profundidad pase a través de los datos, haciendo un seguimiento del nivel de sangría en el camino. Puede hacer esto más fácil manteniendo una entrada "hijos" para cada fila y rellenándola mientras escanea los datos.

En cuanto a si hay una "mejor" manera de almacenar un árbol en una base de datos, eso depende de cómo vas a usar los datos. He visto sistemas que tenían una profundidad máxima conocida que usaban una tabla diferente para cada nivel en la jerarquía. Eso tiene mucho sentido si los niveles en el árbol no son bastante equivalentes después de todas (las categorías de nivel superior son diferentes a las hojas).

Hay soluciones realmente buenas que explotan la representación btree interna de índices sql. Esto se basa en una gran investigación realizada alrededor de 1998.

Aquí hay una tabla de ejemplo (en mysql).

CREATE TABLE `node` (
  `id` int(10) unsigned NOT NULL AUTO_INCREMENT,
  `name` varchar(255) NOT NULL,
  `tw` int(10) unsigned NOT NULL,
  `pa` int(10) unsigned DEFAULT NULL,
  `sz` int(10) unsigned DEFAULT NULL,
  `nc` int(11) GENERATED ALWAYS AS (tw+sz) STORED,
  PRIMARY KEY (`id`),
  KEY `node_tw_index` (`tw`),
  KEY `node_pa_index` (`pa`),
  KEY `node_nc_index` (`nc`),
  CONSTRAINT `node_pa_fk` FOREIGN KEY (`pa`) REFERENCES `node` (`tw`) ON DELETE CASCADE
)

Los únicos campos necesarios para la representación en árbol son:

• tw: El índice de Reserva DFS de izquierda a derecha, donde root = 1.
• pa: La referencia (usando tw) al nodo padre, root tiene null.
• sz: El tamaño de la rama del nodo incluyendo sí mismo.
• nc: se utiliza como azúcar sintáctico. es tw + nc y representa el tw del "siguiente hijo" del nodo.

Aquí hay un ejemplo de población de 24 nodos, ordenada por tw:

+-----+---------+----+------+------+------+
| id  | name    | tw | pa   | sz   | nc   |
+-----+---------+----+------+------+------+
|   1 | Root    |  1 | NULL |   24 |   25 |
|   2 | A       |  2 |    1 |   14 |   16 |
|   3 | AA      |  3 |    2 |    1 |    4 |
|   4 | AB      |  4 |    2 |    7 |   11 |
|   5 | ABA     |  5 |    4 |    1 |    6 |
|   6 | ABB     |  6 |    4 |    3 |    9 |
|   7 | ABBA    |  7 |    6 |    1 |    8 |
|   8 | ABBB    |  8 |    6 |    1 |    9 |
|   9 | ABC     |  9 |    4 |    2 |   11 |
|  10 | ABCD    | 10 |    9 |    1 |   11 |
|  11 | AC      | 11 |    2 |    4 |   15 |
|  12 | ACA     | 12 |   11 |    2 |   14 |
|  13 | ACAA    | 13 |   12 |    1 |   14 |
|  14 | ACB     | 14 |   11 |    1 |   15 |
|  15 | AD      | 15 |    2 |    1 |   16 |
|  16 | B       | 16 |    1 |    1 |   17 |
|  17 | C       | 17 |    1 |    6 |   23 |
| 359 | C0      | 18 |   17 |    5 |   23 |
| 360 | C1      | 19 |   18 |    4 |   23 |
| 361 | C2(res) | 20 |   19 |    3 |   23 |
| 362 | C3      | 21 |   20 |    2 |   23 |
| 363 | C4      | 22 |   21 |    1 |   23 |
|  18 | D       | 23 |    1 |    1 |   24 |
|  19 | E       | 24 |    1 |    1 |   25 |
+-----+---------+----+------+------+------+

Cada resultado de árbol se puede hacer de forma no recursiva. Por ejemplo, para obtener una lista de ancestros del nodo en tw= ' 22 '

Ancestros

select anc.* from node me,node anc 
where me.tw=22 and anc.nc >= me.tw and anc.tw <= me.tw 
order by anc.tw;
+-----+---------+----+------+------+------+
| id  | name    | tw | pa   | sz   | nc   |
+-----+---------+----+------+------+------+
|   1 | Root    |  1 | NULL |   24 |   25 |
|  17 | C       | 17 |    1 |    6 |   23 |
| 359 | C0      | 18 |   17 |    5 |   23 |
| 360 | C1      | 19 |   18 |    4 |   23 |
| 361 | C2(res) | 20 |   19 |    3 |   23 |
| 362 | C3      | 21 |   20 |    2 |   23 |
| 363 | C4      | 22 |   21 |    1 |   23 |
+-----+---------+----+------+------+------+

Los hermanos y los hijos son triviales - solo use el orden de campos pa por tw.

Descendientes

Por ejemplo, el conjunto (rama) de nodos que tienen sus raíces en tw = 17.

select des.* from node me,node des 
where me.tw=17 and des.tw < me.nc and des.tw >= me.tw 
order by des.tw;
+-----+---------+----+------+------+------+
| id  | name    | tw | pa   | sz   | nc   |
+-----+---------+----+------+------+------+
|  17 | C       | 17 |    1 |    6 |   23 |
| 359 | C0      | 18 |   17 |    5 |   23 |
| 360 | C1      | 19 |   18 |    4 |   23 |
| 361 | C2(res) | 20 |   19 |    3 |   23 |
| 362 | C3      | 21 |   20 |    2 |   23 |
| 363 | C4      | 22 |   21 |    1 |   23 |
+-----+---------+----+------+------+------+

Notas complementarias

Esta metodología es extremadamente útil para cuando hay un número mucho mayor de lecturas que inserciones o actualizaciones.

Debido a que la inserción, movimiento o actualización de un nodo en el árbol requiere que el árbol se ajuste, es necesario bloquear la tabla antes de comenzar con la acción.

El costo de inserción / eliminación es alto porque el índice tw y sz (tamaño de rama) los valores deberán actualizarse en todos los nodos después del punto de inserción y para todos los ancestros respectivamente.

El movimiento de rama implica mover el valor tw de la rama fuera de rango, por lo que también es necesario desactivar las restricciones de clave foránea cuando se mueve una rama. Hay, esencialmente, cuatro consultas necesarias para mover una rama:

• Mueva la rama fuera del rango.
• Cerrar la brecha que dejó. (el árbol restante está ahora normalizado).
• Abrir la brecha donde se irá.
• Mueve la rama a su nueva posición.

Ajustar Consultas de Árbol

La apertura/cierre de huecos en el árbol es una subfunción importante utilizada por los métodos create/update/delete, así que la incluyo aquí.

Necesitamos dos parámetros: una bandera que represente si estamos reduciendo o aumentando el tamaño, y el índice tw del nodo. Así, por ejemplo tw=18 (que tiene un tamaño de rama de 5). Supongamos que estamos reduciendo el tamaño ( eliminando tw) - esto significa que estamos usando '-' en lugar de '+' en las actualizaciones del siguiente ejemplo.

Primero usamos una función ancestro (ligeramente alterada) para actualizar el valor sz.

update node me, node anc set anc.sz = anc.sz - me.sz from 
node me, node anc where me.tw=18 
and ((anc.nc >= me.tw and anc.tw < me.pa) or (anc.tw=me.pa));

Entonces necesitamos ajustar el tw para aquellos cuyo tw es más alto que la rama a eliminar.

update node me, node anc set anc.tw = anc.tw - me.sz from 
node me, node anc where me.tw=18 and anc.tw >= me.tw;

Entonces necesitamos ajustar el padre para aquellos cuyo tw del pa es más alto que la rama a eliminar.

update node me, node anc set anc.pa = anc.pa - me.sz from 
node me, node anc where me.tw=18 and anc.pa >= me.tw;

Si se pueden crear mapas hash anidados o matrices, entonces simplemente puedo bajar por la tabla desde el principio y agregar cada elemento a la matriz anidada. Debo rastrear cada línea hasta el nodo raíz para saber en qué nivel de la matriz anidada insertar. Puedo emplear la memoización para no tener que buscar al mismo padre una y otra vez.

Edit: Primero leería la tabla completa en una matriz, por lo que no consultará la BD repetidamente. Por supuesto, esto no será práctico si su la mesa es muy grande.

Después de construir la estructura, primero debo hacer un recorrido profundo a través de ella e imprimir el HTML.

No hay mejor manera fundamental de almacenar esta información usando una tabla (aunque podría estar equivocado ;), y me encantaría ver una mejor solución ). Sin embargo, si crea un esquema para emplear tablas de bases de datos creadas dinámicamente, entonces abre un mundo completamente nuevo a costa de la simplicidad y el riesgo de SQL hell ;).

Si los elementos están en orden de árbol, como se muestra en su ejemplo, puede usar algo como el siguiente ejemplo de Python:

delimiter = '.'
stack = []
for item in items:
  while stack and not item.startswith(stack[-1]+delimiter):
    print "</div>"
    stack.pop()
  print "<div>"
  print item
  stack.append(item)

Lo que esto hace es mantener una pila que representa la posición actual en el árbol. Para cada elemento de la tabla, hace estallar los elementos de la pila (cerrando los divs coincidentes) hasta que encuentre el padre del elemento actual. Luego muestra el inicio de ese nodo y lo empuja a la pila.

Si desea generar la salida del árbol usando sangría en lugar de anidada elementos, simplemente puede omitir las instrucciones print para imprimir los divs e imprimir un número de espacios igual a algún múltiplo del tamaño de la pila antes de cada elemento. Por ejemplo, en Python:

print "  " * len(stack)

También puede usar fácilmente este método para construir un conjunto de listas anidadas o diccionarios.

Editar: Veo por su aclaración que los nombres no estaban destinados a ser rutas de nodo. Eso sugiere un enfoque alternativo:

idx = {}
idx[0] = []
for node in results:
  child_list = []
  idx[node.Id] = child_list
  idx[node.ParentId].append((node, child_list))

Esto construye un árbol de matrices de tuplas (!). idx [0] representa la raíz (s) del árbol. Cada elemento en una matriz es una tupla de 2 que consiste en el propio nodo y una lista de todos sus hijos. Una vez construido, puede mantener idx[0] y descartar idx, a menos que desee acceder a los nodos por su ID.

Para extender la solución SQL de Bill, básicamente puede hacer lo mismo usando una matriz plana. Además, si todas sus cadenas tienen la misma longitud y se conoce el número máximo de hijos (por ejemplo, en un árbol binario), puede hacerlo utilizando una sola cadena (matriz de caracteres). Si usted tiene un número arbitrario de niños esto complica las cosas un poco... Tendría que revisar mis viejas notas para ver qué se puede hacer.

Entonces, sacrificando un poco de memoria, especialmente si su árbol es escaso y / o sin balancear, puede, con un poco de matemáticas de índice, acceder a todas las cadenas al azar almacenando su árbol, ancho primero en la matriz como así (para un árbol binario):

String[] nodeArray = [L0root, L1child1, L1child2, L2Child1, L2Child2, L2Child3, L2Child4] ...

Yo conozco la longitud de la cuerda, lo sabes

Ahora estoy en el trabajo, así que no puedo pasar mucho tiempo en él, pero con interés puedo obtener un poco de código para hacer esto.

Lo usamos para buscar en árboles binarios hechos de codones de ADN, un proceso construyó el árbol, luego lo aplanamos para buscar patrones de texto y cuando se encuentra, aunque matemáticas de índice (revers desde arriba) obtenemos el nodo de vuelta... muy rápido y eficiente, nuestro árbol rara vez tenía nodos vacíos, pero podíamos buscar gigabytes de datos en un santiamén.

Piense en usar herramientas nosql como neo4j para estructuras jerárquicas. por ejemplo, una aplicación en red como linkedin utiliza couchbase (otra solución nosql)

Pero use nosql solo para consultas a nivel de data-mart y no para almacenar / mantener transacciones