creating tree traversal hierarchy from scratch using PHP/MySQL

Question

I am currently developing a category hierarchy, and I got the point of creating tree treversal i think. But I need to add a new node into this hierarchy usign PHP function.

The problem is rebuild_tree function would be good enough (in other words, efficient with large trees).

Sample query:

 CREATE TABLE `t_categories`(
   `id` INTEGER UNSIGNED NOT NULL AUTO_INCREMENT,
   `title` VARCHAR(45) NOT NULL,
   `lft` INTEGER UNSIGNED NOT NULL,
   `rght` INTEGER UNSIGNED NOT NULL,
   PRIMARY KEY (`id`)
 );

 INSERT INTO t_categories (title, lft, rght) VALUES ('Cat 1',1,16);
 INSERT INTO t_categories (title, lft, rght) VALUES ('Cat 2',2,3);
 INSERT INTO t_categories (title, lft, rght) VALUES ('Cat 3',4,7);
 INSERT INTO t_categories (title, lft, rght) VALUES ('Cat 4',5,6);
 INSERT INTO t_categories (title, lft, rght) VALUES ('Cat 5',8,13);
 INSERT INTO t_categories (title, lft, rght) VALUES ('Cat 6',9,12);
 INSERT INTO t_categories (title, lft, rght) VALUES ('Cat 7',10,11);
 INSERT INTO t_categories (title, lft, rght) VALUES ('Cat 8',14,15);

Table results look like that:

 ID    TITLE   LFT    RGHT
 1     Cat1    1      16
 2     Cat2    2      3
 3     Cat3    4      7
 4     Cat4    5      6
 5     Cat5    8      13
 6     Cat6    9      12
 7     Cat7    10     11
 8     Cat8    14     15

I gave sample data above, but I need to create completely new node from scratch as well.

So, how can I add a new node into this tree using PHP function that efficients with large trees?

if you're looking for an efficient way of managing large trees then you'd better switch from nested sets to adjacency list - explainextended.com/2009/09/24/… — Jon Black
– Jon Black, Commented Mar 8, 2011 at 12:11
@foo: good point but at least 90 can close the case and choose an answer. — Cybercartel
– Cybercartel, Commented Mar 16, 2011 at 20:04

Cybercartel · Accepted Answer · 2011-03-07 18:31:54Z

2

This is a celko tree. Simpelst approach would be depth-first traversal of the tree and update only the left value and then in a recursive manner the right value. Insertition is much more costly.

answered Mar 7, 2011 at 18:31

Cybercartel

12.6k7 gold badges39 silver badges73 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Jonas Bötel Over a year ago

Here is how celko does insertions: ibase.ru/devinfo/DBMSTrees/sqltrees.html

umlcat · Accepted Answer · 2011-03-07 18:34:08Z

2

I recommend that you add a "parent id" field to your table structure instead of the "left" and "right" fields. If its important to you have an order for the children items, use also a "localorder" int field.

With the current structure, each time you want to add an item, you have to check if there is a previous item, for the first item, and to check if there is a final item, for a last item.

CREATE TABLE `t_categories`(
   `keyid` INTEGER UNSIGNED NOT NULL,
   `title` VARCHAR(45) NOT NULL,
   `parentid` INTEGER UNSIGNED NOT NULL,
   `sortorder` INTEGER UNSIGNED NOT NULL,
   PRIMARY KEY (`id`)
 );

-- root item, no parent
 INSERT INTO t_categories (keyid, title, parentid, sortorder) VALUES (1, 'Root', 0, 0);

-- first level
 INSERT INTO t_categories (keyid, title, parentid, sortorder) VALUES (2, 'a:', 1, 1);
 INSERT INTO t_categories (keyid, title, parentid, sortorder) VALUES (3, 'b:', 1, 2);
 INSERT INTO t_categories (keyid, title, parentid, sortorder) VALUES (3, 'c:', 1, 3);
 INSERT INTO t_categories (keyid, title, parentid, sortorder) VALUES (4, 'd:', 1, 4);

-- second level

 INSERT INTO t_categories (keyid, title, parentid, sortorder) VALUES (5, 'a:\temp', 2, 1);
 INSERT INTO t_categories (keyid, title, parentid, sortorder) VALUES (6, 'a:\docs'', 2, 2);
 INSERT INTO t_categories (keyid, title, parentid, sortorder) VALUES (7, 'a:\music', 2, 3);

 INSERT INTO t_categories (keyid, title, parentid, sortorder) VALUES (8, 'c:\temp', 4, 1);
 INSERT INTO t_categories (keyid, title, parentid, sortorder) VALUES (9, 'c:\docs'', 4, 2);
 INSERT INTO t_categories (keyid, title, parentid, sortorder) VALUES (10, 'c:\music', 4, 3);

-- and so on

answered Mar 7, 2011 at 18:34

umlcat

4,1513 gold badges22 silver badges31 bronze badges

3 Comments

kuzey beytar Over a year ago

thank you for your answer, but this method you mentioned is not one I want -it's not better and faster for me

umlcat Over a year ago

how do you want to iterate over the tree, once is already stored in the table ?

umlcat Over a year ago

to check how to iterate over the tree check muy other answer, later in this same post

Cybercartel · Accepted Answer · 2011-03-08 09:52:20Z

0

The same tree is used by the huffman compresssion to count the occurrence of a letter in the given document. I think to encode a string the algorithm then use also a depth-first traversal so that the letter with the most occurrence is encoded with the least bits possible. I don't know if it is useful here but the lowest entropy of a text is found using shannon theorm -log(x)+log(2) where x is the letter and log(2) is the base in bits it is always 2.

edited Mar 8, 2011 at 9:52

answered Mar 7, 2011 at 20:23

Cybercartel

12.6k7 gold badges39 silver badges73 bronze badges

Comments

umlcat · Accepted Answer · 2011-03-08 16:19:48Z

My previous answer is incomplete. It's a summary, the whole code is to long to be in a forum post. Forgot to ask, procedural PHP, or Object Oriented PHP ?

MySQL: CREATE TABLE t_categories( keyid INTEGER UNSIGNED NOT NULL, title VARCHAR(45) NOT NULL, parentid INTEGER UNSIGNED NOT NULL, sortorder INTEGER UNSIGNED NOT NULL, PRIMARY KEY (id) );

PHP function headers:

// globar var, acts like a type /* typedef */ treeNodeType = array( "keyid" => 0, "title" => "", "parentid" => 0, "sortorder" => 0, )

// globar var, acts like a type /* typedef */ treeType = array( "root" => nil, "whatever" => "", )

/* treeNodeType / function insertNode(/ treeType / ATree, AParentId, ATitle) { ... } / void / function deleteNode(/ treeType */ ATree, AKeyId) { ... }

// --> MAIN main();

/* void */ function main() { // treeType myTree; myTree = treeType;

// insert root = 0 rootNode = insertNode(myTree, 0, '[PC]');

... }

Collectives™ on Stack Overflow

creating tree traversal hierarchy from scratch using PHP/MySQL

4 Answers 4

1 Comment

3 Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

1 Comment

3 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related