Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

sorting data into a tree

I have the following data:

var data = [
    { index : 1, sort : 10, parent : 0 },
    { index : 2, sort : 7, parent : 0 },
    { index : 3, sort : 15, parent : 1 },
    { index : 4, sort : 4, parent : 0 },
    { index : 5, sort : 13, parent : 1 },
    { index : 6, sort : 20, parent : 5 },
    { index : 7, sort : 2, parent : 8 },
    { index : 8, sort : 6, parent : 5 },
];

How do I efficiently sort this by both parent ID and the sort value so that I end up with:

var data = [
    { index : 4, sort : 4, parent : 0 },    
    { index : 2, sort : 7, parent : 0 },
    { index : 1, sort : 10, parent : 0 },
    { index : 5, sort : 13, parent : 1 },
    { index : 8, sort : 6, parent : 5 },
    { index : 7, sort : 2, parent : 8 },
    { index : 6, sort : 20, parent : 5 },   
    { index : 3, sort : 15, parent : 1 },
];

This is a tree structure. Each element is immediately followed by any children and all elements on the same branch are sorted by the sort value.

The best I can come up with is to first sort by parent and then do a second sort on each branch. This seems inefficient.

Edit: The example sort order was wrong. I've corrected it.

Edit for clarification: Each nested branch needs to appear immediately below the parent value, not at the end of the branch.

Edit: further corrections to data.

like image 925
SystemicPlural Avatar asked Nov 23 '11 11:11

SystemicPlural


People also ask

What is tree sort with example?

Tree sort is a sorting algorithm that is based on Binary Search Tree data structure. It first creates a binary search tree from the elements of the input list or array and then performs an in-order traversal on the created binary search tree to get the elements in sorted order.

Which sort is called as tree sort?

Explanation: Tree sort becomes an adaptive sort when it is implemented with a splay tree as a BST.

Which sorting algorithm is based on tree data structure?

Tree sort is a sorting algorithm that is based on Binary Search Tree data structure. It first creates a binary search tree from the elements of the input list or array and then performs an in-order traversal on the created binary search tree to get the elements in sorted order.

How do you create a tree in data structure?

Insert Operation The very first insertion creates the tree. Afterwards, whenever an element is to be inserted, first locate its proper location. Start searching from the root node, then if the data is less than the key value, search for the empty location in the left subtree and insert the data.


2 Answers

This is not your original approach, but you could build an actual tree from your data, like this:

function TreeNode(data) {
  this.data     = data;
  this.parent   = null;
  this.children = [];
}
TreeNode.comparer = function (a, b) { 
  return a.data.sort < b.data.sort ? 0 : 1; 
};
TreeNode.prototype.sortRecursive = function () {
  this.children.sort(TreeNode.comparer);
  for (var i=0, l=this.children.length; i<l; i++) {
    this.children[i].sortRecursive();
  }
  return this;
};

function toTree(data) {
  var nodeById = {}, i = 0, l = data.length, node;

  nodeById[0] = new TreeNode(); // that's the root node

  for (i=0; i<l; i++) {  // make TreeNode objects for each item
    nodeById[ data[i].index ] = new TreeNode(data[i]);
  }
  for (i=0; i<l; i++) {  // link all TreeNode objects
    node = nodeById[ data[i].index ];
    node.parent = nodeById[node.data.parent];
    node.parent.children.push(node);
  }
  return nodeById[0].sortRecursive();
}

With this set-up, you will get your nodes neatly nested with a simple call:

var tree = toTree(data);
TreeNode:0
  parent  -> null
  data    -> undefined
  childen -> Array[
    TreeNode:1
      parent  -> TreeNode:0
      data    -> { index : 4, sort :  4, parent : 0 }
      childen -> Array[]
    TreeNode:2
      parent  -> TreeNode:0
      data    -> { index : 2, sort :  7, parent : 0 }
      childen -> Array[]
    TreeNode:3
      parent  -> TreeNode:0
      data    -> { index : 1, sort : 10, parent : 0 }
      childen -> Array[
        TreeNode:4
          parent  -> TreeNode:3
          data    -> { index : 5, sort : 13, parent : 1 }
          childen -> Array[
          ]
        TreeNode:5
          parent  -> TreeNode:3
          data    -> { index : 3, sort : 15, parent : 1 }
          childen -> Array[
            ... and so on ...
          ]
      ]
  ]

Once you have that tree object, you can do a number of things with it, including traversing it recursively in the expected order.

To do this, you could add a helper function that does depth-first traversal and executes a payload function f for every node:

TreeNode.prototype.walk = function(f, recursive) {
  for (var i=0, l=this.children.length; i<l; i++) {
    var child = this.children[i];
    f.apply(child, Array.prototype.slice.call(arguments, 2));
    if (recursive) child.walk.apply(child, arguments);
  }
}

and call it like this:

tree.walk(function () { console.log(this.data) }, true);

which would produce:

{ index: 4, sort:  4, parent: 0}
{ index: 2, sort:  7, parent: 0}
{ index: 1, sort: 10, parent: 0}
{ index: 5, sort: 13, parent: 1}
{ index: 8, sort:  6, parent: 5}
{ index: 7, sort:  2, parent: 8}
{ index: 6, sort: 20, parent: 5}
{ index: 3, sort: 15, parent: 1}

Use more complex payload functions for other effects, like adding table rows in a table with jQuery or items to a <select> box.

like image 130
Tomalak Avatar answered Nov 01 '22 13:11

Tomalak


Tomalak request above that I post my singleton version of their answer. Here it is:

/**
 * Represents sorted results in a tree structure.
 */
Tree = (function() {

    /**
     *
     * @type {Object} nodes Holds all the nodes in a flat format.
     * @type {Object} nodes.data The data that is held in this node.
     * @type {Object} nodes.parent Points to the parent object of this node.
     * @type {Array} nodes.children An array of the child nodes of this node.
     */
    var nodes = {};

    /**
     * @type {Object} root_node A Reference to the root node in nodes.
     */
    var root_node;

    /**
     * A sort function to sort the nodes by the data.sort value in each node.
     * @param {Number} a The first node to compare
     * @param {Number} b The second node to compare
     * @return {Boolean} Swap these nodes or not.
     */
    var comparer = function (a, b) {
        return a.data.sort < b.data.sort ? 0 : 1;
    };

    /**
     * Sorts all the nodes so that they are in the correct order according to each nodes data.sort value.
     * @param {Object} node A reference to the node in the nodes object.
     */
    var sortRecursive = function (node) {
        node.children.sort(comparer);
        var len = node.children.length;
        for (var i = 0 ; i < len ; i++) {
            sortRecursive(node.children[i]);
        }
    };

    /**
     * Create a new node with the passed in data.
     * @param {Object} data The data that is associated with this node.
     */
    var create_node = function(data){
        var node = {
            data : data,
            parent : null,
            children : []
        };
        return node;
    };

    return {

        /**
         * Create a new tree of data
         * @param {Array} data An array of data objects to transorm into a tree.
         * @param {Array} data[].index The id of this node
         * @param {Array} data[].parent The parent id of this node.
         * @param {Number} root_id Id of the root node.
         */
        create : function(data, root_id){

            // Clear any previous data
            nodes = {};

            var i;
            var len = data.length;

            // Create an empty root node
            nodes[root_id] = create_node({});
            root_node = nodes[root_id];

            // Make node objects for each data item
            for (i=0; i<len; i++) {
                if(typeof data[i].sort !== "undefined")
                    nodes[ data[i].index ] = create_node(data[i]);
            }

            // Link all TreeNode objects
            for (i=0; i<len; i++) {
                var node = nodes[data[i].index];
                node.parent = nodes[node.data.parent];
                node.parent.children.push(node);
            }
            sortRecursive(nodes[root_id]);
        },

        /**
         * Walk through the nodes in nested and then sorted order, calling the passed in callback for each node.
         * @param {Function} callback A callback function to call for each node.
         * @param {Boolean} recursive Should the walkback be recursive, or just fetch the top level results.
         * @param {Object|Undefined} node The node that is currently being walked.
         *                                Ommit this value and the root node will be used.
         */
        walk : function(callback, recursive, node) {
            if(typeof node == "undefined")
                node = root_node;

            for (var i = 0, len = node.children.length; i < len; i++) {
                var child = node.children[i];
                callback.apply(child, Array.prototype.slice.call(arguments, 2));
                if (recursive)
                    arguments.callee(callback, recursive, child);
            }
        }

    };
})();

Populate the tree with:

Tree.create(unsorted_data, parent_id);

Fetch a sorted array with:

var sorted = [];
Tree.walk(function(){
    sorted.push(this.data);
}, true);
like image 28
SystemicPlural Avatar answered Nov 01 '22 14:11

SystemicPlural