Method for encoding, traversing, manipulating and querying a tree

1. A method for encoding a tree, via a processor executing code, the method comprising:

receiving, via a processor, an input tree comprising a plurality of nodes, organized in a parent-child hierarchy, a parent node coupled to one or more child nodes;

assigning, via the processor, a node ID to each of the plurality of nodes of the input tree;

generating, via the processor, a representation between each parent node and the each of the child node associated with the parent node;

computing, via the processor, a tree code from prime numbers in the natural sequence of numbers, and the assigned node IDs to each of the parent node and child nodes, wherein the tree code is computed according to the formula:

Tree Code= p n1 m1 *p n2 +* . . . *p nk mk

where, p ni is the ni th prime number in the natural sequence of numbers, ni is the node ID of the i th parent node in the parent-child table, and mi is the number of children of the i th parent node in the parent-child table;

and

storing the tree code representative of the input tree.

2. The method of claim 1 , wherein generating a representation between each parent node and the child nodes associated with the parent node comprises

creating a parent-child table between each parent node of the input tree and the child nodes associated with the parent node.

3. The method of claim 2 , wherein the parent-child table comprises a parent row and a child row, wherein the parent row comprises each of the indices of the prime numbers of the tree code and the child row comprises each of the associated powers of the prime numbers.

4. A method for decoding a tree, the method comprising:

receiving a tree code;

factorizing the tree code into one or more prime numbers in ascending order, each prime number factor being raised to an associated power;

replacing each prime number by a respective prime number index;

creating a parent-child table comprising a parent row and a child row, the parent row containing each of the prime number indices and the child row containing each of the associated powers; and

creating a parent-child ID map comprising a parent row and a child row, the parent row of the parent-child ID map comprising each element of the parent row of the parent-child table, and the child row of the parent-child ID map comprising a sequence of natural numbers commencing from the integer 2, where each element of the parent row occurrence is repeated a number of times equivalent to the corresponding associated powers of the child row.

5. The method of claim 4 , wherein the structure of the parent-child ID map is such that each column of the parent-child ID map corresponds to a parent-child node hierarchy, wherein a parent node ID belongs to the parent row and the corresponding child node ID to the child row.

6. The method of claim 5 , wherein a parent node comprises multiple child nodes, and each parent-child node hierarchy is represented as a separate column in the parent-child ID map in order of sibling sequence in the tree.

7. The method of claim 4 , wherein the parent-child table, the parent-child ID map, and tree code are inter-derivable from any one of the other.

8. The method of claim 4 , further comprises

determining the number of nodes and edges of the decoded tree wherein the number of edges in the tree structure is equal to the sum of the number of children of the parent-child table and number of nodes in the tree structure is equal to one more than the number of edges.

9. The method of claim 4 , further comprises

determining the level of a specified node of the decoded tree, which comprises the steps of

performing a traversal of the parent-child ID map from the specified node to a root node of the tree;

counting the number of traversals involved; and

adding one to the count.

10. The method of claim 4 , further comprises

determining the leaf nodes of the decoded tree wherein leaf nodes of the tree structure are determined by comparing the parent row and child row of the parent-child ID map, and the nodes belonging to the child row and not the parent row are considered to be the leaf nodes of the tree.

11. The method of claim 4 , further comprises

determining the ancestors of a specified node of the decoded tree, which comprises the steps of

performing a traversal in the parent-child ID map starting with the specified node, wherein the nodes involved in the traversal, excluding the input node provides the ancestors of the node.

12. The method of claim 4 , further comprises

determining the descendants of a node of the decoded tree, which comprises the step of

performing a traversal of the parent-child ID map starting with an input node, wherein the nodes involved in the traversal excluding the input node provides the descendants of the input node.

13. The method of claim 4 , further comprises

determining the nodes of a tree fragment of the decoded tree, wherein traversal of the parent-child ID map is performed beginning with a root node of the tree fragment and nodes involved in the traversal are determined to be the nodes of the tree fragment.

14. The method of claim 4 , further comprises

determining the tree code of a specified tree fragment of the decoded tree, which comprises the steps of

finding nodes of the tree fragment;

selecting from the parent-child ID map only those columns that have the nodes of the fragments in both the parent rows and the child rows;

isolating the selected columns as a separate table;

inserting a new child row for the new parent-child ID map with natural numbers commencing from an integer 2, and retaining the old child row for next operation;

establishing a relationship between the old child node ID and the new child node ID;

creating a new parent row by relabelling old parent node IDs by comparing with the relationship between the old child node ID and the new child node ID;

removing the old child row and the old parent row, thereby creating a parent-child ID map of the tree fragment which is now isolated from the main tree;

creating a parent-child table from the parent-child ID map; and

computing the tree code for the tree fragment for the parent-child table.

15. The method of claim 4 , further comprises

determining a tree fragment of a specified tree code of the decoded, which comprises the steps of

finding all possible tree fragments by matching a specific criteria;

computing the tree code of all the tree fragments by finding the nodes of the tree fragment;

selecting from the parent-child ID map only those columns comprising nodes of the fragments in both the parent rows and the child rows;

isolating the selected columns as a separate table;

inserting a new Child row for the new parent-child ID map with natural numbers commencing from an integer 2, and retaining the old child row for next operation;

establishing a relationship between the old child node ID and the new child node ID;

creating a new parent row by relabelling old parent node IDs by comparing with the relationship between the old child node ID and the new child node ID;

removing the old child row and the old parent row, creating a parent-child table from the parent-child ID map;

computing the tree code for the tree fragment for the parent-child table; and

returning the fragment ID whose tree code matches the input tree code.

16. The method of claim 4 , further comprises

adding two or more trees of the decoded tree comprising the steps

(a) obtaining the parent-child ID map of the two or more trees;

(b) determining a column in a first parent-child ID map belonging to a first tree where a node of a second tree is to be inserted;

(c) reorganizing the first parent-child ID map after insertion of the node of the second tree, to its original format, where the child row of the parent-child ID map is a sequence of natural number commencing from the integer 2;

repeating steps (b) and (c) for all nodes of the second tree;

determining a tree code for the combined parent-child ID map.

17. The method of claim 4 , further comprises

deleting a tree fragment from a decoded tree, which comprises the steps of

performing a traversal of the parent-child ID map beginning from a root node of the tree fragment and nodes involved in the traversal are determined to be the nodes of the tree fragment;

removing columns of the parent-child ID map of the tree containing fragment nodes;

reorganizing the first parent-child ID map after removing the fragment nodes to its original format, where the child row of the parent-child ID map is a sequence of natural number commencing from the integer 2;

determining a tree code for the combined parent-child ID map.

18. The method of claim 4 , further comprises

sorting nodes IDs in depth-first order of a decoded tree, which comprises the steps of

creating a parent-child relationship map from the parent-child map, the parent-child relationship map comprising a parent node ID as keys and child node IDs as values;

obtaining the key and corresponding values from the lowermost row of the parent-child relationship map;

searching for the key obtained in the value column of the parent-child relationship map;

appending the corresponding value obtained to the value of the row found after searching for the key;

deleting the lowermost row from the parent-child relationship map; repeating the above step until the parent-child relationship map comprises only one row; and

appending the values of the row to the key.

19. The method of claim 4 , further comprises

detecting N node self similarity of a decoded tree, which comprises the steps of

(a) determining the number of edges and nodes from the parent-child ID map, wherein the number of edges in the tree structure is equal to the sum of the number of children of the parent-child table and number of nodes in the tree structure is equal to one more than the number of edges;

(b) validating if N node self similarity exists for the tree and performing step (c) only if the tree has N-node self-similarity; go to step (d);

(c) detecting the N node bottom fragment of the tree, wherein

if the bottom tree fragment does not exist, then there is no N node self-similarity in the tree or

if the bottom tree fragment exists, recording a fragment ID of the bottom fragment;

(d) subtracting the bottom fragment from the tree after recording the fragment ID;

repeating the steps (c) and (d) until the fragment ID of the last subtracted bottom fragment is the root node of the tree.