注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

php开发lamp

《西安--木木》-经历丰富了生活。 架构师QQ群: 246695517

 
 
 

日志

 
 

Modified Preorder Tree Traversal  

2014-04-01 11:08:52|  分类: 算法 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

Modified Preorder Tree Traversal

Now, let’s have a look at another method for storing trees. Recursion can be slow, so we would rather not use a recursive function. We’d also like to minimize the number of database queries. Preferably, we’d have just one query for each activity.

We’ll start by laying out our tree in a horizontal way. Start at the root node (‘Food’), and write a 1 to its left. Follow the tree to ‘Fruit’ and write a 2 next to it. In this way, you walk (traverse) along the edges of the tree while writing a number on the left and right side of each node. The last number is written at the right side of the ‘Food’ node. In this image, you can see the whole numbered tree, and a few arrows to indicate the numbering order.

1105_numbering

We’ll call these numbers left and right (e.g. the left value of ‘Food’ is 1, the right value is 18). As you can see, these numbers indicate the relationship between each node. Because ‘Red’ has the numbers 3 and 6, it is a descendant of the 1-18 ‘Food’ node. In the same way, we can say that all nodes with left values greater than 2 and right values less than 11, are descendants of 2-11 ‘Fruit’. The tree structure is now stored in the left and right values. This method of walking around the tree and counting nodes is called the ‘modified preorder tree traversal’ algorithm.

Before we continue, let’s see how these values look in our table:

1105_table2

Note that the words ‘left’ and ‘right’ have a special meaning in SQL. Therefore, we’ll have to use ‘lft’ and ‘rgt’ to identify the columns. Also note that we don’t really need the ‘parent’ column anymore. We now have the lft and rgt values to store the tree structure.

Retrieve the Tree

If you want to display the tree using a table with left and right values, you’ll first have to identify the nodes that you want to retrieve. For example, if you want the ‘Fruit’ subtree, you’ll have to select only the nodes with a left value between 2 and 11. In SQL, that would be:

SELECT * FROM tree WHERE lft BETWEEN 2 AND 11;

That returns:

1105_table3

Well, there it is: a whole tree in one query. To display this tree like we did our recursive function, we’ll have to add an ORDER BY clause to this query. 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.

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

The only problem left is the indentation.

To show the tree structure, children should be indented slightly more than their parent. We can do this by keeping a stack of right values. Each time you start with the children of a node, you add the right value of that node to the stack. You know that 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, you can see if you’re still displaying the children of that parent. When you’re finished displaying a node, you remove its right value from the stack. If you count the elements in the stack, you’ll get the level of the current node.

<?php  
function display_tree($root) {  
   // retrieve the left and right value of the $root node  
   $result = mysql_query('SELECT lft, rgt FROM tree '.  
                          'WHERE title="'.$root.'";');  
   $row = mysql_fetch_array($result);  
 
   // start with an empty $right stack  
   $right = array();  
 
   // now, retrieve all descendants of the $root node  
   $result = mysql_query('SELECT title, lft, rgt FROM tree '.  
                          'WHERE lft BETWEEN '.$row['lft'].' AND '.  
                          $row['rgt'].' ORDER BY lft ASC;');  
 
   // display each row  
   while ($row = mysql_fetch_array($result)) {  
       // only check stack if there is one  
       if (count($right)>0) {  
           // check if we should remove a node from the stack  
           while ($right[count($right)-1]<$row['rgt']) {  
               array_pop($right);  
           }  
       }  
 
       // display indented node title  
       echo str_repeat('  ',count($right)).$row['title']."n";  
 
       // add this node to the stack  
       $right[] = $row['rgt'];  
   }  
}  
?>

If you run this code, you’ll get exactly the same tree as with the recursive function discussed above. Our new function will probably be faster: it isn’t recursive and it only uses two queries.

The Path to a Node

With this new algorithm, we’ll also have to find a new way to get the path to a specific node. To get this path, we’ll need a list of all ancestors of that node.

With our new table structure, that really isn’t much work. When you look at, for example, the 4-5 ‘Cherry’ node, you’ll see that the left values of all ancestors are less than 4, while all right values are greater than 5. To get all ancestors, we can use this query:

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

Note that, just like in our previous query, we have to use an ORDER BY clause to sort the nodes. This query will return:

+-------+
| title |
+-------+
| Food |
| Fruit |
| Red |
+-------+

We now only have to join the rows to get the path to ‘Cherry’.

How Many Descendants

If you give me the left and right values of a node, I can tell you how many descendants it has by using a little math.

As each descendant increments the right value of the node with 2, the number of descendants can be calculated with:

descendants = (right ??“ left - 1) / 2



Automating the Tree Traversal

Now that you’ve seen some of the handy things you can do with this table, it’s time to learn how we can automate the creation of this table. While it’s a nice exercise the first time and with a small tree, we really need a script that does all this counting and tree walking for us.

Let’s write a script that converts an adjacency list to a modified preorder tree traversal table.

<?php  
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 title FROM tree '.  
                          'WHERE parent="'.$parent.'";');  
   while ($row = mysql_fetch_array($result)) {  
       // recursive execution of this function for each  
       // child of this node  
       // $right is the current right value, which is  
       // incremented by the rebuild_tree function  
       $right = rebuild_tree($row['title'], $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 title="'.$parent.'";');  
 
   // return the right value of this node + 1  
   return $right+1;  
}  
?>

This is a recursive function. You should start it with rebuild_tree('Food',1); The function then retrieves all children of the ‘Food’ node.

If there are no children, it sets its left and right values. The left value is given, 1, and the right value is the left value plus one. If there are children, this function is repeated and the last right value is returned. That value is then used as the right value of the ‘Food’ node.

The recursion makes this a fairly complex function to understand. However, this function achieves the same result we did by hand at the beginning of this section. It walks around the tree, adding one for each node it sees. After you’ve run this function, you’ll see that the left and right values are still the same (a quick check: the right value of the root node should be twice the number of nodes).

Adding a Node

How do we add a node to the tree? There are two approaches: you can keep the parent column in your table and just rerun the rebuild_tree() function — a simple but not that elegant function; or you can update the left and right values of all nodes at the right side of the new node.

The first option is simple. You use the adjacency list method for updating, and the modified preorder tree traversal algorithm for retrieval. If you want to add a new node, you just add it to the table and set the parent column. Then, you simply rerun the rebuild_tree() function. This is easy, but not very efficient with large trees.

The second way to add, and delete nodes is to update the left and right values of all nodes to the right of the new node. Let’s have a look at an example. We want to add a new type of fruit, a ‘Strawberry’, as the last node and a child of ‘Red’. First, we’ll have to make some space. The right value of ‘Red’ should be changed from 6 to 8, the 7-10 ‘Yellow’ node should be changed to 9-12 etc. Updating the ‘Red’ node means that we’ll have to add 2 to all left and right values greater than 5.

We’ll use the query:

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

Now we can add a new node ‘Strawberry’ to fill the new space. This node has left 6 and right 7.

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

If we run our display_tree() function, we’ll see that our new ‘Strawberry’ node has been successfully inserted into the tree:

Food  
 Fruit  
   Red  
     Cherry  
     Strawberry  
   Yellow  
     Banana  
 Meat  
   Beef  
   Pork

Disadvantages

At first, the modified preorder tree traversal algorithm seems difficult to understand. It certainly is less simple than the adjacency list method. However, once you’re used to the left and right properties, it becomes clear that you can do almost everything with this technique that you could do with the adjacency list method, and that the modified preorder tree traversal algorithm is much faster. Updating the tree takes more queries, which is slower, but retrieving the nodes is achieved with only one query.

Conclusion

You’re now familiar with both ways to store trees in a database. While I have a slight preference for the modified preorder tree traversal, in your particular situation the adjacency list method might be better. I’ll leave that to your own judgement.

One last note: as I’ve already said I don’t recommend that you use the title of a node to refer to that node. You really should follow the basic rules of database normalization. I didn’t use numerical ids because that would make the examples less readable.

Further Reading

More on Trees in SQL by database wizard Joe Celko:
http://searchdatabase.techtarget.com/tip/1,289483,sid13_gci537290,00.html

Two other ways to handle hierarchical data:
http://www.evolt.org/article/Four_ways_to_work_with_hierarchical_data/17/4047/index.html

Xindice, the ‘native XML database’:
http://xml.apache.org/xindice/

An explanation of recursion:
http://www.strath.ac.uk/IT/Docs/Ccourse/subsection3_9_5.html

If you enjoyed reading this post, you’ll love Learnable; the place to learn fresh skills and techniques from the masters. Members get instant access to all of SitePoint’s ebooks and interactive online courses, like PHP & MySQL Web Development for Beginners.



  评论这张
 
阅读(672)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017