SitePoint Sponsor

User Tag List

Page 3 of 6 FirstFirst 123456 LastLast
Results 51 to 75 of 141
  1. #51
    SitePoint Member
    Join Date
    Jul 2005
    Posts
    13
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    OK, I was monkeying around some more, and it's relatively painless to move a node as well. I think. This is hardly an optimal test database - it has a whopping twenty entries - but enough to get the idea.

    function move_node($parent, $title) {
    // This is the whack-a-mole method of moving a node (I was too lazy to calculate exactly
    // what would be involved in a manual move). So here's what I do - get the right value
    // of the new parent node. Set the parent of the moved node as appropriate. Rebuild the
    // database for the current node, then rebuild the entire database. As I say, ugly as sin.
    // BUT IT WORKS!!

    // First, we get the parent's right value
    $result = mysql_query('SELECT rgt FROM tree WHERE title="'.$parent.'";');
    $row = mysql_fetch_array($result);
    $newLeft = $row['rgt'];

    // Maybe we should take the root of the entire tree, and rebuild from that? Easy, but time-consuming.
    $result = mysql_query('SELECT title FROM tree ORDER BY lft ASC LIMIT 1;');
    $row = mysql_fetch_array($result);
    $rootLevel=$row['title'];

    // Next, we set the node's new parent.
    $result = mysql_query('UPDATE tree set parent="'.$parent.'" WHERE title="'.$title.'";');

    // Rebuild the tree from this node down, based on a new left value.
    rebuild_tree($title, $newLeft);

    // Rebuild the entire DB, because you just clobbered the hell out of it!
    rebuild_tree($rootLevel, 1);
    }

    ... The real disadvantage to this approach is the double-rebuild of the database. I probably don't have to do it, but I figure better safe than sorry. Please do post a quicker or more efficient way of moving nodes, if anybody has one...

  2. #52
    Jerry
    SitePoint Community Guest
    This is good if you have 1 Tree per table.
    Im wondering, how do you solve the issue if you have multiple trees with different roots?

    i mean, for instance drive MyComputer.
    ID,Name,ParentID
    1, DriveC, 0
    2, DriveD, 0
    3, DriveE, 0
    4, Documents,2
    5, Winnt, 2
    6, Downloads, 2

    I was having a hardtime applying this concept. this can easily be solve by creating a super root, and all multiple trees point to this. but still the problem is, how to solve the multiple tree problem? help

  3. #53
    Chris
    SitePoint Community Guest
    This is a great article and one major positive I see for the Modified Preorder Tree Traversal method is the inbuilt ordering of elements within the same level on the tree.

  4. #54
    SitePoint Member
    Join Date
    Jul 2005
    Posts
    13
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Jerry - they aren't multiple trees, and you aren't adding a super-root: you're looking at each physical drive as a tree in and of itself, while Micro$oft, for example, looks at 'My Computer' as the root node, each drive as a child node, and so on. A cubicle jockey might decide that the cubicle cluster should be the root, and each computer a child, and each drive a child of that. A corporate IT guy might look at the entire company's network as a root node, and each cubicle cluster as a child, and so on. Ad nauseam.

    And falieson, as I said in your thread in the forums, simply rebuilding the tables resolved that -- problem.

    On to more fun - I have built a delete_node() function. Basically, it reverses the add_node() - it removes the node and all descendants, then decrements all nodes with a greater lft and rgt value as appropriate. Here's the code for THAT:

    function delete_node($title) {
    // This will delete a node AND ALL DESCENDANT NODES! If this isn't what you want,
    // consider moving all sub-nodes out first. Alternatively, I can rewrite this to
    // remove only the node, and change the nlevel of all child nodes to point to the
    // deleted node's parent. However, this strikes me as slightly counter-intuitive.
    //
    // Logically, I think that the process will be similar to that of adding a node, only
    // in reverse. First, we'll need to get the left and right value of the node to be
    // removed. When we have this, we'll run a delete to remove any node whose left and
    // right fall between these values (inclusive, to remove the node itself). Then, we
    // need to decrement all left and right node values by the difference between the
    // deleted node's right and left values, plus one.

    // First, get the right/left from the selected node.
    $result = mysql_query('SELECT rgt, lft from tree WHERE title="'.$title.'";');
    $row = mysql_fetch_array($result);
    $leftVal = $row['lft'];
    $rightVal = $row['rgt'];
    $decrementBy = $rightVal - $leftVal + 1;

    // Now, we have the range of nodes to be deleted.
    $result = mysql_query('DELETE FROM tree WHERE lft BETWEEN '.$leftVal.' AND '.$rightVal.';');

    // If this is right, we should decrement all remaining nodes with a left and/or right
    // greater than the deleted node's right value by our $decrementBy value. I think.
    $result2 = mysql_QUERY('UPDATE tree SET rgt=rgt-'.$decrementBy.' WHERE rgt>'.$rightVal.';');
    $result3 = mysql_QUERY('UPDATE tree SET lft=lft-'.$decrementBy.' WHERE lft>'.$rightVal.';');

    // And that should do it.
    }

  5. #55
    Jerry
    SitePoint Community Guest
    thanx.
    i was about to implement this idea but
    the difficult part was populating the values of left and right numbers.
    i realize that i have multiple trees.

    how to populate the left and right values when using different trees?

    the only solution i see now is to add a supernode(my computer being top most root or other reserves superroots. hehe) the so that i can populate the left and right values.

    i'll be implementing this soon as soon as i clean up the database.

  6. #56
    SitePoint Wizard REMIYA's Avatar
    Join Date
    May 2005
    Posts
    1,351
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Is there really a need of left and right value?
    Why do we need the left and right?
    Isn't just the parent sufficient?

  7. #57
    SitePoint Member
    Join Date
    Jul 2005
    Posts
    13
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    The point of the left and right is kind of obscure, REMIYA, but it is practical. Typically, when querying a database for a given node and it's descendants, you get the parent, then all nodes that point to that parent, then, for each child, you get all the nodes that point to that child, and so on, and so on... But with the left-right values, asking for any left/right values between a given node will return ALL of its descendants. And ordering them by left value will put them into a recognizable tree. If you want to know more, I'm actually building a PHP5 class to do all this for you. The end user should NEVER see the left and right value, it's purely an internal data representation tool.

    Just email or IM if you have questions about this - I'm really enjoying this!

  8. #58
    SitePoint Member
    Join Date
    Jul 2005
    Posts
    13
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    It's a tricky thing, jerry - I'm actually using the tree as a table in my DB, then referencing other tables to contain the data for each tree row. Somehow, I'm thinking this'd be easier in XML. But hey! This way's SO much more fun!

  9. #59
    SitePoint Member
    Join Date
    Jul 2005
    Posts
    13
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Sorry, I wasn't very clear on that last comment - there are two separate tree structures in my DB, and some of the rows in each tree are tangentially connected to others. It's a pain.

  10. #60
    SitePoint Wizard REMIYA's Avatar
    Join Date
    May 2005
    Posts
    1,351
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    I am asking because RDLDB [doc] is hierarchy-related. And I have never felt the need of having right or left and still have never been wondering which child comes first. The first in is the first out (The first child is first, the second is second, the third is third, etc).
    That is why I was wondering why would anyone use right and left. And why would anyone need so many computations.

  11. #61
    SitePoint Member
    Join Date
    Jul 2005
    Posts
    13
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    In the quick view I took of RDLDB, you probably wouldn't need right and left values. There are places where it's appropriate, this may or may not be one.
    The point of this whole exercise seems to have been a hypothetical romp down alternative lane. Rather than recursing your way down a tree structure to access subnodes, you can retrieve all subnodes at a single call via this modified tree recursion trick. That's all it is - a trick.
    There are calculations, and a number of hoops to be jumped through - the relative value is yet do be determined, by my research. I do see that there is an advantage to this - if nothing else, it changed the way I view tree structures. If you don't need the ability to move nodes, don't care about time spent in recursion calling a DB yet again for a node's children, then this is totally irrelevant.
    Just my 0.02

  12. #62
    delfeld
    SitePoint Community Guest
    The adjacency list has some problems when data is duplicated when using names in place of id values. For example, the items:

    fruit-green-apple-green

    and

    fruit-ripe-apple-green

    may not produce expected results. This problem does not exist if row id's are used instead of names.

    Here is a comparison between retrievals on the two methods:

    retrieve descendents:
    left-right: SELECT title FROM tree WHERE lft > {left value} AND rgt < {right value}
    adjacency list: SELECT title FROM tree WHERE ancestorId > {current id} AND ancestorId < ???

    retrieve ancestors:
    left-right: SELECT title FROM tree WHERE lft < {left value} AND rgt > {right value}
    adjacency list: SELECT title FROM tree WHERE ancestorId < {current id} AND ancestorId > ???

    The value in the left-right list is that there is not only a starting point - as in ascendency lists - but there is also a stopping point.

    I don't see how - in a simple search without joins - an adjacency list can find any relatives (outside of one level up or down) without multiple searches. It doesn't *matter* if there is no use for the left-right structure beyond speeding up the search, since that is the whole goal. To use a hierarchical adjacency list may be better for insertions and human data reading, but it is not better for the most common website function - searching for data.

    There is a disadvantage if there are more than a few updates. I do not think this could be used, for example, for storing chat-room messages.

    Even still, the left-right can be improved by using the idea of pointers instead of actual numbers. That way, there would be no need for actual numbers to be updated. I am not quite sure if there is anything like this in MySQL.

    Or else another table column could be used during insertions. The table would store all insertions along with their insertion row until a certain time, and then do all insertions at once. Still not dynamic, though.

  13. #63
    SitePoint Addict timvw's Avatar
    Join Date
    Jan 2005
    Location
    Belgium
    Posts
    354
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Btw, one could also have a look at pear's nested set class...

  14. #64
    celk-no!
    SitePoint Community Guest
    Your diagram with the arrows is much more understandable than JC's "worm and tree" metaphor!

  15. #65
    Digvijoy Mohapatra
    SitePoint Community Guest
    This is what i looking for thanks.

  16. #66
    Ivan Nemeth
    SitePoint Community Guest
    I've used for storing trees the adjacency list method, but after your article I will use the tree traversal method. I really like it, thanks!

  17. #67
    Scotty
    SitePoint Community Guest
    Without reading any tutorials I came up with the adjancey method of storing trees. After reading this I'm going to have to change my method. Excellent tutorial even though it's made my head hurt!

    Will have to play with it a bit!

    Cheers

  18. #68
    Jerod
    SitePoint Community Guest
    Great article! Also, for those who want it, I needed to store the tree and keep everything alphabetized (I was storing category names in a hierarchy). To do so, I used the following (assume a POSTed form with a 'Parent' and 'New Category' field):

    //get the id of the parent to which we're going to add a child
    $parent = $_POST['parent'];
    $new = $_POST['new'];

    //this'll work on a where by ID eventually...
    $sql = "SELECT id, lft FROM categories WHERE name = '$parent'";
    echo "SQL: " . $sql . "<br>";
    $result = mysql_query($sql) or die(mysql_error());
    $row = mysql_fetch_assoc($result) or die(mysql_error());

    //get the left value of the parent to which we need to add a child
    $oldleft = $row['lft'];
    //and the id of the parent node
    $parentid = $row['id'];

    //before any updates occur, get the left value we're going to
    //use for the new node.
    $sql = " SELECT MIN(lft) as newleft FROM categories "
    ." WHERE (lft>$oldleft AND name > '$new' AND parent = $parentid)"
    ." OR (lft>$oldleft AND parent != $parentid)";
    $result = mysql_query($sql) or die(mysql_error());
    $row = mysql_fetch_assoc($result) or die(mysql_error());

    //our new node's left value
    $newleft = $row['newleft'];

    //move all the existing nodes (right and left) that fall
    //after this guy up by 2. The comparisons for name and parentid
    //are needed to alphabetize everything, otherwise we could
    //just do the update where rgt>$oldleft and be done.
    $sql = " UPDATE categories SET rgt=rgt+2 "
    ." WHERE "
    ." (rgt>$oldleft AND name > '$new' AND parent = $parentid) "
    ." OR "
    ." (rgt>$oldleft AND parent != $parentid)";
    echo "SQL: " . $sql . "<br>";
    $result = mysql_query($sql) or die(mysql_error());

    $sql = " UPDATE categories SET lft=lft+2 "
    ." WHERE "
    ." (lft>$oldleft AND name > '$new' AND parent = $parentid) "
    ." OR "
    ." (lft>$oldleft AND parent != $parentid)";
    echo "SQL: " . $sql . "<br>";
    $result = mysql_query($sql) or die(mysql_error());

    //go ahead and put the new node in place
    $sql = " INSERT categories(name,lft,rgt,parent) "
    ." VALUES ('" . $new . "'," . ($newleft) . "," . ($newleft+1) . ",$parentid)";
    echo "SQL: " . $sql . "<br>";
    $result = mysql_query($sql) or die(mysql_error());

    You'll notice the updates changed slightly, and we had to find for ourselves the left and right values of the new child node. Please note, I have done about 5 minutes of testing -- if there are any bugs, feel free to post back...

  19. #69
    jerry
    SitePoint Community Guest
    [img]
    http://i2.sitepoint.com/graphics/sitepoint_numbering.gif
    [/img]

    simple question really...
    How do i query only fruit and meat.

    I just need to get the child of a certain tree. not the entire tree.

    The only way i see was to include the parentID on the columns.
    then again, i just want to query n'th decendants.

    like from the picture, i want to query up to 2nd generation of food, which should not include cherry and banana.

    any help is appriciated.

    *im back again. stumping...

  20. #70
    brian
    SitePoint Community Guest
    This article explains (in MySql, but i'm sure the logic for other dbs would be similar) how to do a number of things with the lft rgt system: http://dev.mysql.com/tech-resources/articles/hierarchical-data.html

  21. #71
    kL
    SitePoint Community Guest
    You may get only every second level by requiring lft to be even or odd, but that's it.

    To get children only or do other depth-related queries you'll need to maintain another column with depth.

  22. #72
    Bernd-vdb
    SitePoint Community Guest
    What I did is implement the adjacency list method as a DB function. This way you still have its advantages (elegant design and code, only one update/insert) without the performance penalty: You need only one DB-query for any (sub-)tree - and it is the query overhead that sucks CPU cycles, not the function.
    PostgreSQL was capable of recursive functions, not MySQL. This may have changed with the latest 5.x version, but I have not (yet) seen any examples online.
    However, I don't see why anyone should stay away from Postgres once he has digged into DBs that far.

  23. #73
    kH
    SitePoint Community Guest
    Very nice article. It was a good read. I found this PHP tree class that has add and delete features and it is pretty interesting. There is no documentation so you might have to dig into the code to find out how to use it.

    http://www.husainshabbir.com/2005/11/10/modified-preorder-tree-traversal-php-code/

  24. #74
    PRASHPSG
    SitePoint Community Guest
    another possible schema for tree database is like this

    tree_table(id, parent, leaf, depth)

    The depth attribute is very handy for getting data.

  25. #75
    M A J Jeyaseelan
    SitePoint Community Guest
    We have developed a method for handling unlimited hierarchies without the use of primary keys but using the RDBMS backend. The response time is faster than any conventional datbase architecture would involve


Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •