Storing Hierarchical Data in Database using Modified Preorder Tree Traversal Method:
Consider the following tree structure:
Food
|
————————-
| |
Fruit Meat
——— ———-
| | | |
Red Yellow Beef Pork
Step 1:
=====
Start Numbering the nodes. Start from the root node. Each node will have left ane right values.
For Eg: Assign “1″ to the left side of root node “Food”. Assign “2″ to the left side of “Fruit” node and “3″ to the left side of “Red” node.
[1] Food [14]
|
——————————
| |
[2] Fruit [7] [8] Meat [13]
————- ——————
| | | |
[3] Red [4] [5] Yellow [6] [9] Beef [10] [11] Pork [12]
Note: The Right Value of the root node “Food” will have the highest value.
This method of walking around the tree and counting nodes is called the ‘modified preorder tree traversal’ algorithm
Database Structure and Value will be as follows:
Parent Title lft rgt
==============================
Food 1 14
Food Fruit 2 7
Fruit Red 3 4
Fruit Yellow 5 6
Food Meat 8 13
Meat Beed 9 10
Meat Pork 11 12
EXAMPLES:
========
1. if you want the ‘Fruit’ subtree, you’ll have to select only the nodes with a left value between 2 and 7. In SQL, that would be:
SELECT * FROM tree WHERE lft BETWEEN 2 AND 7 ORDER BY lft ASC;
If you add and delete rows from your table, your table probably won’t be in the right order. We should therefore order the rows by their left value
[ORDER BY lft ASC].
2. if you want the ‘Meat’ subtree, you’ll have to select only the nodes with a left value between 8 and 13. In SQL, that would be:
SELECT * FROM tree WHERE lft BETWEEN 8 AND 13 ORDER BY lft ASC;
ADD A NODE AT MIDDLE:
==================
If we want to add a node at the middle position, say for eg, a child node for the node “Red” , we have to follow the following steps:
1. First, we’ll have to make some space by changing the right value and left value of “Red” and the other following node values.
[1] Food [16]
|
——————————
| |
[2] Fruit [9] [10] Meat [15]
————- ——————
| | | |
[3] Red [6] [7] Yellow [8] [11] Beef [12] [13] Pork [14]
|
[4] Cherry [5]
2. Following query is used to update the right and left values:
UPDATE tree SET rgt=rgt+2 WHERE rgt>4;
UPDATE tree SET lft=lft+2 WHERE lft>4;
we need to add 2 values to both left and right. For eg: Previously, the right value for node “Red” is [4] and now it is changed to [6]. Similarly
we have to do for all other nodes.
3. After Altering the node values we have to insert a new node. Following is the query used to insert a new node:
INSERT INTO tree SET lft=4, rgt=5, title=’Cherry’;
ADDING A NODE AT END:
===================
Following SQL query must be executed to Add a node at the end ie a child node to the node “Pork”.
UPDATE tree SET rgt=rgt+2 WHERE rgt>14;
INSERT INTO tree SET lft=14, rgt=15, title=’New’;
SAMPLE CODE TO DISPLAY TREE STRUCTURE:
==================================
0) {
// check if we should remove a node from the stack
while ($right[count($right)-1]
A right values of the nodes need to kept in a stack to show the tree structure:
$right = array();
Add the right value of node to the stack each time when we start with the children of a node:
$right[] = $row[’rgt’];
All children of that node have a right value that is less than the right value of the parent, so by comparing the right value of the current node with
the last right node in the stack, we can see if we’re still displaying the children of that parent.
while ($right[count($right)-1]
