data structure for traversal tree in PHP?
I don't have a background in CS or data structures. I want to make a PHP class that stores a modified preorder transversal tree, for manipulation and syncing with a database.
Basically I need to store data like:
+-------------+----------------------+-----+-----+
| category_id | name | lft | rgt |
+-------------+----------------------+-----+-----+
| 1 | ELECTRONICS | 1 | 20 |
| 2 | TELEVISIONS | 2 | 9 |
| 3 | TUBE | 3 | 4 |
| 4 | LCD | 5 | 6 |
| 5 | PLASMA | 7 | 8 |
| 6 | PORTABLE ELECTRONICS | 10 | 19 |
| 7 | MP3 PLAYERS | 11 | 14 |
| 8 | FLASH | 12 | 13 |
| 9 | CD PLAYERS | 15 | 16 |
| 10 | 2 WAY RADIOS | 17 | 18 |
+-------------+----------------------+-----+-----+
I was thinking of using an array, but it seems cumbersome. If it were an array of arrays like this: array( 'name'=> "PORTABLE ELECTRONICS", 'lft' => 10, 'rgt' = 19 ), then it would get cumbersome to loop through that array repeatedly to make sure all numbers are present, etc.
Since PHP has a few new data structures available, I wonder if any of these would get me any benefit over using an array?
- SplDoubly
- LinkedList
- SplStack
- SplQueue
- SplHeap
- SplMaxHeap
- SplMinHeap
- SplPriorityQueue
- SplFixedArray
- SplObjectStorage
Edit: This class isn't going to be a gateway to a tree stored in a database table. (If it were, I would just have a query of classes.) It's just a stand-alone mmpt in some kind of PHP data structure.
Answer
Edit: Ok, I looked into this a little more. I think there was a mix up in the nomenclature. You're not looking for a data structure for a transveral tree in PHP. You want to use a tree as a data structure in PHP, and you want to recover data from that tree using a method called the modified preorder tree traversal algorithm.
When working with a tree, we work from left to right, one layer at a time, descending to each node's children before assigning a right-hand number and moving on to the right. This approach is called the modified preorder tree traversal algorithm.
This is about storing hierarchical data in PHP vs MySQL. In PHP we can use a simple tree. The problem is that it is not easy to store a tree in the flat database that is MySQL. One option is to take the PHP and retrieve and adjacency list from it. This is essentially a list of each item and its parents. This way of doing things has some draw backs.
Another method is to extract information from the PHP tree that describes the nested sets that can be made out of the hierarchical data. To get this information from the PHP tree we need to use a modified preorder tree traversal algorithm. This is a method of running up and down the tree in order to extract certain information from it.
Whether we use the adjacency list model or the modified preorder tree traversal to retrieve the information, we use the exact same PHP Tree. The difference becomes how we retrieve the information from the tree and how we store the information in MySQL. The code for how to extract the information from MySQL is already on the page you quoted. To synch the data between PHP and MySQL you just have to use the MySQL techniques described on that page and a PHP tree class.
For this, I created a class in PHP that stores a tree. It uses a nodes. Each node can be thought of as the root of a complete tree, since from each node a complete subtree can be accessed. It was just easier to separate out the node from the tree, and it causes less overhead.
The important part of the class is the showAdjacency method. This runs the tree using a modified preorder tree traversal, and it displays the lft and rgt quantity for each name that enables you to store the data in MySQL as a Nested Set.
You can also display the tree, so you can visualize it. The deletion method is missing from this class. When you implement it, you have to pass the children of the deleted node to the parent of the node. Maybe I'll do that later.
I'll include the entire class at the bottom of the post, but here is how the data is retrieved for the modified preorder tree traversal:
// The modified preorder tree traversal.
private function showAdjacency($root, $spaces)
{
// Print the data first
if ($root)
{
// On the way down the tree, we get lft.
$left = ++$spaces;
foreach( $root->next as $child)
{
if ($child)
{
$spaces = $this->showAdjacency($child, $spaces);
}
}
}
// On the way back up, we get rgt.
$right = ++$spaces;
echo "$left - $right - $root->data <br/>";
return $spaces;
}
You can obviously store $root->data, $rgt, and $lft in an array that you use to synch with your database.
Here is the entire class. After the class I create a tree using the sample data from the page you linked to, and I output the lft and rgt values as well as the tree visualization.
You can run the code on Codepad
<?php
// Class defintions and methods:
// It's easier to use separate nodes. Each node still points to an entire and complete subtree.
class Node
{
public $data;
public $next = array();
}
// A first try at creating a tree with any number of branches from its nodes
// by Peter Ajtai - feel free to use and modify
class Tree
{
// The root
private $root;
public function __construct()
{
$this->root = NULL;
}
// The public wrapper.
// This is needed because we must start the recursive functions
// at the root, and we do not want to give public access to root.
// I am not familiar w overloading in PHP, maybe __set should be used for this
public function insertPub($data, $parent)
{
$root =& $this->root;
$this->insert($root, $data, $parent);
}
private function insert(&$root, $data, $parent)
{
// Create the root of the entire tree if no parent is passed in
if (!$root && !$parent)
{
$root = new Node;
$temp =& $root;
$temp->data = $data;
// Create space for next insertion
$temp->next[] = NULL;
} else if ($root->data == $parent)
{
// Add data as a child if we're at the parent, and we're done.
// Find the empty node to insert at
foreach($root->next as &$child)
{
// Insert at the first (and only) NULL
if (!$child)
{
$child = new Node;
$temp =& $child;
$temp->data = $data;
// Create space for next insertion
$temp->next[] = NULL;
}
}
// Create space for the next insertion
$root->next[] = NULL;
} else
{
// Keep searching for the parent as default behavior.
foreach($root->next as $child)
{
if ($child)
{
$this->insert($child, $data, $parent);
}
}
}
}
// Public wrapper for the display function.
public function showAdjPub()
{
echo "The neighbors:<br/><br/>";
$root =& $this->root;
$this->showAdjacency($root, 0);
echo "<br/>";
}
// The display function.
private function showAdjacency($root, $spaces)
{
// Print the data first
if ($root)
{
$left = ++$spaces;
foreach( $root->next as $child)
{
if ($child)
{
$spaces = $this->showAdjacency($child, $spaces);
}
}
}
$right = ++$spaces;
echo "$left - $right - $root->data <br/>";
return $spaces;
}
// Public wrapper for the display function.
public function showAllPub()
{
echo "The tree:<br/><br/>";
$root =& $this->root;
$this->showAll($root, 0);
echo "<br/>";
}
// The display function.
private function showAll($root, $spaces)
{
// Print the data first
if ($root)
{
for ($i=0; $i < $spaces; ++$i)
echo "---> ";
echo "$root->data <br/>";
++$spaces;
foreach( $root->next as $child)
{
if ($child)
{
$this->showAll($child, $spaces);
}
}
}
}
}
// Create a new instance of the tree
$myTree = new Tree;
// Insert the data into the tree.
// The following data would be retrieved using MySQL
$name = 'Electronics'; $parent = NULL;
$myTree->insertPub($name, $parent);
$name = 'Televisions'; $parent = 'Electronics';
$myTree->insertPub($name, $parent);
$name = 'Tube'; $parent = 'Televisions';
$myTree->insertPub($name, $parent);
$name = 'Lcd'; $parent = 'Televisions';
$myTree->insertPub($name, $parent);
$name = 'Plasma'; $parent = 'Televisions';
$myTree->insertPub($name, $parent);
$name = 'Portable Electronics'; $parent = 'Electronics';
$myTree->insertPub($name, $parent);
$name = 'MP3 Players'; $parent = 'Portable Electronics';
$myTree->insertPub($name, $parent);
$name = 'Flash'; $parent = 'MP3 Players';
$myTree->insertPub($name, $parent);
$name = 'CD Players'; $parent = 'Portable Electronics';
$myTree->insertPub($name, $parent);
$name = '2 Way Radios'; $parent = 'Portable Electronics';
$myTree->insertPub($name, $parent);
// Display adjacency
$myTree->showAdjPub();
// Show hierarchy
$myTree->showAllPub();
?>
PS: Storing the data in PHP in nested arrays like you suggested would be very difficult. In the class above, if a data member is deleted the tree is modified (including additions of entire subtrees, etc) the lft and rgt values will still be retrieved correctly.
If you use arrays to store the information you will have an extremely hard time deleting items that have both parents and children, and updating the lft and rgt valuse would be very hard. Finally adding large sets (subtrees) to the array would also be extremely difficult.
A tree is really the ideal way to store this sort of hierarchical data. It mimics our notions of sets. The problem is that while PHP stores trees easily MySQL doesn't, so we need to go through all the difficult work of the modified preorder tree traversal in order to extract information from the PHP tree so that we can store it in the MySQL db.