This is my very first blog post
so I hope you will share your feeling about my post. Is it helpful? Am I
talking too detailed or too general? Is the font easy for you to read? If there
is any problem you think that would help me in later posts, please send me a
message or comment on this post. Thank you!
I’m going to our topic now. This
article addresses the following issues:
If you know well about one issue,
you should bypass it and read the part that is suitable for you.
One of a common task is to insert
data in tree-form into database, such as the navigation tree like
--Drink
----Coke
----Pepsi
--Food
----Pork
----Beef
Example 1
You’re finding a way so that when you retrieving the data
back from the database, you can represent it in nested <ul> and <li>
form. If this is your case, then there’re some options for you:
Perhaps the third solution has more advantage over the other
two, but if you choose ALM (or sometimes your co-worker ask you to use ALM)
then this article is a simple solution for it.
Here I’m simply giving the presentation of Example 1 in
relational database if you choose ALM:
Table 1
That’s it. That’s how your data would look like in your
database for ALM. Now I’m gonna give you my library to convert that type of
data to tree in php and java. For those who would like to do quick work, read
part 2. Who want to know more about my method before implementing it please
read part 3 and 4 first.
Please follow download link
to download the library.
The ALM2Tree.7z should be extract by 7zip. Now you got 4
files:
- Base_category.php: It is the data structure as in Table1. Each Base_category object represent one row in Table 1.
- Node: It is the combination of a Base_category, a pointer to the Node’s father and an array of pointer to the Node’s children.
- CTree: It contains one Node named $root and 2 stack: $stack1 and $stack2.
We also have array $orphan. If finally the new element cannot insert to our tree, then it has no father and we push it to $orphan array.
I will explain it in detail in part 3.
To use the library, you should:
1) Code some line to get data from your database. Supposed that you have your data in $your_data2) Code some line to convert it to an array of Base_category object. An example of how to initialize Base_category object is as follow:
$bc = new Base_category(7, “Food”, 1) ; // 7: ID of Food. 1:
parent_id of Food
2) After the 2) step you should have array $arr. Now you
should initialize a CTree object by
$tree = new Ctree() ;
4) To Convert $arr to tree, simply use:
$tree->build_tree($arr) ;
That’s it. It’s quite simple, huh. Now how can you use your
tree? I have prepare some methods for you:
Get_root() // Return the Node $root
Get_orphan() // Return array of Base_category $orphan
Get_leaves( $id ) // Get all id of leave Nodes in sub-tree
rooting from the node that has id = $id
Get_descendants( $id ) //Get all descendants (Node) of the
node that has id = $id
My advice is to run my test.php file and see the result. You
could print_r the result to see the data structure to write new function if you
need. I have commented all my code so have a look at it. Hope it helps!
I am not saying that I’ve devised new algorithm. It’s quite
a simple and common problem thus I think there are bunch of solution for it.
But the fact that I didn’t read the algorithm anywhere and I now publish my
code, I should explain how the code runs.
ALM2Tree Algorithm
Input: An array of Base_category object $arr
Output: A Ctree object which contains Node $root and array
of Base_category $orphan
1. Create $stack1 and $stack2
2. Transfer all element from $arr to $stack1
3. While $stack1 and $stack2 is not empty
3.1 If size
of $stack1 and size of $stack2 are equal
Return
3.2 Try to
insert each element from $stack1 to the tree until $stack1 is empty
3.3
Recalculate the size of $stack1
3.4 Try to
insert each element of $stack2 to the tree untial $stack2 is empty
3.3
Recalculate the size of $stack2
The condition in 3.1 is when we have orphans and the tree has been built as fullest as possible.
The steps 3.2 and 3.4 use the add( $c ) function ( $c:
Base_category object ). It is called by a Node object, i.e the $root.
The algorithm for a Node to add a Base_category
Input: An object whose type is Base_category: $c
Output: void. Either $c will be added to the Node’s
descendants or $c will be add to opposite stack. With “opposite”, I mean, for
example, $c is poped from $stack1 then $stack2 is the opposite stack. $stack1
and $stack2 are static variables.
- Find descendants of the current Node, supposed we have $des array
- If $c->pid is not equal to any ids of Nodes in $des, then $c is orphan (at this moment only – may be $c’s father will be inserted later. See Figure 1)
- Else
- Find current node's direct child that leads to the father of $c, we call it node A (See Figure 2)
- when node A found, recursively call add() function at node A (i.e use $A.add($c) )
Figure 1
Figure 2
Figure 3
The worse situation for ALM2Tree Algorithm is as Figure 3. If it happens, we only insert one element to the tree for each round. Thus the complexity is O(n!) with n is the number of elements which need to be inserted to the tree.
In fact, when I applied this algorithm, my website provided a way such that a sub-category could only be created if it belongs to another valid category. Thus in my database, data was in “right” order: father first, then comes it children. The complexity in my case was O(n).
