Деревоподобная структура данных в JS, которая позволяет быстро найти node?

Как я могу создать древовидную структуру данных в JS, где я могу получить доступ к таким вещам, как ссылка на родительский node, на основе поиска node на основе id, имеющий доступ к длине (числу) детей узлы, поиск по индексу и т.д.?

это в основном API, который я предполагаю:

var rootNode = DataStructure.getRoot();
var child1 = rootNode.addNode('child1'); //added a node with id 'child1'
child1.addNode('innerChild1');
child1.addNode('innerChild2');
rootNode.getChildById('child1') //should be same node as var child1
rootNode.getAtIndex(0) //should be same node as var child1
child1.parent() //should be rootNode
child1.getAtIndex(0) // should be node with id 'innerChild1'
child1.getAtIndex(1) // should be node with id 'innerChild2'
child1.length() //should be 2

и т.д..

Я понимаю его широкий вопрос, но мне интересно, может ли кто-нибудь рекомендовать способ приблизиться к этому и/или к любым библиотекам, которые могли бы это сделать уже? Должен ли я просто динамически создавать XML и работать с его собственными методами? Это будет самый быстрый?

Ответы

Ответ 1

Структура данных, которую вы описали, может быть легко реализована следующим образом:

var Tree = defclass({
    constructor: function (parent) {
        this.parent   = parent || null; // null for root node
        this.children = {};             // for id based lookup
        this.ids      = [];             // for index based lookup
        this.length   = 0;              // for ease of access
    },
    addNode: function (id) {
        var children = this.children;
        if (children.hasOwnProperty(id)) throw new Error(id + " exists");
        return children[this.ids[this.length++] = id] = new Tree(this);
    },
    getChildById: function (id) {
        var children = this.children;
        if (children.hasOwnProperty(id)) return children[id];
        throw new Error(id + " does not exist");
    },
    getAtIndex: function (index) {
        return this.getChildById(this.ids[index]);
    }
});

function defclass(prototype) {
    var constructor = prototype.constructor;
    constructor.prototype = prototype;
    return constructor;
}
<script>
    setTimeout(function () {
        var rootNode    = new Tree;
        var child1      = rootNode.addNode("child1");
        var innerChild1 = child1.addNode("innerChild1");
        var innerChild2 = child1.addNode("innerChild2");

        console.assert(rootNode.getChildById("child1") === child1);
        console.assert(rootNode.getAtIndex(0)          === child1);
        console.assert(child1.parent                   === rootNode);
        console.assert(child1.getAtIndex(0)            === innerChild1);
        console.assert(child1.getAtIndex(1)            === innerChild2);
        console.assert(child1.length                   === 2);

        alert("success");
    }, 0);
</script>

Ответ 2

У меня есть такая структура в приложении. Указанный API затруднит создание такой структуры, как вы хотите. Вот некоторые из замечаний, которые я заметил: DataStructure - одноэлементный, addChild не позволяет добавлять node с дочерними элементами, а индексы - это числа. Как насчет следующего?

API

TreeNode (новый)

Пользователи

  • дети (объект, индексированный по идентификатору)
  • root (TreeNode)
  • parent (TreeNode)
  • index (String)
  • атрибуты (объект)
  • _referenceCount (int) - полезно, если по какой-то причине ваше дерево имеет циклы

Методы:

  • addChild (TreeNode: treeNode)
    • Зарегистрируйте node с родительским
    • Добавляет node по ID для детей
    • Увеличивает количество ссылок добавленного TreeNode
  • forEach (callback (TreeNode: treeNode))
  • removeChild (String: id)
    • Удаляет node из этого объекта
    • Decrement _referenceCount указанного ребенка
    • Удаляет его из корня, если _referenceCount равно 0

Дерево (расширяет TreeNode) (новое)

Пользователи

  • _nodeMap (Object)

Методы:

  • getNodeByID (String: id)
    • ищет id в _nodeMap, O (1) время поиска
  • removeNode (String: id)
  • addToNodeMap (TreeNode: treeNode)

treeFactory (необязательно)

Методы:

  • createFromFormatX (Object: дерево вещей в каком-то определенном формате). Дерево прекрасно работает, вы должны создать factory для вашего конкретного случая, который поможет вам преобразовать blob в вашу фантастическую структуру данных.
  • createFromFormatY, в основном другой механизм загрузчика

Потенциальная неизменность

Ничто здесь не обязательно обязательно. Тем не менее, вы можете использовать новый метод factory и сделать все вышеприведенные методы частным, всегда заставляя неизменность дерева. Это может быть или не быть желательным.