Assume you have a flat table that stores an ordered tree hierarchy:
Id Name ParentId Order
1 'Node 1' 0 10
2 'Node 1.1' 1 10
3 'Node 2' 0 20
4 'Node 1.1.1' 2 10
5 'Node 2.1' 3 10
6 'Node 1.2' 1 20
Here's a diagram, where we have [id] Name. Root node 0 is fictional.
[0] ROOT
/ \
[1] Node 1 [3] Node 2
/ \ \
[2] Node 1.1 [6] Node 1.2 [5] Node 2.1
/
[4] Node 1.1.1
What minimalistic approach would you use to output that to HTML (or text, for that matter) as a correctly ordered, correctly indented tree?
Assume further you only have basic data structures (arrays and hashmaps), no fancy objects with parent/children references, no ORM, no framework, just your two hands. The table is represented as a result set, which can be accessed randomly.
Pseudo code or plain English is okay, this is purely a conceptional question.
Bonus question: Is there a fundamentally better way to store a tree structure like this in a RDBMS?
EDITS AND ADDITIONS
To answer one commenter's (Mark Bessey's) question: A root node is not necessary, because it is never going to be displayed anyway. ParentId = 0 is the convention to express "these are top level". The Order column defines how nodes with the same parent are going to be sorted.
The "result set" I spoke of can be pictured as an array of hashmaps (to stay in that terminology). For my example was meant to be already there. Some answers go the extra mile and construct it first, but thats okay.
The tree can be arbitrarily deep. Each node can have N children. I did not exactly have a "millions of entries" tree in mind, though.
Don't mistake my choice of node naming ('Node 1.1.1') for something to rely on. The nodes could equally well be called 'Frank' or 'Bob', no naming structure is implied, this was merely to make it readable.
I have posted my own solution so you guys can pull it to pieces.
This question is related to
sql
algorithm
recursion
tree
hierarchical-data
If nested hash maps or arrays can be created, then I can simply go down the table from the beginning and add each item to the nested array. I must trace each line to the root node in order to know which level in the nested array to insert into. I can employ memoization so that I do not need to look up the same parent over and over again.
Edit: I would read the entire table into an array first, so it will not query the DB repeatedly. Of course this won't be practical if your table is very large.
After the structure is built, I must do a depth first traverse through it and print out the HTML.
There's no better fundamental way to store this information using one table (I could be wrong though ;), and would love to see a better solution ). However, if you create a scheme to employ dynamically created db tables, then you opened up a whole new world at the sacrifice of simplicity, and the risk of SQL hell ;).
Well given the choice, I'd be using objects. I'd create an object for each record where each object has a children collection and store them all in an assoc array (/hashtable) where the Id is the key. And blitz through the collection once, adding the children to the relevant children fields. Simple.
But because you're being no fun by restricting use of some good OOP, I'd probably iterate based on:
function PrintLine(int pID, int level)
foreach record where ParentID == pID
print level*tabs + record-data
PrintLine(record.ID, level + 1)
PrintLine(0, 0)
Edit: this is similar to a couple of other entries, but I think it's slightly cleaner. One thing I'll add: this is extremely SQL-intensive. It's nasty. If you have the choice, go the OOP route.
As of Oracle 9i, you can use CONNECT BY.
SELECT LPAD(' ', (LEVEL - 1) * 4) || "Name" AS "Name"
FROM (SELECT * FROM TMP_NODE ORDER BY "Order")
CONNECT BY PRIOR "Id" = "ParentId"
START WITH "Id" IN (SELECT "Id" FROM TMP_NODE WHERE "ParentId" = 0)
As of SQL Server 2005, you can use a recursive common table expression (CTE).
WITH [NodeList] (
[Id]
, [ParentId]
, [Level]
, [Order]
) AS (
SELECT [Node].[Id]
, [Node].[ParentId]
, 0 AS [Level]
, CONVERT([varchar](MAX), [Node].[Order]) AS [Order]
FROM [Node]
WHERE [Node].[ParentId] = 0
UNION ALL
SELECT [Node].[Id]
, [Node].[ParentId]
, [NodeList].[Level] + 1 AS [Level]
, [NodeList].[Order] + '|'
+ CONVERT([varchar](MAX), [Node].[Order]) AS [Order]
FROM [Node]
INNER JOIN [NodeList] ON [NodeList].[Id] = [Node].[ParentId]
) SELECT REPLICATE(' ', [NodeList].[Level] * 4) + [Node].[Name] AS [Name]
FROM [Node]
INNER JOIN [NodeList] ON [NodeList].[Id] = [Node].[Id]
ORDER BY [NodeList].[Order]
Both will output the following results.
Name 'Node 1' ' Node 1.1' ' Node 1.1.1' ' Node 1.2' 'Node 2' ' Node 2.1'
This was written quickly, and is neither pretty nor efficient (plus it autoboxes alot, converting between int and Integer is annoying!), but it works.
It probably breaks the rules since I'm creating my own objects but hey I'm doing this as a diversion from real work :)
This also assumes that the resultSet/table is completely read into some sort of structure before you start building Nodes, which wouldn't be the best solution if you have hundreds of thousands of rows.
public class Node {
private Node parent = null;
private List<Node> children;
private String name;
private int id = -1;
public Node(Node parent, int id, String name) {
this.parent = parent;
this.children = new ArrayList<Node>();
this.name = name;
this.id = id;
}
public int getId() {
return this.id;
}
public String getName() {
return this.name;
}
public void addChild(Node child) {
children.add(child);
}
public List<Node> getChildren() {
return children;
}
public boolean isRoot() {
return (this.parent == null);
}
@Override
public String toString() {
return "id=" + id + ", name=" + name + ", parent=" + parent;
}
}
public class NodeBuilder {
public static Node build(List<Map<String, String>> input) {
// maps id of a node to it's Node object
Map<Integer, Node> nodeMap = new HashMap<Integer, Node>();
// maps id of a node to the id of it's parent
Map<Integer, Integer> childParentMap = new HashMap<Integer, Integer>();
// create special 'root' Node with id=0
Node root = new Node(null, 0, "root");
nodeMap.put(root.getId(), root);
// iterate thru the input
for (Map<String, String> map : input) {
// expect each Map to have keys for "id", "name", "parent" ... a
// real implementation would read from a SQL object or resultset
int id = Integer.parseInt(map.get("id"));
String name = map.get("name");
int parent = Integer.parseInt(map.get("parent"));
Node node = new Node(null, id, name);
nodeMap.put(id, node);
childParentMap.put(id, parent);
}
// now that each Node is created, setup the child-parent relationships
for (Map.Entry<Integer, Integer> entry : childParentMap.entrySet()) {
int nodeId = entry.getKey();
int parentId = entry.getValue();
Node child = nodeMap.get(nodeId);
Node parent = nodeMap.get(parentId);
parent.addChild(child);
}
return root;
}
}
public class NodePrinter {
static void printRootNode(Node root) {
printNodes(root, 0);
}
static void printNodes(Node node, int indentLevel) {
printNode(node, indentLevel);
// recurse
for (Node child : node.getChildren()) {
printNodes(child, indentLevel + 1);
}
}
static void printNode(Node node, int indentLevel) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < indentLevel; i++) {
sb.append("\t");
}
sb.append(node);
System.out.println(sb.toString());
}
public static void main(String[] args) {
// setup dummy data
List<Map<String, String>> resultSet = new ArrayList<Map<String, String>>();
resultSet.add(newMap("1", "Node 1", "0"));
resultSet.add(newMap("2", "Node 1.1", "1"));
resultSet.add(newMap("3", "Node 2", "0"));
resultSet.add(newMap("4", "Node 1.1.1", "2"));
resultSet.add(newMap("5", "Node 2.1", "3"));
resultSet.add(newMap("6", "Node 1.2", "1"));
Node root = NodeBuilder.build(resultSet);
printRootNode(root);
}
//convenience method for creating our dummy data
private static Map<String, String> newMap(String id, String name, String parentId) {
Map<String, String> row = new HashMap<String, String>();
row.put("id", id);
row.put("name", name);
row.put("parent", parentId);
return row;
}
}
As of Oracle 9i, you can use CONNECT BY.
SELECT LPAD(' ', (LEVEL - 1) * 4) || "Name" AS "Name"
FROM (SELECT * FROM TMP_NODE ORDER BY "Order")
CONNECT BY PRIOR "Id" = "ParentId"
START WITH "Id" IN (SELECT "Id" FROM TMP_NODE WHERE "ParentId" = 0)
As of SQL Server 2005, you can use a recursive common table expression (CTE).
WITH [NodeList] (
[Id]
, [ParentId]
, [Level]
, [Order]
) AS (
SELECT [Node].[Id]
, [Node].[ParentId]
, 0 AS [Level]
, CONVERT([varchar](MAX), [Node].[Order]) AS [Order]
FROM [Node]
WHERE [Node].[ParentId] = 0
UNION ALL
SELECT [Node].[Id]
, [Node].[ParentId]
, [NodeList].[Level] + 1 AS [Level]
, [NodeList].[Order] + '|'
+ CONVERT([varchar](MAX), [Node].[Order]) AS [Order]
FROM [Node]
INNER JOIN [NodeList] ON [NodeList].[Id] = [Node].[ParentId]
) SELECT REPLICATE(' ', [NodeList].[Level] * 4) + [Node].[Name] AS [Name]
FROM [Node]
INNER JOIN [NodeList] ON [NodeList].[Id] = [Node].[Id]
ORDER BY [NodeList].[Order]
Both will output the following results.
Name 'Node 1' ' Node 1.1' ' Node 1.1.1' ' Node 1.2' 'Node 2' ' Node 2.1'
If you use nested sets (sometimes referred to as Modified Pre-order Tree Traversal) you can extract the entire tree structure or any subtree within it in tree order with a single query, at the cost of inserts being more expensive, as you need to manage columns which describe an in-order path through thee tree structure.
For django-mptt, I used a structure like this:
id parent_id tree_id level lft rght -- --------- ------- ----- --- ---- 1 null 1 0 1 14 2 1 1 1 2 7 3 2 1 2 3 4 4 2 1 2 5 6 5 1 1 1 8 13 6 5 1 2 9 10 7 5 1 2 11 12
Which describes a tree which looks like this (with id representing each item):
1
+-- 2
| +-- 3
| +-- 4
|
+-- 5
+-- 6
+-- 7
Or, as a nested set diagram which makes it more obvious how the lft and rght values work:
__________________________________________________________________________ | Root 1 | | ________________________________ ________________________________ | | | Child 1.1 | | Child 1.2 | | | | ___________ ___________ | | ___________ ___________ | | | | | C 1.1.1 | | C 1.1.2 | | | | C 1.2.1 | | C 1.2.2 | | | 1 2 3___________4 5___________6 7 8 9___________10 11__________12 13 14 | |________________________________| |________________________________| | |__________________________________________________________________________|
As you can see, to get the entire subtree for a given node, in tree order, you simply have to select all rows which have lft and rght values between its lft and rght values. It's also simple to retrieve the tree of ancestors for a given node.
The level column is a bit of denormalisation for convenience more than anything and the tree_id column allows you to restart the lft and rght numbering for each top-level node, which reduces the number of columns affected by inserts, moves and deletions, as the lft and rght columns have to be adjusted accordingly when these operations take place in order to create or close gaps. I made some development notes at the time when I was trying to wrap my head around the queries required for each operation.
In terms of actually working with this data to display a tree, I created a tree_item_iterator utility function which, for each node, should give you sufficient information to generate whatever kind of display you want.
More info about MPTT:
If elements are in tree order, as shown in your example, you can use something like the following Python example:
delimiter = '.'
stack = []
for item in items:
while stack and not item.startswith(stack[-1]+delimiter):
print "</div>"
stack.pop()
print "<div>"
print item
stack.append(item)
What this does is maintain a stack representing the current position in the tree. For each element in the table, it pops stack elements (closing the matching divs) until it finds the parent of the current item. Then it outputs the start of that node and pushes it to the stack.
If you want to output the tree using indenting rather than nested elements, you can simply skip the print statements to print the divs, and print a number of spaces equal to some multiple of the size of the stack before each item. For example, in Python:
print " " * len(stack)
You could also easily use this method to construct a set of nested lists or dictionaries.
Edit: I see from your clarification that the names were not intended to be node paths. That suggests an alternate approach:
idx = {}
idx[0] = []
for node in results:
child_list = []
idx[node.Id] = child_list
idx[node.ParentId].append((node, child_list))
This constructs a tree of arrays of tuples(!). idx[0] represents the root(s) of the tree. Each element in an array is a 2-tuple consisting of the node itself and a list of all its children. Once constructed, you can hold on to idx[0] and discard idx, unless you want to access nodes by their ID.
Bill's answer is pretty gosh-darned good, this answer adds some things to it which makes me wish SO supported threaded answers.
Anyway I wanted to support the tree structure and the Order property. I included a single property in each Node called leftSibling that does the same thing Order is meant to do in the original question (maintain left-to-right order).
mysql> desc nodes ; +-------------+--------------+------+-----+---------+----------------+ | Field | Type | Null | Key | Default | Extra | +-------------+--------------+------+-----+---------+----------------+ | id | int(11) | NO | PRI | NULL | auto_increment | | name | varchar(255) | YES | | NULL | | | leftSibling | int(11) | NO | | 0 | | +-------------+--------------+------+-----+---------+----------------+ 3 rows in set (0.00 sec) mysql> desc adjacencies; +------------+---------+------+-----+---------+----------------+ | Field | Type | Null | Key | Default | Extra | +------------+---------+------+-----+---------+----------------+ | relationId | int(11) | NO | PRI | NULL | auto_increment | | parent | int(11) | NO | | NULL | | | child | int(11) | NO | | NULL | | | pathLen | int(11) | NO | | NULL | | +------------+---------+------+-----+---------+----------------+ 4 rows in set (0.00 sec)
More detail and SQL code on my blog.
Thanks Bill your answer was helpful in getting started!
It's a quite old question, but as it's got many views I think it's worth to present an alternative, and in my opinion very elegant, solution.
In order to read a tree structure you can use recursive Common Table Expressions (CTEs). It gives a possibility to fetch whole tree structure at once, have the information about the level of the node, its parent node and order within children of the parent node.
Let me show you how this would work in PostgreSQL 9.1.
Create a structure
CREATE TABLE tree (
id int NOT NULL,
name varchar(32) NOT NULL,
parent_id int NULL,
node_order int NOT NULL,
CONSTRAINT tree_pk PRIMARY KEY (id),
CONSTRAINT tree_tree_fk FOREIGN KEY (parent_id)
REFERENCES tree (id) NOT DEFERRABLE
);
insert into tree values
(0, 'ROOT', NULL, 0),
(1, 'Node 1', 0, 10),
(2, 'Node 1.1', 1, 10),
(3, 'Node 2', 0, 20),
(4, 'Node 1.1.1', 2, 10),
(5, 'Node 2.1', 3, 10),
(6, 'Node 1.2', 1, 20);
Write a query
WITH RECURSIVE
tree_search (id, name, level, parent_id, node_order) AS (
SELECT
id,
name,
0,
parent_id,
1
FROM tree
WHERE parent_id is NULL
UNION ALL
SELECT
t.id,
t.name,
ts.level + 1,
ts.id,
t.node_order
FROM tree t, tree_search ts
WHERE t.parent_id = ts.id
)
SELECT * FROM tree_search
WHERE level > 0
ORDER BY level, parent_id, node_order;
Here are the results:
id | name | level | parent_id | node_order
----+------------+-------+-----------+------------
1 | Node 1 | 1 | 0 | 10
3 | Node 2 | 1 | 0 | 20
2 | Node 1.1 | 2 | 1 | 10
6 | Node 1.2 | 2 | 1 | 20
5 | Node 2.1 | 2 | 3 | 10
4 | Node 1.1.1 | 3 | 2 | 10
(6 rows)
The tree nodes are ordered by a level of depth. In the final output we would present them in the subsequent lines.
For each level, they are ordered by parent_id and node_order within the parent. This tells us how to present them in the output - link node to the parent in this order.
Having such a structure it wouldn't be difficult to make a really nice presentation in HTML.
Recursive CTEs are available in PostgreSQL, IBM DB2, MS SQL Server and Oracle.
If you'd like to read more on recursive SQL queries, you can either check the documentation of your favourite DBMS or read my two articles covering this topic:
If nested hash maps or arrays can be created, then I can simply go down the table from the beginning and add each item to the nested array. I must trace each line to the root node in order to know which level in the nested array to insert into. I can employ memoization so that I do not need to look up the same parent over and over again.
Edit: I would read the entire table into an array first, so it will not query the DB repeatedly. Of course this won't be practical if your table is very large.
After the structure is built, I must do a depth first traverse through it and print out the HTML.
There's no better fundamental way to store this information using one table (I could be wrong though ;), and would love to see a better solution ). However, if you create a scheme to employ dynamically created db tables, then you opened up a whole new world at the sacrifice of simplicity, and the risk of SQL hell ;).
If elements are in tree order, as shown in your example, you can use something like the following Python example:
delimiter = '.'
stack = []
for item in items:
while stack and not item.startswith(stack[-1]+delimiter):
print "</div>"
stack.pop()
print "<div>"
print item
stack.append(item)
What this does is maintain a stack representing the current position in the tree. For each element in the table, it pops stack elements (closing the matching divs) until it finds the parent of the current item. Then it outputs the start of that node and pushes it to the stack.
If you want to output the tree using indenting rather than nested elements, you can simply skip the print statements to print the divs, and print a number of spaces equal to some multiple of the size of the stack before each item. For example, in Python:
print " " * len(stack)
You could also easily use this method to construct a set of nested lists or dictionaries.
Edit: I see from your clarification that the names were not intended to be node paths. That suggests an alternate approach:
idx = {}
idx[0] = []
for node in results:
child_list = []
idx[node.Id] = child_list
idx[node.ParentId].append((node, child_list))
This constructs a tree of arrays of tuples(!). idx[0] represents the root(s) of the tree. Each element in an array is a 2-tuple consisting of the node itself and a list of all its children. Once constructed, you can hold on to idx[0] and discard idx, unless you want to access nodes by their ID.
If elements are in tree order, as shown in your example, you can use something like the following Python example:
delimiter = '.'
stack = []
for item in items:
while stack and not item.startswith(stack[-1]+delimiter):
print "</div>"
stack.pop()
print "<div>"
print item
stack.append(item)
What this does is maintain a stack representing the current position in the tree. For each element in the table, it pops stack elements (closing the matching divs) until it finds the parent of the current item. Then it outputs the start of that node and pushes it to the stack.
If you want to output the tree using indenting rather than nested elements, you can simply skip the print statements to print the divs, and print a number of spaces equal to some multiple of the size of the stack before each item. For example, in Python:
print " " * len(stack)
You could also easily use this method to construct a set of nested lists or dictionaries.
Edit: I see from your clarification that the names were not intended to be node paths. That suggests an alternate approach:
idx = {}
idx[0] = []
for node in results:
child_list = []
idx[node.Id] = child_list
idx[node.ParentId].append((node, child_list))
This constructs a tree of arrays of tuples(!). idx[0] represents the root(s) of the tree. Each element in an array is a 2-tuple consisting of the node itself and a list of all its children. Once constructed, you can hold on to idx[0] and discard idx, unless you want to access nodes by their ID.
Think about using nosql tools like neo4j for hierarchial structures. e.g a networked application like linkedin uses couchbase (another nosql solution)
But use nosql only for data-mart level queries and not to store / maintain transactions
If you use nested sets (sometimes referred to as Modified Pre-order Tree Traversal) you can extract the entire tree structure or any subtree within it in tree order with a single query, at the cost of inserts being more expensive, as you need to manage columns which describe an in-order path through thee tree structure.
For django-mptt, I used a structure like this:
id parent_id tree_id level lft rght -- --------- ------- ----- --- ---- 1 null 1 0 1 14 2 1 1 1 2 7 3 2 1 2 3 4 4 2 1 2 5 6 5 1 1 1 8 13 6 5 1 2 9 10 7 5 1 2 11 12
Which describes a tree which looks like this (with id representing each item):
1
+-- 2
| +-- 3
| +-- 4
|
+-- 5
+-- 6
+-- 7
Or, as a nested set diagram which makes it more obvious how the lft and rght values work:
__________________________________________________________________________ | Root 1 | | ________________________________ ________________________________ | | | Child 1.1 | | Child 1.2 | | | | ___________ ___________ | | ___________ ___________ | | | | | C 1.1.1 | | C 1.1.2 | | | | C 1.2.1 | | C 1.2.2 | | | 1 2 3___________4 5___________6 7 8 9___________10 11__________12 13 14 | |________________________________| |________________________________| | |__________________________________________________________________________|
As you can see, to get the entire subtree for a given node, in tree order, you simply have to select all rows which have lft and rght values between its lft and rght values. It's also simple to retrieve the tree of ancestors for a given node.
The level column is a bit of denormalisation for convenience more than anything and the tree_id column allows you to restart the lft and rght numbering for each top-level node, which reduces the number of columns affected by inserts, moves and deletions, as the lft and rght columns have to be adjusted accordingly when these operations take place in order to create or close gaps. I made some development notes at the time when I was trying to wrap my head around the queries required for each operation.
In terms of actually working with this data to display a tree, I created a tree_item_iterator utility function which, for each node, should give you sufficient information to generate whatever kind of display you want.
More info about MPTT:
There are really good solutions which exploit the internal btree representation of sql indices. This is based on some great research done back around 1998.
Here is an example table (in mysql).
CREATE TABLE `node` (
`id` int(10) unsigned NOT NULL AUTO_INCREMENT,
`name` varchar(255) NOT NULL,
`tw` int(10) unsigned NOT NULL,
`pa` int(10) unsigned DEFAULT NULL,
`sz` int(10) unsigned DEFAULT NULL,
`nc` int(11) GENERATED ALWAYS AS (tw+sz) STORED,
PRIMARY KEY (`id`),
KEY `node_tw_index` (`tw`),
KEY `node_pa_index` (`pa`),
KEY `node_nc_index` (`nc`),
CONSTRAINT `node_pa_fk` FOREIGN KEY (`pa`) REFERENCES `node` (`tw`) ON DELETE CASCADE
)
The only fields necessary for the tree representation are:
Here is an example 24 node population, ordered by tw:
+-----+---------+----+------+------+------+
| id | name | tw | pa | sz | nc |
+-----+---------+----+------+------+------+
| 1 | Root | 1 | NULL | 24 | 25 |
| 2 | A | 2 | 1 | 14 | 16 |
| 3 | AA | 3 | 2 | 1 | 4 |
| 4 | AB | 4 | 2 | 7 | 11 |
| 5 | ABA | 5 | 4 | 1 | 6 |
| 6 | ABB | 6 | 4 | 3 | 9 |
| 7 | ABBA | 7 | 6 | 1 | 8 |
| 8 | ABBB | 8 | 6 | 1 | 9 |
| 9 | ABC | 9 | 4 | 2 | 11 |
| 10 | ABCD | 10 | 9 | 1 | 11 |
| 11 | AC | 11 | 2 | 4 | 15 |
| 12 | ACA | 12 | 11 | 2 | 14 |
| 13 | ACAA | 13 | 12 | 1 | 14 |
| 14 | ACB | 14 | 11 | 1 | 15 |
| 15 | AD | 15 | 2 | 1 | 16 |
| 16 | B | 16 | 1 | 1 | 17 |
| 17 | C | 17 | 1 | 6 | 23 |
| 359 | C0 | 18 | 17 | 5 | 23 |
| 360 | C1 | 19 | 18 | 4 | 23 |
| 361 | C2(res) | 20 | 19 | 3 | 23 |
| 362 | C3 | 21 | 20 | 2 | 23 |
| 363 | C4 | 22 | 21 | 1 | 23 |
| 18 | D | 23 | 1 | 1 | 24 |
| 19 | E | 24 | 1 | 1 | 25 |
+-----+---------+----+------+------+------+
Every tree result can be done non-recursively. For instance, to get a list of ancestors of node at tw='22'
Ancestors
select anc.* from node me,node anc
where me.tw=22 and anc.nc >= me.tw and anc.tw <= me.tw
order by anc.tw;
+-----+---------+----+------+------+------+
| id | name | tw | pa | sz | nc |
+-----+---------+----+------+------+------+
| 1 | Root | 1 | NULL | 24 | 25 |
| 17 | C | 17 | 1 | 6 | 23 |
| 359 | C0 | 18 | 17 | 5 | 23 |
| 360 | C1 | 19 | 18 | 4 | 23 |
| 361 | C2(res) | 20 | 19 | 3 | 23 |
| 362 | C3 | 21 | 20 | 2 | 23 |
| 363 | C4 | 22 | 21 | 1 | 23 |
+-----+---------+----+------+------+------+
Siblings and children are trivial - just use pa field ordering by tw.
Descendants
For example the set (branch) of nodes that are rooted at tw = 17.
select des.* from node me,node des
where me.tw=17 and des.tw < me.nc and des.tw >= me.tw
order by des.tw;
+-----+---------+----+------+------+------+
| id | name | tw | pa | sz | nc |
+-----+---------+----+------+------+------+
| 17 | C | 17 | 1 | 6 | 23 |
| 359 | C0 | 18 | 17 | 5 | 23 |
| 360 | C1 | 19 | 18 | 4 | 23 |
| 361 | C2(res) | 20 | 19 | 3 | 23 |
| 362 | C3 | 21 | 20 | 2 | 23 |
| 363 | C4 | 22 | 21 | 1 | 23 |
+-----+---------+----+------+------+------+
Additional Notes
This methodology is extremely useful for when there are a far greater number of reads than there are inserts or updates.
Because the insertion, movement, or updating of a node in the tree requires the tree to be adjusted, it is necessary to lock the table before commencing with the action.
The insertion/deletion cost is high because the tw index and sz (branch size) values will need to be updated on all the nodes after the insertion point, and for all ancestors respectively.
Branch moving involves moving the tw value of the branch out of range, so it is also necessary to disable foreign key constraints when moving a branch. There are, essentially four queries required to move a branch:
Adjust Tree Queries
The opening/closing of gaps in the tree is an important sub-function used by create/update/delete methods, so I include it here.
We need two parameters - a flag representing whether or not we are downsizing or upsizing, and the node's tw index. So, for example tw=18 (which has a branch size of 5). Let's assume that we are downsizing (removing tw) - this means that we are using '-' instead of '+' in the updates of the following example.
We first use a (slightly altered) ancestor function to update the sz value.
update node me, node anc set anc.sz = anc.sz - me.sz from
node me, node anc where me.tw=18
and ((anc.nc >= me.tw and anc.tw < me.pa) or (anc.tw=me.pa));
Then we need to adjust the tw for those whose tw is higher than the branch to be removed.
update node me, node anc set anc.tw = anc.tw - me.sz from
node me, node anc where me.tw=18 and anc.tw >= me.tw;
Then we need to adjust the parent for those whose pa's tw is higher than the branch to be removed.
update node me, node anc set anc.pa = anc.pa - me.sz from
node me, node anc where me.tw=18 and anc.pa >= me.tw;
As of Oracle 9i, you can use CONNECT BY.
SELECT LPAD(' ', (LEVEL - 1) * 4) || "Name" AS "Name"
FROM (SELECT * FROM TMP_NODE ORDER BY "Order")
CONNECT BY PRIOR "Id" = "ParentId"
START WITH "Id" IN (SELECT "Id" FROM TMP_NODE WHERE "ParentId" = 0)
As of SQL Server 2005, you can use a recursive common table expression (CTE).
WITH [NodeList] (
[Id]
, [ParentId]
, [Level]
, [Order]
) AS (
SELECT [Node].[Id]
, [Node].[ParentId]
, 0 AS [Level]
, CONVERT([varchar](MAX), [Node].[Order]) AS [Order]
FROM [Node]
WHERE [Node].[ParentId] = 0
UNION ALL
SELECT [Node].[Id]
, [Node].[ParentId]
, [NodeList].[Level] + 1 AS [Level]
, [NodeList].[Order] + '|'
+ CONVERT([varchar](MAX), [Node].[Order]) AS [Order]
FROM [Node]
INNER JOIN [NodeList] ON [NodeList].[Id] = [Node].[ParentId]
) SELECT REPLICATE(' ', [NodeList].[Level] * 4) + [Node].[Name] AS [Name]
FROM [Node]
INNER JOIN [NodeList] ON [NodeList].[Id] = [Node].[Id]
ORDER BY [NodeList].[Order]
Both will output the following results.
Name 'Node 1' ' Node 1.1' ' Node 1.1.1' ' Node 1.2' 'Node 2' ' Node 2.1'
Assuming that you know that the root elements are zero, here's the pseudocode to output to text:
function PrintLevel (int curr, int level)
//print the indents
for (i=1; i<=level; i++)
print a tab
print curr \n;
for each child in the table with a parent of curr
PrintLevel (child, level+1)
for each elementID where the parentid is zero
PrintLevel(elementID, 0)
To Extend Bill's SQL solution you can basically do the same using a flat array. Further more if your strings all have the same lenght and your maximum number of children are known (say in a binary tree) you can do it using a single string (character array). If you have arbitrary number of children this complicates things a bit... I would have to check my old notes to see what can be done.
Then, sacrificing a bit of memory, especially if your tree is sparse and/or unballanced, you can, with a bit of index math, access all the strings randomly by storing your tree, width first in the array like so (for a binary tree):
String[] nodeArray = [L0root, L1child1, L1child2, L2Child1, L2Child2, L2Child3, L2Child4] ...
yo know your string length, you know it
I'm at work now so cannot spend much time on it but with interest I can fetch a bit of code to do this.
We use to do it to search in binary trees made of DNA codons, a process built the tree, then we flattened it to search text patterns and when found, though index math (revers from above) we get the node back... very fast and efficient, tough our tree rarely had empty nodes, but we could searh gigabytes of data in a jiffy.
This was written quickly, and is neither pretty nor efficient (plus it autoboxes alot, converting between int and Integer is annoying!), but it works.
It probably breaks the rules since I'm creating my own objects but hey I'm doing this as a diversion from real work :)
This also assumes that the resultSet/table is completely read into some sort of structure before you start building Nodes, which wouldn't be the best solution if you have hundreds of thousands of rows.
public class Node {
private Node parent = null;
private List<Node> children;
private String name;
private int id = -1;
public Node(Node parent, int id, String name) {
this.parent = parent;
this.children = new ArrayList<Node>();
this.name = name;
this.id = id;
}
public int getId() {
return this.id;
}
public String getName() {
return this.name;
}
public void addChild(Node child) {
children.add(child);
}
public List<Node> getChildren() {
return children;
}
public boolean isRoot() {
return (this.parent == null);
}
@Override
public String toString() {
return "id=" + id + ", name=" + name + ", parent=" + parent;
}
}
public class NodeBuilder {
public static Node build(List<Map<String, String>> input) {
// maps id of a node to it's Node object
Map<Integer, Node> nodeMap = new HashMap<Integer, Node>();
// maps id of a node to the id of it's parent
Map<Integer, Integer> childParentMap = new HashMap<Integer, Integer>();
// create special 'root' Node with id=0
Node root = new Node(null, 0, "root");
nodeMap.put(root.getId(), root);
// iterate thru the input
for (Map<String, String> map : input) {
// expect each Map to have keys for "id", "name", "parent" ... a
// real implementation would read from a SQL object or resultset
int id = Integer.parseInt(map.get("id"));
String name = map.get("name");
int parent = Integer.parseInt(map.get("parent"));
Node node = new Node(null, id, name);
nodeMap.put(id, node);
childParentMap.put(id, parent);
}
// now that each Node is created, setup the child-parent relationships
for (Map.Entry<Integer, Integer> entry : childParentMap.entrySet()) {
int nodeId = entry.getKey();
int parentId = entry.getValue();
Node child = nodeMap.get(nodeId);
Node parent = nodeMap.get(parentId);
parent.addChild(child);
}
return root;
}
}
public class NodePrinter {
static void printRootNode(Node root) {
printNodes(root, 0);
}
static void printNodes(Node node, int indentLevel) {
printNode(node, indentLevel);
// recurse
for (Node child : node.getChildren()) {
printNodes(child, indentLevel + 1);
}
}
static void printNode(Node node, int indentLevel) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < indentLevel; i++) {
sb.append("\t");
}
sb.append(node);
System.out.println(sb.toString());
}
public static void main(String[] args) {
// setup dummy data
List<Map<String, String>> resultSet = new ArrayList<Map<String, String>>();
resultSet.add(newMap("1", "Node 1", "0"));
resultSet.add(newMap("2", "Node 1.1", "1"));
resultSet.add(newMap("3", "Node 2", "0"));
resultSet.add(newMap("4", "Node 1.1.1", "2"));
resultSet.add(newMap("5", "Node 2.1", "3"));
resultSet.add(newMap("6", "Node 1.2", "1"));
Node root = NodeBuilder.build(resultSet);
printRootNode(root);
}
//convenience method for creating our dummy data
private static Map<String, String> newMap(String id, String name, String parentId) {
Map<String, String> row = new HashMap<String, String>();
row.put("id", id);
row.put("name", name);
row.put("parent", parentId);
return row;
}
}
You can emulate any other data structure with a hashmap, so that's not a terrible limitation. Scanning from the top to the bottom, you create a hashmap for each row of the database, with an entry for each column. Add each of these hashmaps to a "master" hashmap, keyed on the id. If any node has a "parent" that you haven't seen yet, create an placeholder entry for it in the master hashmap, and fill it in when you see the actual node.
To print it out, do a simple depth-first pass through the data, keeping track of indent level along the way. You can make this easier by keeping a "children" entry for each row, and populating it as you scan the data.
As for whether there's a "better" way to store a tree in a database, that depends on how you're going to use the data. I've seen systems that had a known maximum depth that used a different table for each level in the hierarchy. That makes a lot of sense if the levels in the tree aren't quite equivalent after all (top level categories being different than the leaves).
Assuming that you know that the root elements are zero, here's the pseudocode to output to text:
function PrintLevel (int curr, int level)
//print the indents
for (i=1; i<=level; i++)
print a tab
print curr \n;
for each child in the table with a parent of curr
PrintLevel (child, level+1)
for each elementID where the parentid is zero
PrintLevel(elementID, 0)
If nested hash maps or arrays can be created, then I can simply go down the table from the beginning and add each item to the nested array. I must trace each line to the root node in order to know which level in the nested array to insert into. I can employ memoization so that I do not need to look up the same parent over and over again.
Edit: I would read the entire table into an array first, so it will not query the DB repeatedly. Of course this won't be practical if your table is very large.
After the structure is built, I must do a depth first traverse through it and print out the HTML.
There's no better fundamental way to store this information using one table (I could be wrong though ;), and would love to see a better solution ). However, if you create a scheme to employ dynamically created db tables, then you opened up a whole new world at the sacrifice of simplicity, and the risk of SQL hell ;).
Assuming that you know that the root elements are zero, here's the pseudocode to output to text:
function PrintLevel (int curr, int level)
//print the indents
for (i=1; i<=level; i++)
print a tab
print curr \n;
for each child in the table with a parent of curr
PrintLevel (child, level+1)
for each elementID where the parentid is zero
PrintLevel(elementID, 0)
If you use nested sets (sometimes referred to as Modified Pre-order Tree Traversal) you can extract the entire tree structure or any subtree within it in tree order with a single query, at the cost of inserts being more expensive, as you need to manage columns which describe an in-order path through thee tree structure.
For django-mptt, I used a structure like this:
id parent_id tree_id level lft rght -- --------- ------- ----- --- ---- 1 null 1 0 1 14 2 1 1 1 2 7 3 2 1 2 3 4 4 2 1 2 5 6 5 1 1 1 8 13 6 5 1 2 9 10 7 5 1 2 11 12
Which describes a tree which looks like this (with id representing each item):
1
+-- 2
| +-- 3
| +-- 4
|
+-- 5
+-- 6
+-- 7
Or, as a nested set diagram which makes it more obvious how the lft and rght values work:
__________________________________________________________________________ | Root 1 | | ________________________________ ________________________________ | | | Child 1.1 | | Child 1.2 | | | | ___________ ___________ | | ___________ ___________ | | | | | C 1.1.1 | | C 1.1.2 | | | | C 1.2.1 | | C 1.2.2 | | | 1 2 3___________4 5___________6 7 8 9___________10 11__________12 13 14 | |________________________________| |________________________________| | |__________________________________________________________________________|
As you can see, to get the entire subtree for a given node, in tree order, you simply have to select all rows which have lft and rght values between its lft and rght values. It's also simple to retrieve the tree of ancestors for a given node.
The level column is a bit of denormalisation for convenience more than anything and the tree_id column allows you to restart the lft and rght numbering for each top-level node, which reduces the number of columns affected by inserts, moves and deletions, as the lft and rght columns have to be adjusted accordingly when these operations take place in order to create or close gaps. I made some development notes at the time when I was trying to wrap my head around the queries required for each operation.
In terms of actually working with this data to display a tree, I created a tree_item_iterator utility function which, for each node, should give you sufficient information to generate whatever kind of display you want.
More info about MPTT:
Think about using nosql tools like neo4j for hierarchial structures. e.g a networked application like linkedin uses couchbase (another nosql solution)
But use nosql only for data-mart level queries and not to store / maintain transactions
This was written quickly, and is neither pretty nor efficient (plus it autoboxes alot, converting between int and Integer is annoying!), but it works.
It probably breaks the rules since I'm creating my own objects but hey I'm doing this as a diversion from real work :)
This also assumes that the resultSet/table is completely read into some sort of structure before you start building Nodes, which wouldn't be the best solution if you have hundreds of thousands of rows.
public class Node {
private Node parent = null;
private List<Node> children;
private String name;
private int id = -1;
public Node(Node parent, int id, String name) {
this.parent = parent;
this.children = new ArrayList<Node>();
this.name = name;
this.id = id;
}
public int getId() {
return this.id;
}
public String getName() {
return this.name;
}
public void addChild(Node child) {
children.add(child);
}
public List<Node> getChildren() {
return children;
}
public boolean isRoot() {
return (this.parent == null);
}
@Override
public String toString() {
return "id=" + id + ", name=" + name + ", parent=" + parent;
}
}
public class NodeBuilder {
public static Node build(List<Map<String, String>> input) {
// maps id of a node to it's Node object
Map<Integer, Node> nodeMap = new HashMap<Integer, Node>();
// maps id of a node to the id of it's parent
Map<Integer, Integer> childParentMap = new HashMap<Integer, Integer>();
// create special 'root' Node with id=0
Node root = new Node(null, 0, "root");
nodeMap.put(root.getId(), root);
// iterate thru the input
for (Map<String, String> map : input) {
// expect each Map to have keys for "id", "name", "parent" ... a
// real implementation would read from a SQL object or resultset
int id = Integer.parseInt(map.get("id"));
String name = map.get("name");
int parent = Integer.parseInt(map.get("parent"));
Node node = new Node(null, id, name);
nodeMap.put(id, node);
childParentMap.put(id, parent);
}
// now that each Node is created, setup the child-parent relationships
for (Map.Entry<Integer, Integer> entry : childParentMap.entrySet()) {
int nodeId = entry.getKey();
int parentId = entry.getValue();
Node child = nodeMap.get(nodeId);
Node parent = nodeMap.get(parentId);
parent.addChild(child);
}
return root;
}
}
public class NodePrinter {
static void printRootNode(Node root) {
printNodes(root, 0);
}
static void printNodes(Node node, int indentLevel) {
printNode(node, indentLevel);
// recurse
for (Node child : node.getChildren()) {
printNodes(child, indentLevel + 1);
}
}
static void printNode(Node node, int indentLevel) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < indentLevel; i++) {
sb.append("\t");
}
sb.append(node);
System.out.println(sb.toString());
}
public static void main(String[] args) {
// setup dummy data
List<Map<String, String>> resultSet = new ArrayList<Map<String, String>>();
resultSet.add(newMap("1", "Node 1", "0"));
resultSet.add(newMap("2", "Node 1.1", "1"));
resultSet.add(newMap("3", "Node 2", "0"));
resultSet.add(newMap("4", "Node 1.1.1", "2"));
resultSet.add(newMap("5", "Node 2.1", "3"));
resultSet.add(newMap("6", "Node 1.2", "1"));
Node root = NodeBuilder.build(resultSet);
printRootNode(root);
}
//convenience method for creating our dummy data
private static Map<String, String> newMap(String id, String name, String parentId) {
Map<String, String> row = new HashMap<String, String>();
row.put("id", id);
row.put("name", name);
row.put("parent", parentId);
return row;
}
}
Bill's answer is pretty gosh-darned good, this answer adds some things to it which makes me wish SO supported threaded answers.
Anyway I wanted to support the tree structure and the Order property. I included a single property in each Node called leftSibling that does the same thing Order is meant to do in the original question (maintain left-to-right order).
mysql> desc nodes ; +-------------+--------------+------+-----+---------+----------------+ | Field | Type | Null | Key | Default | Extra | +-------------+--------------+------+-----+---------+----------------+ | id | int(11) | NO | PRI | NULL | auto_increment | | name | varchar(255) | YES | | NULL | | | leftSibling | int(11) | NO | | 0 | | +-------------+--------------+------+-----+---------+----------------+ 3 rows in set (0.00 sec) mysql> desc adjacencies; +------------+---------+------+-----+---------+----------------+ | Field | Type | Null | Key | Default | Extra | +------------+---------+------+-----+---------+----------------+ | relationId | int(11) | NO | PRI | NULL | auto_increment | | parent | int(11) | NO | | NULL | | | child | int(11) | NO | | NULL | | | pathLen | int(11) | NO | | NULL | | +------------+---------+------+-----+---------+----------------+ 4 rows in set (0.00 sec)
More detail and SQL code on my blog.
Thanks Bill your answer was helpful in getting started!
You can emulate any other data structure with a hashmap, so that's not a terrible limitation. Scanning from the top to the bottom, you create a hashmap for each row of the database, with an entry for each column. Add each of these hashmaps to a "master" hashmap, keyed on the id. If any node has a "parent" that you haven't seen yet, create an placeholder entry for it in the master hashmap, and fill it in when you see the actual node.
To print it out, do a simple depth-first pass through the data, keeping track of indent level along the way. You can make this easier by keeping a "children" entry for each row, and populating it as you scan the data.
As for whether there's a "better" way to store a tree in a database, that depends on how you're going to use the data. I've seen systems that had a known maximum depth that used a different table for each level in the hierarchy. That makes a lot of sense if the levels in the tree aren't quite equivalent after all (top level categories being different than the leaves).
It's a quite old question, but as it's got many views I think it's worth to present an alternative, and in my opinion very elegant, solution.
In order to read a tree structure you can use recursive Common Table Expressions (CTEs). It gives a possibility to fetch whole tree structure at once, have the information about the level of the node, its parent node and order within children of the parent node.
Let me show you how this would work in PostgreSQL 9.1.
Create a structure
CREATE TABLE tree (
id int NOT NULL,
name varchar(32) NOT NULL,
parent_id int NULL,
node_order int NOT NULL,
CONSTRAINT tree_pk PRIMARY KEY (id),
CONSTRAINT tree_tree_fk FOREIGN KEY (parent_id)
REFERENCES tree (id) NOT DEFERRABLE
);
insert into tree values
(0, 'ROOT', NULL, 0),
(1, 'Node 1', 0, 10),
(2, 'Node 1.1', 1, 10),
(3, 'Node 2', 0, 20),
(4, 'Node 1.1.1', 2, 10),
(5, 'Node 2.1', 3, 10),
(6, 'Node 1.2', 1, 20);
Write a query
WITH RECURSIVE
tree_search (id, name, level, parent_id, node_order) AS (
SELECT
id,
name,
0,
parent_id,
1
FROM tree
WHERE parent_id is NULL
UNION ALL
SELECT
t.id,
t.name,
ts.level + 1,
ts.id,
t.node_order
FROM tree t, tree_search ts
WHERE t.parent_id = ts.id
)
SELECT * FROM tree_search
WHERE level > 0
ORDER BY level, parent_id, node_order;
Here are the results:
id | name | level | parent_id | node_order
----+------------+-------+-----------+------------
1 | Node 1 | 1 | 0 | 10
3 | Node 2 | 1 | 0 | 20
2 | Node 1.1 | 2 | 1 | 10
6 | Node 1.2 | 2 | 1 | 20
5 | Node 2.1 | 2 | 3 | 10
4 | Node 1.1.1 | 3 | 2 | 10
(6 rows)
The tree nodes are ordered by a level of depth. In the final output we would present them in the subsequent lines.
For each level, they are ordered by parent_id and node_order within the parent. This tells us how to present them in the output - link node to the parent in this order.
Having such a structure it wouldn't be difficult to make a really nice presentation in HTML.
Recursive CTEs are available in PostgreSQL, IBM DB2, MS SQL Server and Oracle.
If you'd like to read more on recursive SQL queries, you can either check the documentation of your favourite DBMS or read my two articles covering this topic:
Well given the choice, I'd be using objects. I'd create an object for each record where each object has a children collection and store them all in an assoc array (/hashtable) where the Id is the key. And blitz through the collection once, adding the children to the relevant children fields. Simple.
But because you're being no fun by restricting use of some good OOP, I'd probably iterate based on:
function PrintLine(int pID, int level)
foreach record where ParentID == pID
print level*tabs + record-data
PrintLine(record.ID, level + 1)
PrintLine(0, 0)
Edit: this is similar to a couple of other entries, but I think it's slightly cleaner. One thing I'll add: this is extremely SQL-intensive. It's nasty. If you have the choice, go the OOP route.
As of Oracle 9i, you can use CONNECT BY.
SELECT LPAD(' ', (LEVEL - 1) * 4) || "Name" AS "Name"
FROM (SELECT * FROM TMP_NODE ORDER BY "Order")
CONNECT BY PRIOR "Id" = "ParentId"
START WITH "Id" IN (SELECT "Id" FROM TMP_NODE WHERE "ParentId" = 0)
As of SQL Server 2005, you can use a recursive common table expression (CTE).
WITH [NodeList] (
[Id]
, [ParentId]
, [Level]
, [Order]
) AS (
SELECT [Node].[Id]
, [Node].[ParentId]
, 0 AS [Level]
, CONVERT([varchar](MAX), [Node].[Order]) AS [Order]
FROM [Node]
WHERE [Node].[ParentId] = 0
UNION ALL
SELECT [Node].[Id]
, [Node].[ParentId]
, [NodeList].[Level] + 1 AS [Level]
, [NodeList].[Order] + '|'
+ CONVERT([varchar](MAX), [Node].[Order]) AS [Order]
FROM [Node]
INNER JOIN [NodeList] ON [NodeList].[Id] = [Node].[ParentId]
) SELECT REPLICATE(' ', [NodeList].[Level] * 4) + [Node].[Name] AS [Name]
FROM [Node]
INNER JOIN [NodeList] ON [NodeList].[Id] = [Node].[Id]
ORDER BY [NodeList].[Order]
Both will output the following results.
Name 'Node 1' ' Node 1.1' ' Node 1.1.1' ' Node 1.2' 'Node 2' ' Node 2.1'
You can emulate any other data structure with a hashmap, so that's not a terrible limitation. Scanning from the top to the bottom, you create a hashmap for each row of the database, with an entry for each column. Add each of these hashmaps to a "master" hashmap, keyed on the id. If any node has a "parent" that you haven't seen yet, create an placeholder entry for it in the master hashmap, and fill it in when you see the actual node.
To print it out, do a simple depth-first pass through the data, keeping track of indent level along the way. You can make this easier by keeping a "children" entry for each row, and populating it as you scan the data.
As for whether there's a "better" way to store a tree in a database, that depends on how you're going to use the data. I've seen systems that had a known maximum depth that used a different table for each level in the hierarchy. That makes a lot of sense if the levels in the tree aren't quite equivalent after all (top level categories being different than the leaves).
To Extend Bill's SQL solution you can basically do the same using a flat array. Further more if your strings all have the same lenght and your maximum number of children are known (say in a binary tree) you can do it using a single string (character array). If you have arbitrary number of children this complicates things a bit... I would have to check my old notes to see what can be done.
Then, sacrificing a bit of memory, especially if your tree is sparse and/or unballanced, you can, with a bit of index math, access all the strings randomly by storing your tree, width first in the array like so (for a binary tree):
String[] nodeArray = [L0root, L1child1, L1child2, L2Child1, L2Child2, L2Child3, L2Child4] ...
yo know your string length, you know it
I'm at work now so cannot spend much time on it but with interest I can fetch a bit of code to do this.
We use to do it to search in binary trees made of DNA codons, a process built the tree, then we flattened it to search text patterns and when found, though index math (revers from above) we get the node back... very fast and efficient, tough our tree rarely had empty nodes, but we could searh gigabytes of data in a jiffy.
If elements are in tree order, as shown in your example, you can use something like the following Python example:
delimiter = '.'
stack = []
for item in items:
while stack and not item.startswith(stack[-1]+delimiter):
print "</div>"
stack.pop()
print "<div>"
print item
stack.append(item)
What this does is maintain a stack representing the current position in the tree. For each element in the table, it pops stack elements (closing the matching divs) until it finds the parent of the current item. Then it outputs the start of that node and pushes it to the stack.
If you want to output the tree using indenting rather than nested elements, you can simply skip the print statements to print the divs, and print a number of spaces equal to some multiple of the size of the stack before each item. For example, in Python:
print " " * len(stack)
You could also easily use this method to construct a set of nested lists or dictionaries.
Edit: I see from your clarification that the names were not intended to be node paths. That suggests an alternate approach:
idx = {}
idx[0] = []
for node in results:
child_list = []
idx[node.Id] = child_list
idx[node.ParentId].append((node, child_list))
This constructs a tree of arrays of tuples(!). idx[0] represents the root(s) of the tree. Each element in an array is a 2-tuple consisting of the node itself and a list of all its children. Once constructed, you can hold on to idx[0] and discard idx, unless you want to access nodes by their ID.
If nested hash maps or arrays can be created, then I can simply go down the table from the beginning and add each item to the nested array. I must trace each line to the root node in order to know which level in the nested array to insert into. I can employ memoization so that I do not need to look up the same parent over and over again.
Edit: I would read the entire table into an array first, so it will not query the DB repeatedly. Of course this won't be practical if your table is very large.
After the structure is built, I must do a depth first traverse through it and print out the HTML.
There's no better fundamental way to store this information using one table (I could be wrong though ;), and would love to see a better solution ). However, if you create a scheme to employ dynamically created db tables, then you opened up a whole new world at the sacrifice of simplicity, and the risk of SQL hell ;).
Well given the choice, I'd be using objects. I'd create an object for each record where each object has a children collection and store them all in an assoc array (/hashtable) where the Id is the key. And blitz through the collection once, adding the children to the relevant children fields. Simple.
But because you're being no fun by restricting use of some good OOP, I'd probably iterate based on:
function PrintLine(int pID, int level)
foreach record where ParentID == pID
print level*tabs + record-data
PrintLine(record.ID, level + 1)
PrintLine(0, 0)
Edit: this is similar to a couple of other entries, but I think it's slightly cleaner. One thing I'll add: this is extremely SQL-intensive. It's nasty. If you have the choice, go the OOP route.
This was written quickly, and is neither pretty nor efficient (plus it autoboxes alot, converting between int and Integer is annoying!), but it works.
It probably breaks the rules since I'm creating my own objects but hey I'm doing this as a diversion from real work :)
This also assumes that the resultSet/table is completely read into some sort of structure before you start building Nodes, which wouldn't be the best solution if you have hundreds of thousands of rows.
public class Node {
private Node parent = null;
private List<Node> children;
private String name;
private int id = -1;
public Node(Node parent, int id, String name) {
this.parent = parent;
this.children = new ArrayList<Node>();
this.name = name;
this.id = id;
}
public int getId() {
return this.id;
}
public String getName() {
return this.name;
}
public void addChild(Node child) {
children.add(child);
}
public List<Node> getChildren() {
return children;
}
public boolean isRoot() {
return (this.parent == null);
}
@Override
public String toString() {
return "id=" + id + ", name=" + name + ", parent=" + parent;
}
}
public class NodeBuilder {
public static Node build(List<Map<String, String>> input) {
// maps id of a node to it's Node object
Map<Integer, Node> nodeMap = new HashMap<Integer, Node>();
// maps id of a node to the id of it's parent
Map<Integer, Integer> childParentMap = new HashMap<Integer, Integer>();
// create special 'root' Node with id=0
Node root = new Node(null, 0, "root");
nodeMap.put(root.getId(), root);
// iterate thru the input
for (Map<String, String> map : input) {
// expect each Map to have keys for "id", "name", "parent" ... a
// real implementation would read from a SQL object or resultset
int id = Integer.parseInt(map.get("id"));
String name = map.get("name");
int parent = Integer.parseInt(map.get("parent"));
Node node = new Node(null, id, name);
nodeMap.put(id, node);
childParentMap.put(id, parent);
}
// now that each Node is created, setup the child-parent relationships
for (Map.Entry<Integer, Integer> entry : childParentMap.entrySet()) {
int nodeId = entry.getKey();
int parentId = entry.getValue();
Node child = nodeMap.get(nodeId);
Node parent = nodeMap.get(parentId);
parent.addChild(child);
}
return root;
}
}
public class NodePrinter {
static void printRootNode(Node root) {
printNodes(root, 0);
}
static void printNodes(Node node, int indentLevel) {
printNode(node, indentLevel);
// recurse
for (Node child : node.getChildren()) {
printNodes(child, indentLevel + 1);
}
}
static void printNode(Node node, int indentLevel) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < indentLevel; i++) {
sb.append("\t");
}
sb.append(node);
System.out.println(sb.toString());
}
public static void main(String[] args) {
// setup dummy data
List<Map<String, String>> resultSet = new ArrayList<Map<String, String>>();
resultSet.add(newMap("1", "Node 1", "0"));
resultSet.add(newMap("2", "Node 1.1", "1"));
resultSet.add(newMap("3", "Node 2", "0"));
resultSet.add(newMap("4", "Node 1.1.1", "2"));
resultSet.add(newMap("5", "Node 2.1", "3"));
resultSet.add(newMap("6", "Node 1.2", "1"));
Node root = NodeBuilder.build(resultSet);
printRootNode(root);
}
//convenience method for creating our dummy data
private static Map<String, String> newMap(String id, String name, String parentId) {
Map<String, String> row = new HashMap<String, String>();
row.put("id", id);
row.put("name", name);
row.put("parent", parentId);
return row;
}
}
There are really good solutions which exploit the internal btree representation of sql indices. This is based on some great research done back around 1998.
Here is an example table (in mysql).
CREATE TABLE `node` (
`id` int(10) unsigned NOT NULL AUTO_INCREMENT,
`name` varchar(255) NOT NULL,
`tw` int(10) unsigned NOT NULL,
`pa` int(10) unsigned DEFAULT NULL,
`sz` int(10) unsigned DEFAULT NULL,
`nc` int(11) GENERATED ALWAYS AS (tw+sz) STORED,
PRIMARY KEY (`id`),
KEY `node_tw_index` (`tw`),
KEY `node_pa_index` (`pa`),
KEY `node_nc_index` (`nc`),
CONSTRAINT `node_pa_fk` FOREIGN KEY (`pa`) REFERENCES `node` (`tw`) ON DELETE CASCADE
)
The only fields necessary for the tree representation are:
Here is an example 24 node population, ordered by tw:
+-----+---------+----+------+------+------+
| id | name | tw | pa | sz | nc |
+-----+---------+----+------+------+------+
| 1 | Root | 1 | NULL | 24 | 25 |
| 2 | A | 2 | 1 | 14 | 16 |
| 3 | AA | 3 | 2 | 1 | 4 |
| 4 | AB | 4 | 2 | 7 | 11 |
| 5 | ABA | 5 | 4 | 1 | 6 |
| 6 | ABB | 6 | 4 | 3 | 9 |
| 7 | ABBA | 7 | 6 | 1 | 8 |
| 8 | ABBB | 8 | 6 | 1 | 9 |
| 9 | ABC | 9 | 4 | 2 | 11 |
| 10 | ABCD | 10 | 9 | 1 | 11 |
| 11 | AC | 11 | 2 | 4 | 15 |
| 12 | ACA | 12 | 11 | 2 | 14 |
| 13 | ACAA | 13 | 12 | 1 | 14 |
| 14 | ACB | 14 | 11 | 1 | 15 |
| 15 | AD | 15 | 2 | 1 | 16 |
| 16 | B | 16 | 1 | 1 | 17 |
| 17 | C | 17 | 1 | 6 | 23 |
| 359 | C0 | 18 | 17 | 5 | 23 |
| 360 | C1 | 19 | 18 | 4 | 23 |
| 361 | C2(res) | 20 | 19 | 3 | 23 |
| 362 | C3 | 21 | 20 | 2 | 23 |
| 363 | C4 | 22 | 21 | 1 | 23 |
| 18 | D | 23 | 1 | 1 | 24 |
| 19 | E | 24 | 1 | 1 | 25 |
+-----+---------+----+------+------+------+
Every tree result can be done non-recursively. For instance, to get a list of ancestors of node at tw='22'
Ancestors
select anc.* from node me,node anc
where me.tw=22 and anc.nc >= me.tw and anc.tw <= me.tw
order by anc.tw;
+-----+---------+----+------+------+------+
| id | name | tw | pa | sz | nc |
+-----+---------+----+------+------+------+
| 1 | Root | 1 | NULL | 24 | 25 |
| 17 | C | 17 | 1 | 6 | 23 |
| 359 | C0 | 18 | 17 | 5 | 23 |
| 360 | C1 | 19 | 18 | 4 | 23 |
| 361 | C2(res) | 20 | 19 | 3 | 23 |
| 362 | C3 | 21 | 20 | 2 | 23 |
| 363 | C4 | 22 | 21 | 1 | 23 |
+-----+---------+----+------+------+------+
Siblings and children are trivial - just use pa field ordering by tw.
Descendants
For example the set (branch) of nodes that are rooted at tw = 17.
select des.* from node me,node des
where me.tw=17 and des.tw < me.nc and des.tw >= me.tw
order by des.tw;
+-----+---------+----+------+------+------+
| id | name | tw | pa | sz | nc |
+-----+---------+----+------+------+------+
| 17 | C | 17 | 1 | 6 | 23 |
| 359 | C0 | 18 | 17 | 5 | 23 |
| 360 | C1 | 19 | 18 | 4 | 23 |
| 361 | C2(res) | 20 | 19 | 3 | 23 |
| 362 | C3 | 21 | 20 | 2 | 23 |
| 363 | C4 | 22 | 21 | 1 | 23 |
+-----+---------+----+------+------+------+
Additional Notes
This methodology is extremely useful for when there are a far greater number of reads than there are inserts or updates.
Because the insertion, movement, or updating of a node in the tree requires the tree to be adjusted, it is necessary to lock the table before commencing with the action.
The insertion/deletion cost is high because the tw index and sz (branch size) values will need to be updated on all the nodes after the insertion point, and for all ancestors respectively.
Branch moving involves moving the tw value of the branch out of range, so it is also necessary to disable foreign key constraints when moving a branch. There are, essentially four queries required to move a branch:
Adjust Tree Queries
The opening/closing of gaps in the tree is an important sub-function used by create/update/delete methods, so I include it here.
We need two parameters - a flag representing whether or not we are downsizing or upsizing, and the node's tw index. So, for example tw=18 (which has a branch size of 5). Let's assume that we are downsizing (removing tw) - this means that we are using '-' instead of '+' in the updates of the following example.
We first use a (slightly altered) ancestor function to update the sz value.
update node me, node anc set anc.sz = anc.sz - me.sz from
node me, node anc where me.tw=18
and ((anc.nc >= me.tw and anc.tw < me.pa) or (anc.tw=me.pa));
Then we need to adjust the tw for those whose tw is higher than the branch to be removed.
update node me, node anc set anc.tw = anc.tw - me.sz from
node me, node anc where me.tw=18 and anc.tw >= me.tw;
Then we need to adjust the parent for those whose pa's tw is higher than the branch to be removed.
update node me, node anc set anc.pa = anc.pa - me.sz from
node me, node anc where me.tw=18 and anc.pa >= me.tw;
Assuming that you know that the root elements are zero, here's the pseudocode to output to text:
function PrintLevel (int curr, int level)
//print the indents
for (i=1; i<=level; i++)
print a tab
print curr \n;
for each child in the table with a parent of curr
PrintLevel (child, level+1)
for each elementID where the parentid is zero
PrintLevel(elementID, 0)
To Extend Bill's SQL solution you can basically do the same using a flat array. Further more if your strings all have the same lenght and your maximum number of children are known (say in a binary tree) you can do it using a single string (character array). If you have arbitrary number of children this complicates things a bit... I would have to check my old notes to see what can be done.
Then, sacrificing a bit of memory, especially if your tree is sparse and/or unballanced, you can, with a bit of index math, access all the strings randomly by storing your tree, width first in the array like so (for a binary tree):
String[] nodeArray = [L0root, L1child1, L1child2, L2Child1, L2Child2, L2Child3, L2Child4] ...
yo know your string length, you know it
I'm at work now so cannot spend much time on it but with interest I can fetch a bit of code to do this.
We use to do it to search in binary trees made of DNA codons, a process built the tree, then we flattened it to search text patterns and when found, though index math (revers from above) we get the node back... very fast and efficient, tough our tree rarely had empty nodes, but we could searh gigabytes of data in a jiffy.
Source: Stackoverflow.com