Tree-like data structure in JS that allows for fastest node lookup?

Question

How would I go about creating a tree-like data structure in JS, where, I can have access to things like reference to parent node, id based node lookup, having access to length (number) of children nodes, index based lookup etc?

this is basically the API I am envisioning:

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 

etc..

I understand its a broad question, but I wonder if anyone could recommend a way to approach this and/or any libraries that might be doing it already? Should i just dynamically create an XML and work with its native methods? Would that be the fastest ?

Answer 1

The data structure you described can be easily implemented as follows:

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>

Both id based lookups and index based lookups take constant (i.e. O(1)) time. Hope that helps.

Answer 2

I have a structure like this in an app. The API specified would make it difficult to create a structure like you want. Here are some things I noticed: DataStructure is a singleton, addChild doesn't allow you to add a node with children, and indexes are numbers. How about the following?

API

TreeNode (newable)

Members:

• children (Object, indexed on ID)
• root (TreeNode)
• parent (TreeNode)
• index (String)
• attributes (Object)
• _referenceCount (int) - useful if your tree has cycles for some reason

Methods:

• addChild(TreeNode: treeNode)
  • Register the node with the parent
  • Adds the node by ID to children
  • Increments reference count of added TreeNode
• forEach(callback(TreeNode: treeNode))
• removeChild(String: id)
  • Removes node from this Object
  • Decrement _referenceCount of the indicated child
  • Removes it from the root if _referenceCount is 0

Tree (extends TreeNode) (newable)

Members:

• _nodeMap (Object)

Methods:

• getNodeByID(String: id)
  • looks up id in _nodeMap, O(1) lookup time
• removeNode(String: id)
• addToNodeMap(TreeNode: treeNode)

treeFactory (optional)

Methods:

• createFromFormatX(Object: a tree of stuff in some specific format) The tree works fine, you should create a factory for your specific case that helps you transform a blob into your fancy data structure.
• createFromFormatY, basically another loader mechanism

Potential Immutability

Nothing here is immutable necessarily. You could however, via use of a new factory method and make more of the above methods private always force immutability of the tree. This may or may not be desirable.