Простой обход дерева и быстрый доступ к случайным узлам

Question

Отредактировано после примечания Алекса Таггарта ниже.

Я использую молнию, чтобы легко перемещаться и редактировать дерево, которое может вырасти до многих тысяч узлов. Каждый узел является неполным, когда он сначала создается. Данные будут добавляться/удаляться все время в случайных позициях, листовые узлы будут заменены ветвями и т. Д.

Дерево может быть очень неуравновешенное. Быстрый случайный доступ к узлу также важен.

Реализация должна состоять в том, чтобы пересечь дерево с помощью застежки-молнии и создать хеш-таблицу узлов, проиндексированных ключом. Само собой разумеется, выше было бы крайне неэффективно, как: должны быть созданы

любые изменения

• 2 копии каждого узла должны быть последовательно отражается между структурами данных (2 дерева и HashMap).

Вкратце, есть ли эффективный способ времени/пространства для объединения легкости перемещения/обновления с помощью молнии и быстрого доступа к хеш-таблице в clojure?

Answer 1

Структуры данных Clojure являются постоянными и используют структурное разделение. Это означает, что операции, такие как добавление, удаление или накопление, не так эффективны, как вы описываете. Стоимость памяти будет минимальной, поскольку вы не дублируете то, что уже есть.

По умолчанию структуры данных Clojure неизменяемы. Таким образом, узлы в вашей структуре, подобной дереву, не будут обновляться, если вы не используете какой-то ссылочный тип (например, Var). Я не знаю достаточно о вашем конкретном случае использования, чтобы советоваться о наилучшем способе доступа к узлам. Один из способов доступа к узлам во вложенной структуре - это get-in function, где вы указываете путь к узлу, чтобы вернуть его значение.

Надеюсь, это поможет решить вашу проблему.