JS中的树状数据结构允许最快的节点查找？

Question

我将如何在JS中创建一个类似树的数据结构,在那里,我可以访问诸如父节点的引用,基于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并使用其本机方法吗？那会是最快的吗？

Answer 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>

基于 id 的查找和基于索引的查找都需要恒定的（即O(1)）时间。希望有帮助。