Adjacency list approach to handle child and parent nodes in tree hierarchy

by kalai 2008-01-19 20:05:14

Simple approach to retrieve all the childs belonging to a particular parent is done by modifying the table show below

id name parentid
1 category 0
2 Php 1
3 Perl 1
4 ASP 1
5 Php Script 2
6 Php code 2
7 perl Script 3
The tree structure of above table is shown below

category
|
________________________
| | |
Php Perl ASP

| |
_________ |
| |
Php Script Php Code Perl Script

Along with the above fields in the table an addition of two fields left and right is maintained.

id name parentid left right
1 category 0 1 14
2 Php 1 2 7
3 Perl 1 8 11
4 ASP 1 12 13
5 Php Script 2 3 4
6 Php code 2 5 6
7 perl Script 3 9 10

The left and right values are entered by numbering nodes for each visit based on following condition
If root node is visited then the left of root node 'category' is marked as '1' and if child is present and the link is traversed to child node 'php' and left is child node is marked as '2' , and then traversed to child node 'Php Script' and left of 'Php Script is marked as '3', and then search of child below 'php Script' is done , as there is no child present then the right of 'php script' is marked as '4', another child 'php code' is balance below php so it's left is marked as '5' and there is no child present below php code so its right is marked as 6, now there is no child is left without marking so right of php is marked as 7 and the value of left and right of all other nodes are marked in the same procedure. Finally left and right values of all the nodes will be marked.

Using above modified table we can retrieve whatever we require by using query.

For Example
1. Retrieve parents of child 'Php Script'.

select o2.name from category as o1, category as o2 where o1.left between o2.left and o2.right and o1.name="Php Scritp";

Result: category, Php .










Tagged in:

1748
like
1
dislike
0
mail
flag

You must LOGIN to add comments