Modified Preorder Tree Traversal is one of the methods, how to save tree structure of dates in relational databases. Methods, how to save tree structure is of course plenty, but not all are so efficient. We can use for example various recursive methods, which are mostly in the bigger size of trees very slow because of for gaining of the whole tree will be needed minimally as many SQL queries as many levels of branches is. Next chance is use container, which is faster then recursion, but also in the bigger size of tree we will rain down many SQL queries on database.

Method, by which we can use only one or two SQL queries for whatever operation is called modifying preorder tree traversal.

Basic principle of the whole algorithm is very simple. Duty is rate all of the embranchment of trees with ordinal numbers, accord which we walk through the whole tree. For better imagination of rating see this picture:

Ordinal numbers, which we rate the tree begin from lowest number and with each other embranchment this number grows up by value one. The whole tree we walk through from left to right and by this we are gaining his whole structure.

Home (1, 16) -> First (2, 7) -> Thrid (3, 4) -> Fourth(5, 6) -> First(3, 7) -> Second(8, 12) -> Fifth(9, 14) -> Sixth (10, 11) -> Seventh(12, 13) -> Fifth(9, 14) -> Second(8, 12) -> Home(1, 16)

Each embranchment has now two indexes – right one and left one. By rating of embranchment with this method creates effects to us, which will be for our work very important. Embranchment, in which are subembranchments has always lower left index than all of these subembranchments and his right index is bigger than all of his subembranchments. Evidently is it from base of the whole tree, which has the lowest left index and the biggest right index in the whole tree.

Advantage is in it, that it isn’t problem for us gain whatever of this subtrees ordered exactly accord that, how we have them saved in databases, only with one SQL query.

For programming I choose PHP 5 and MySQL version 4.1

Table in database

Before self saving of dates we can create table in database. All, what we need in this table is name of item, right index, left index and moreover we will be saving size of nested item in tree. Eventually we can save prefix for language mutation (in the whole code we will suppose, that prefix of language mutation is saved in array SESSION). Structure of table can then looks for example like this:

Modified Preorder
Tree Traversal class

If we have created table yet, we can create class for servicing of the whole algorithm now. By traversing is service of dates in database little complicated, than it is by other algorithms, but access to these elements (single embranchments) is more efficient.

Problem with editing is exactly in it, with each change it musts be renumbered indexes of embranchments, because of not creating of collisions in tree to us.

All class will be consists of methods, that will serviced traversing. As first we will defined constructor, which includes one parameter – table of table. In this table is our created structure.

For connection to database we will use extends class connect, which we will extends into our class thanks to connects methods.

First we make method, which inserts basic element of tree – base – into table. Base must have, on the supposition that in our tree are no embranchments, indexes 1 and 2. By that we set our index parent to value 0, from which we will starting.

For check, if method can be called, we can use function, which will check, if our table is empty, or doesn’t contain embranchments with this language mutation.

Embranchments adding

One of most important methods in the whole class will be embranchments adding. Important is think about it, that in the each embranchment adding we must renumber all embranchments, which will be after added embranchment. These are all, that have bigger left index than item index, in which we are adding, against value i + 1.

By embranchment saving we have possibility choose, over which item will be new item inserted. For simplicity will class enable only insert item, which will be nesting in our item. We can choose, whether we want its insert to begin or to end thought.

I interpret as yet once on the picture. See picture, which is at the beginning this article. We want insert next embranchment after “First” embranchment. Class enable us insert embranchment from “Thrid”(on beginning) or after “Fourth” (in the end), with it, that inserted item have same nesting index as “Thrid” or “Fourth”.

Function addTree will have three input arguments: new item name, left index, after which we will insert and position, where we inserting ( on beginning or in the end).

Method addTree use first method setup_position, that is here only by reason of decent input argument for position. This argument value is or number (0 – begin, 1 – end) or char (H – begin, E –end).

Next is use method select_parent( $left, 1 ) here, that get nesting value item, after that we will insert:

Optional argument is $info, If is this parametr on (value 1), this method will saved value of right index ad ID value, to next work.

Now we can insert item. For our insert we must create two methods. One for insert item on begin and second for insert item in the end. Both methods are similar, and isn’t problem merge it’s to a one, but to lucidity we make two methods.

So first method pro insert item to begin:

In SQL query we see inserted data. Parent value is value, that we stated with select_parent method and send his as argument. As well we handed name value. Left index value is handed value $left + 1, because $left have value of left index item, after which we are inserting. Right index value will be over one larger, than this item haven’t subembranchments.

Important is method _update_tree, to which we will handed two arguments – ID and left index of item, after which we are inserting. This method edits our table so, that it recalculates all of the indexes of embranchments within which we are inserting with exception of embranchment, which we just saved.

After explanation the method shows maybe hard to understand, but is very simple.

After method is called, two SQL queries are made. One edits right index and second edits left index. Now we create only method for inserting of embranchment to the end, which is the same like method for insert to begin, only with simple set-ups.

Now we have finished basic of whole class. We can save new embranchments. In the next article we will look to that, how we can delete and move embranchments.

Everything, what is finished now, we can look once more: