Modified Preorder Tree Traversal Algoritm #2

Modified preorder tree traversal is one of the meanings, how to save tree structure in relational database. We will show in this article, how we can erase or move embranchments from created tree.

This article continues to last article “modified preorder tree traversal algorithm #1”, where were explained basic principles of algorithm and we showed basic principles of creating of tree. If you haven’t read, I recommend you to read it.

So we have created table in our database, which we are connecting to, and we have saved structure in that. By each element (embranchment) we have saved left and right index and index of nesting in tree.

Erasing embranchments from tree

Modified preorder tree traversal is algorithm very pleasant, if we look at this from view of dates selecting, indeed from view of editing we can’t make any operation with only one SQL query.

It’s the same like with erasing of embranchments from tree. It isn’t possible to erase one row from table simply, because if we do so, it happen, that left and right indexes wouldn’t agree. So it is important, to check indexes and renumbered tree after erasing of each embranchment.

Method, which we create first, will control, if in embranchment, which we want erase, are no more embranchments. Of course it wouldn’t be problem to erase also the whole parts of tree, but it is absolutely needles. If we want erase one whole part of tree, we can erase it each embranchment singly.

So our class will be enabled to erase only embranchments, which don’t branch out any more, it means, only those, which are on the end of tree.

Method for checking, if embranchment doesn’t branch out any more, will be very simple. Principe is in it, that we will know right and left index of the embranchment, which we are erasing, and we must find out, if there is no embranchment, which has left index between these two embranchments. We must know left and right index in this method, which we are erasing.

Left index will be input value of whole method for erasing embranchment and right index we find out with method “select_parent”, which we created in last article.

So we know both indexes and we can finally create method:

Method _checkTree has return value 1 or 0 in case of finding or non-finding of embranchment. Next method, which we will need, will edit right and left index after erasing.

In last article about traversal algorithm we have created method _update_tree, which care about renumbering of indexes after adding of embranchments. Surely you feel yet, how will method for renumbering looks like after erasing.
Method will be nearly identical, only with different, that instead of rising of indexes we will decline indexes now:

In this method we need know both indexes again, to renumber only good embranchment. We will renumber only those, which has bigger index than erased embranchment.

When we have created methods for checking and renumbering of tree, we can finally erase embranchments. Before erasing we will control, if embranchment doesn’t branch out any more and nearly before erasing we will renumber tree. This operation we will make before erasing from this reason, that if renumbering didn’t do right, erasing don’t happen:

This method return in case of true value one. In case, that other embranchments exists, which are nesting in erasing embranchment, return value -1. In other cases it returns value 0, which symbolize false.

Moving of embranchments in tree

Moving of embranchments is perhaps the most complicated operation, which we will make in tree. For moving of two embranchments we will have to know their left and right indexes. Left indexes will be directly input parameters of method for moving. These input parameters we must check, if they have same level of nesting. If isn’t this reality true, we won’t moving. So we will be limitation again to it, that two embranchment, which we are moving, must have the same level nesting.

We know left index, but we don’t know right index and level of nesting. So we create method for findings these values first.

Method returns array, which is saved right index and level of nesting both embranchments in. This method we call with next method, which we need:

The method _checkingTree checks values of nesting and checks indexes moreover. Return value is array, which contain values from method _select_parent_check.

Now we know all needful values and we can change two embranchments between themselves. By changing there can appear some situations:

First of them appear, when two embranchments are just side-by-side and don’t contain other nested embranchments. This case is the most simple and we should change indexes of embranchments only.

Another case is, that two embranchments are side-by-side, but they have nested other embranchments in them. In this case we have to change indexes also in embranchments extra, which are inside of embranchments, which we are changing. It is logic, because right and left embranchments can’t contain same number of nested embranchments and so each index has to be changed.

The most complicated case appears in situation, when both embranchments, which we are changing, contain other embranchments and there are other embranchments between then extra. In this case we must change indexes in all subembranchments of right embranchment, in all subembranchments of left embranchment and moreover change indexes in all embranchments, which are between these two embranchments.

We have to all take regard to all of these cases and we have to make exception to all of these cases. Now we have created only methods for finding information, which we need for moving.

The smarter will make moving alone, others have to wait for next article.

We can look, what is completed at the end: