15

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 ?

nuway
  • 2,324
  • 4
  • 27
  • 48

2 Answers2

4

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.

Community
  • 1
  • 1
Aadit M Shah
  • 72,912
  • 30
  • 168
  • 299
  • You should name that class a `Node`. A `Tree` would be a complete "document", e.g. with tree-wide id lookup; a structure with a reference to the root node. – Bergi Apr 21 '15 at 14:31
  • @Bergi Actually, I was thinking of it more as the algebraic data type `data Tree = Tree { parent :: Maybe Tree, children :: Map String Tree, ids :: Array Int String, length :: Int }`. Since the data constructor returns a `Tree` (which trivially also happens to be a node) I named it `Tree`. – Aadit M Shah Apr 21 '15 at 15:50
  • Mhm. I'm more accustomed to the ADT `data Tree = Emtpy | Node { … }`, but I guess yours makes sense as well. – Bergi Apr 21 '15 at 16:00
1

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.

Parris
  • 17,833
  • 17
  • 90
  • 133
  • Please comment if you down vote. This works, and has O(1) lookup times. – Parris Apr 17 '15 at 19:48
  • Why didn't you just write the code? It would probably earn you more up-votes. – Sildoreth Apr 21 '15 at 15:26
  • 2
    @Sildoreth yea, I might get more up votes? Although generally when questions are like "implement this thing for me", I and others here will shy away from actually implementing the whole thing and instead opt for proposing a concept. I also didn't have time to REALLY create a solution and run it through its paces. I might as well create an open source library for this instead of just answering a stackoverflow question. – Parris Apr 24 '15 at 08:26