Storing hierarchical data in a database part 2b: Modified preorder tree traversal – insertions

Last time I introduced the Modified preorder tree traversal algorithm as a method to store relationships between nodes. This time I’ll show you how nodes are inserted into the tree. Note that I’m using MySQL, so you may need to change your queries slightly depending on the DB you’re using.

Before we get started, I’d like to share some links I’ve found since the last post.
Wikipedia: Tree traversal
MySQL AB: Managing Hierarchical Data in MySQL

Consider our tree, introduced last time:

Say you wanted to insert “Boxer” as a child node of Dog. The left/right values for this new node will be 14/15, respectively. Before we can insert, however, we need to make some room: all left/right values greater than 13 need to be incremented by two so we can fit [14]Boxer[15] in (Dog becomes [13]Dog[16] and Cat becomes [17]Cat[18] ).

$sql_lft="UPDATE animals SET lft=lft+2 WHERE lft>13";
$sql_right="UPDATE animals SET rght=rght+2 WHERE rght>13";
$sql_insert="INSERT INTO animals (`node_name`,`lft`,`rght`) VALUES ('Boxer',14,15)";

In order to insert a leaf node (at the same level), you simply use the rght value from a neighbor (or parent node’s lft value in some cases… you should be able to figure-out why).

The trickiest part really isn’t the insert as much as it is writing an algorithm that determines the proper lft/rght values at every point in the hierarchy. There are lots of ways to do it, so I’ll leave it up to your imagination. The best way to understand what’s going on is by trying it yourself. If you get stuck, feel free to ask!

Next time around I’m going to discuss the idea of moving (multiple) nodes within the tree, and a few other little pieces of functionality that should serve you well…

Join the Conversation

13 Comments

  1. Is it possible to retrieve a part of the tree, for example to level 2, instead of the whole tree?

    In your example this would be:
    + Animals
    + Fish
    + Mammals

  2. It’s definitely possible to retrieve part of a tree. Reference the sql from the previous part here. One method to do this is actually in your business-end code (PHP) by “clipping” the tree – only print (or only store in the array) nodes whose indentation are less than some number n. In the example you suggested, Animals would have an indentation level 0, and Fish and Mammals would have an indentation level 1, so on and so forth.

    if($tree[$ii]['indent']<2)
    {
    echo str_repeat(" ",$tree[$ii]['indent']).$tree[$ii]['NodeName']."<br />";
    }

    …is just one way to do this

  3. Hello! I need your help.
    Do you know how to do an algorith that can do a copy of a set of nodes?

  4. Your comment reminds me that the next installation of this series is long overdue!

    To answer your question, I hint at it in my comment above. It’s pretty similar. Rather than taking a temporary array of nodes you’re moving, you would take a copy of nodes, without their node ids (primary keys) and make their lft/rght values relative to a starting point zero, such that the top-most node lft value starts at 0. You then select the location where you want to copy to, shift the nodes after that point by the size of the set you’re inserting (i.e. your copy). Next insert the copy, adding the insertion point value to the lft and rght values of your copy.

  5. Cameron,

    Nice article. This method is really very good. Still I’m having this problem…

    Imagine I want to move a particular node around a tree, let’s say, from a level3 to level0 [the root]. How can I correctly update the tree nodes? I’m thinking that it will take 2 steps: first it would be like deleting it, and move all its right nodes to the left and then ‘pasting’ my node to its final position and moving all the node’s with higher left values to the right….

    I’m still not sure if this is the correct way… and how to affect the node’s ‘children’ if they exist…

    cheers,
    T.

    Still I can’t

  6. Further question according retrieving part of a tree:

    i wonder just if You store the indentation (or level or depth whatever You call it) in db as next column or is there any method/algorithm to retrieve this value while selecting records ?

  7. Hi, Did you ever create part 3 (or 2c?) I’m curious about your solution for moving nodes. If you could email me what you came up with that would be great. Thanks

  8. Hi,

    Here how can I reorder the data, like move up/down. E.g How can move ‘Dog’ node under ‘Fish’ node.

  9. I’m sorry I haven’t gotten around to creating the LONG overdue next part in this little series. Life got away from me for a while and I just plain forgot!

    See if my comment above make sense. In short, you want to make a copy of what you’re moving, then do a delete of the those nodes in the tree, which in-turn decrements all the lft/rght values to the RIGHT of the first deleted node. At that point, you can begin reconstructing the copied set of nodes one at a time into the tree.

  10. Moving nodes up or down is relative easy.
    I will paste my example on how to accomplish this task. this example is is part of my own script and will not fit the the tutorial above, but it should not be that hard to understand my method (i hope).

    /*
    Moves a node a step up.

    @ Return: Boolean

    */
    public function moveNodeUp( $id ){
    $moved = false;

    $target_node = $this->getNode($id);

    if(count($target_node))/* Valid node */{

    // Get previous sibling
    $prev_sibling = $this->getPrevSibling( $id );

    if(count($prev_sibling))/* Previous sibling exists, Node is able to move up */{

    // Get left and right values of the target node
    $target_lft = $target_node[‘lft’];
    $target_right = $target_node[‘rgt’];

    // Get left and right values of the previous sibling where the target node needs to be placed above
    $prev_lft = $prev_sibling[‘lft’];
    $prev_right = $prev_sibling[‘rgt’];

    // Total descendants within the target node
    $target_descendants = $this->descendants($target_lft, $target_right);

    // Total descendants within the previous sibling.
    $prev_descendants = $this->descendants($prev_lft, $prev_right);

    // get most max right value in database table
    $max_right = $this->getMaxRightValue( );

    // Calculate the target gap wich will appear when replacing the target node and all its descendants
    // To its tempoary spot
    $target_gap = ($target_descendants * 2) + 2;

    // Calculate the gap wich will appear when replacing the the previous sibling to the gap wich was
    // created when the target node was moved to its tempoary spot.
    $prev_gap = ($prev_descendants * 2) + 2;

    // Calculate the offset to add up to the target node and its descendants
    // when moving them to its tempoary spot at the end of the table
    $target_offset = ($max_right – $target_lft ) + 1;

    // Calculate the offset wich needs to be withdrawed from the target node and its descendants
    // when they are re-moved to its new position
    $prev_offset = $target_offset + $prev_gap;

    #– Mysql operations –#

    // Add up the “target offset” to the left and right values of the target node and its descendants
    // this way they will appear at the end of the database table above the tree.
    $this->runQuery(‘UPDATE ‘.$this->db_table.
    ‘ SET ‘.
    $this->dbf_rgt.’=’.$this->dbf_rgt.’+’.$target_offset.
    ‘,’.
    $this->dbf_lft.’=’.$this->dbf_lft.’+’.$target_offset.
    ‘ WHERE ‘.
    $this->dbf_lft.
    ‘ BETWEEN ‘.
    $target_lft.
    ‘ AND ‘.
    $target_right.
    ‘;’)or die(mysql_error());

    // Now fill up the gap that was created by moving the target node and its descendants
    // simply add up the target gap to the left and right values of the previous sibling and its descendants
    $this->runQuery(‘UPDATE ‘.$this->db_table.
    ‘ SET ‘.
    $this->dbf_rgt.’=’.$this->dbf_rgt.’+’.$target_gap.
    ‘,’.
    $this->dbf_lft.’=’.$this->dbf_lft.’+’.$target_gap.
    ‘ WHERE ‘.
    $this->dbf_lft.
    ‘ BETWEEN ‘.
    $prev_lft.
    ‘ AND ‘.
    $prev_right.

    ‘;’)or die(mysql_error());

    // And finaly withdraw the previous sibling offset from the left and right values of the target node and its descendants
    // to fill up the gap that was created by moving the previous sibling to the gap that was created when moving the
    // target node and its descendants to its tempoary spot
    $this->runQuery(‘UPDATE ‘.$this->db_table.
    ‘ SET ‘.
    $this->dbf_rgt.’=’.$this->dbf_rgt.’-‘.$prev_offset.
    ‘,’.
    $this->dbf_lft.’=’.$this->dbf_lft.’-‘.$prev_offset.
    ‘ WHERE ‘.
    $this->dbf_rgt.
    ‘ > ‘.
    $max_right.
    ‘;’)or die(mysql_error());

    #– Target node has been moved up –#
    $moved = true;
    }
    }
    return $moved;
    }

    /*
    Moves a node a step down

    @ Return: Boolean

    */
    public function moveNodeDown( $id ){
    $moved = false;
    $next_sibling = $this->getNextSibling( $id );// get next sibling
    if(count($next_sibling)){
    $moved = $this->moveNodeUp( $next_sibling[‘id’] ); // simply move the next sibling a spot up
    }
    return $moved;
    }

Leave a comment

Hey there! Come check out all-new content at my new mistercameron.com!