Implementation algorithm for parsing infinite classification of left and right values

1. Introduction
Product classification, multi-level tree structure forums, mailing lists and many other places we will encounter such problems: how to store multi-level Structured data? In PHP applications, the backend data storage is usually a relational database, which can save large amounts of data and provide efficient data retrieval and update services. However, the basic form of relational data is a criss-crossed table, which is a flat structure. If you want to store a multi-level tree structure in a relational database, you need to perform reasonable translation work. Next, I will discuss what I have seen and heard and some practical experience with you:
There are basically two common design methods for storing hierarchical data in a flat database:
* Adjacency list model (adjacency list model)
* Modified preorder tree traversal algorithm (modified preorder tree traversal algorithm)
I am not a computer major, nor have I learned any data structures Things, so I translated these two names according to their literal meanings. Please tell me if I am wrong. These two things may sound scary, but they are actually very easy to understand.

2. Model
Here I use a simple food catalog as our example data.
Our data structure is like this, the following is the code:

Copy the code The code is as follows:

Food

|---Fruit

| |---Red

| |--Cherry

| +---Yellow

|              +--Banana

+---Meat
                                                                                                                    🎜>

Copy code

The code is as follows:

Food : FoodFruit : FruitRed : Red

Cherry : Cherry

Yellow: Yellow
Banana: Banana
Meat: Meat
Beef: Beef
Pork: Pork




3. Implementation 

1. Adjacency list model
This model is often used and has been introduced in many tutorials and books. We describe the entire tree structure through a flat table by adding an attribute parent to each node to represent the parent node of this node. According to this principle, the data in the example can be transformed into the following table: The following is the code:

Copy the code

The code is as follows:

+-----------------------+| parent | name |+--------- ----------------+

| Food |

| Food | Fruit |
| Fruit | Green |
| Green | Pear |
| Fruit | Red |
| Red | Cherry |
| Fruit | Yellow |
| Yellow | Banana |
| Food | Meat |
| Meat | at | Pork |
+-----------------------+


We see that Pear is a child node of Green, Green is a child node of Fruit. The root node 'Food' has no parent node. In order to describe this problem simply, only name is used to represent a record in this example. In an actual database, you need to use a numeric ID to identify each node. The table structure of the database should probably look like this: id, parent_id, name, descrīption. 
With such a table, we can save the entire multi-level tree structure through the database. 
Display a multi-level tree. If we need to display such a multi-level structure, we need a recursive function. 
The following is the code:

Copy the code

The code is as follows:

// $parent is the parent of the children we want to see
// $level is increased when we go deeper into the tree,
// used to display a nice indented tree
function display_children($parent, $level) {
 // Get all child nodes of a parent node $parent
 $result = mysql_query("
 SELECT name
 From Tree  Where Parent = '". $ Parent."' 
; "
); 
 // Display each sub -node 
 While ($ row = mysql_fetch_array ($ result)) {
                                                                                                                                                                                                            echo str_repeat(' ', $level) . $row['name'] . "n"; Node
 display_children($row['name'], $level+1);
 }
}
?>


 for the root node of the entire structure ( Food) You can use this function to print out the entire multi-level tree structure. Since Food is the root node and its parent node is empty, it is called like this: display_children('',0). The contents of the entire tree will be displayed: 

Copy the code

The code is as follows: Food

Fruit

 Red
 Cherry  YELLOW 
 Banana 
 Meat 
 Beef 
 Pork 
 
 
 If you just want to display a part of the entire structure, such as the fruit part, you can do this. Call: display_children('Fruit',0);
Almost using the same method, we can know the path from the root node to any node. For example, Cherry's path is "Food >; Fruit >; Red". In order to get such a path, we need to start from the deepest level "Cherry", query to get its parent node "Red" and add it to the path, and then we query Red's parent node and add it to the path. , and so on until the top level "Food", the following is the code: 

Copy the code

The code is as follows: < ?php// $node is the deepest node

function get_path($node) {

 // Query the parent node of this node
 $result = mysql_query("
 SELECT parent< E> From Tree 
 where name = '". $ Node."' 
; "
); 
 $ row = mysql_fetch_array ($ result); 
 $path = array();
 // If it is not the root node, continue to search upwards 
 // (The root node has no parent node)
 if ($row['parent'] != ' ') {
 // the last part of the path to $node, is the name
 // of the parent of $node
 $path[] = $row['parent'];
           // we should add the path to the parent of this node
            // to the path
                                                                                                                                                                                                          🎜> // return the path
 return $path;
}
?>;


If you use this function for "Cherry": print_r(get_path('Cherry' )), you will get an array like this: 



 Copy the code 

 The code is as follows: 

Array (

[ 0] => Food [1] => Fruit [2] => Red)

How to print it into the format you want is up to you.
Disadvantages:
This method is very simple, easy to understand, and easy to use. But there are some disadvantages. Mainly because the running speed is very slow, because each node requires a database query, and when the amount of data is large, many queries are required to complete a tree. In addition, due to the need for recursive operations, each level of recursion needs to occupy some memory, so the space utilization efficiency is relatively low.

2. Presorted tree traversal algorithm
Now let us take a look at another faster method that does not use recursive calculations. This is the presorted tree traversal algorithm (modified preorder tree traversal algorithm)
You may have less exposure to this method, and it is not as easy to understand as the above method when you use it for the first time. However, because this method does not use a recursive query algorithm, it has higher query efficiency.

We first draw the multi-level data on paper as follows, write 1 to the left of the root node Food, then continue down the tree, write 2 to the left of Fruit, and continue moving forward. , label each node with numbers on the left and right along the edge of the entire tree. The last number is 18 marked to the right of Food. In the picture below you can see the entire multi-level structure marked with numbers. (Don’t understand? Point to the numbers with your fingers and count from 1 to 18 and you will understand. If you still don’t understand, count again and pay attention to moving your fingers).
These numbers indicate the relationship between each node. The numbers of "Red" are 3 and 6, which are the descendant nodes of "Food" 1-18. Similarly, we can see that all nodes with left values greater than 2 and right values less than 11 are descendant nodes of "Fruit" 2-11
The following is the code:

Copy code The code is as follows: --------+

 2 Fruit 11 12 Meat 17

 +-------------+ +------ -----+

3 Red 6 7 Yellow 10 13 Beef 14 15 Pork 16

4 Cherry 5 8 Banana 9

This is the entire tree structure Can be stored in the database by left and right values. Before continuing, let's take a look at the compiled data table below. 
The following is the code:

Copy the code

The code is as follows:

+---------- +----------------+-----+-----+| parent | name | lft | rgt |+-------- --+----------------+-----+-----+

| | Food | 1 | 18 |

| Food | Fruit | 2 | 11 |
| Fruit | Red | 3 | 6 |
| Red | Cherry | 4 | 5 |
| Fruit | Yellow | 7 | 10 |
| Yellow | Banana | 8 | 9 |
| Food | Meat | 12 | 17 |
| Meat | Beef | 13 | 14 |
| Meat | Pork | 15 | 16 |
+----------+ ------------+-----+-----+




Note: 

Due to" "left" and "right" have special meaning in SQL, so we need to use "lft" and "rgt" to represent the left and right fields. In addition, the "parent" field is no longer needed in this structure to represent the tree structure. In other words, the following table structure is sufficient.
The following is the code:Copy the code

The code is as follows:

+------------+-----+-----+
| name | lft | rgt |
+---- --------+-----+-----+
| Food | 1 | 18 |
| Fruit | 2 | 11 |
| Red | 3 | 6 |
| Cherry | 4 | 5 |
| Yellow | 7 | 10 |
| Banana | 8 | 9 |
| Meat | 12 | 17 |
| Beef | 13 | 14 |
| Pork | 15 | 16 |
+------------+-----+-----+

Okay Now we can get data from the database. For example, if we need to get all the nodes under the "Fruit" item, we can write the query statement like this:

Copy code The code is as follows:

SELECT * FROM tree WHERE lft BETWEEN 2 AND 11;

This query got the following results.
The following is the code:

Copy the code The code is as follows:

+---------- --+-----+-----+
| name | lft | rgt |
+------------+-----+-- ---+
| Fruit | 2 | 11 |
| Red | 3 | 6 |
| Cherry | 4 | 5 |
| Yellow | 7 | 10 |
| Banana | 8 | 9 |
+------------+-----+-----+

See it, just one query All these nodes are available. In order to be able to display the entire tree structure like the recursive function above, we also need to sort such a query. Sort by the lvalue of the node:

Copy code The code is as follows:

SELECT * FROM tree WHERE lft BETWEEN 2 AND 11 ORDER BY lft ASC;

The remaining question is how to display the level of indentation.
The following is the code:

Copy the code The code is as follows:

function display_tree($ root) {
// Get the left and right values of the root node
$result = mysql_query("
SELECT lft, rgt
FROM tree
WHERE name = '" . $root . "'
; "
);
$row = mysql_fetch_array($result);
// Prepare an empty rvalue stack
$right = array();
// Get the base All descendant nodes of point
$result = mysql_query("
SELECT name, lft, rgt
FROM tree
WHERE lft BETWEEN '" . $row['lft'] . "' AND '" . $row['rgt'] ."'
          ORDER BY lft ASC
         ;"
     ); {
// only check stack if there is one
if (count($right) > 0) {
($right) - 1] < $row['rgt']) {
str_repeat(' ',count($right)) . $row['name'] . "n";
// Add this node to the stack ];
}
}
?>

If you run the above function you will get the same result as the recursive function. It's just that our new function may be faster because there are only 2 database queries.
It is easier to know the path of a node. If we want to know the path of Cherry, we can use its left and right values 4 and 5 to make a query.

Copy code The code is as follows:

SELECT name FROM tree WHERE lft < 4 AND rgt >; 5 ORDER BY lft ASC;

This will get the following results:
The following is the code:

Copy the codeThe code is as follows:

+----------------+
| name |
+----------------+
| Food |
| Fruit |
| Red |
+------------+

So how many descendant nodes does a certain node have? Very simple, the total number of descendants = (rvalue - left value - 1)/2

Copy code The code is as follows:

descendants = (right – left - 1) / 2

Don’t believe it? Do the math yourself.
Using this simple formula, we can quickly calculate that the "Fruit 2-11" node has 4 descendant nodes, while the "Banana 8-9" node has no descendant nodes, which means that it is not a parent Node.
Amazing, right? Although I have used this method many times, it still feels amazing every time I do it.
This is indeed a good method, but is there any way to help us create such a data table with left and right values? Here is another function to introduce to you. This function can automatically convert the table with name and parent structures into a data table with left and right values.
The following is the code:

Copy the code The code is as follows:

function rebuild_tree($ parent, $left) {
 // the right value of this node is the left value + 1
 $right = $left+1;
 // get all children of this node
 $result = mysql_query("
 SELECT name
 FROM tree
 WHERE parent = '" . $parent . "'
 ;"
 );
 while ($row = mysql_fetch_array($re sult )) {
 // recursive execution of this function for each
 🎜>        $right = rebuild_tree($row['name'], $right);
    }
       // we've got the left value, and now that we've processed
      // the children of this node we also know the right value
 mysql_query("
 UPDATE tree
 SET
 lft = '" . $left . "',
 rgt= '" . $right . " '
 WHERE name = '" . $parent . "'
 ; "
 );
 // return the right value of this node + 1
 return $right + 1;
}
?>


Of course this function is a recursive function, we need to run this function from the root node to reconstruct a tree with left and right values

Copy code

The code is as follows:rebuild_tree('Food',1);

This function looks a bit complicated, but its function is the same as manually numbering the table, which is to convert the three-dimensional multi-layer structure into a data table with left and right values.
So how do we add, update and delete a node for such a structure?
There are generally two ways to add a node:
The first one, retain the original name and parent structure, use The old method adds data to the data, and uses the rebuild_tree function to renumber the entire structure after each piece of data is added.
The second, more efficient way is to change all the values located on the right side of the new node. For example: we want to add a new fruit "Strawberry" which will become the last child node of the "Red" node. First we need to make some space for it. The right value of "Red" should be changed from 6 to 8, and the left and right value of "Yellow 7-10" should be changed to 9-12. By analogy, we can know that if you want to make room for new values, you need to add 2 to all nodes with left and right values greater than 5 (5 is the right value of the last child node of "Red"). So we perform database operations like this:

Copy code The code is as follows:

UPDATE tree SET rgt = rgt + 2 WHERE rgt > ; 5;
UPDATE tree SET lft = lft + 2 WHERE lft > 5;

This frees up space for the newly inserted value, which can now be created in the freed space A new data node, its left and right values are 6 and 7 respectively

Copy code The code is as follows:

INSERT INTO tree SET lft=6, rgt=7, name='Strawberry';

Let’s do another query and see! How about it? Soon.

4. Conclusion
Okay, now you can design your multi-level database structure in two different ways. Which method you use depends entirely on you. Personal judgment, but for structures with many levels and large quantities, I prefer the second method. The first method is easier if the query volume is small but the data needs to be added and updated frequently.
In addition, if the database supports it, you can also write rebuild_tree() and the space-freeing operation as trigger functions on the database side, and execute them automatically during insertion and update. This can achieve better operating efficiency, and you add SQL statements for new nodes will become simpler.

Implementation algorithm for parsing infinite classification of left and right values_PHP tutorial