I have been using trees as structures to store data, such as categories in a forum. In most cases what happens is that you create a node, for instance a category, that may or may not have a parent. This is called an adjucency matrix, because what you do is, in each node, keep the info about his parent. One other way of representing a tree, especialy usefull in databases, is a nested sets representation. Essentialy, with this one, all you do is create sets of nodes, parent “containing” the children. But is this usefull? Does it make your life easier?
First of all we need to see how each way works. To do this i will explain what fields each node in the tree needs. Each node for the adjucency matrix needs to keep a “pointer” to the parent node. In other words, on an SQL table it could be an integer keeping the parent id if any. If ordering in the same level under each node matters, then we need to keep the place of the node between the childs of the parent. This is all we need. A small example would be something like the one below:
| ID | Name | Parent | Place |
| 1 | Main Category | 0 | 1 |
| 2 | Subcat 1 | 1 | 1 |
| 3 | Subcat 2 | 1 | 2 |
| 4 | Subsubcat 1 | 3 | 1 |
| 5 | Subcat 3 | 1 | 3 |
The same tree, shown above, in this conventional way, is shown in the table below using the Nested sets method.
| ID | Name | Left | Right | Level |
| 1 | Main Category | 1 | 10 | 1 |
| 2 | Subcat 1 | 2 | 3 | 2 |
| 3 | Subcat 2 | 4 | 7 | 2 |
| 4 | Subsubcat 1 | 5 | 6 | 3 |
| 5 | Subcat 3 | 8 | 9 | 2 |
I know, it looks confusing. Let’s take a quick look at a graphic. It will make it much much easier.
I hope this makes it more clear. So, as you can see, each node has a left and a right number indicating, actually, whose child he is and how many child he has. If, for instance, you have the node Subcat 2, the left and right indications are 4 and 7. So he, surely, has a parent. As for the children he has ((7-4)-1)/2=1 childs. Same for Main category. He has ((10-1)-1)/2=4 childs.
So this is another way of representing a tree. But is it better than the adjucency matrix, programing-wise i mean. Let’s take all the possibilities under consideration.
Inserting node: Let’s say we want to insert a node under the main category, on the first level (same level as subcat) after subcat 2 and call it subcat 4. All we have to do is “open” some space between subcat 2 and 3 and put it in there. To do that we have to add 2 (the left and right index of the new category) to all the nodes that have left or right greater than 7 (this is the right index of the category after which we want to add the new one). So the left of subcat 3 will be 10, right will 11 and finally, the right index of the main category should be 12. After that, all we have to do, is insert our new node with left index 8 and right index 9.
Deleting node: This is a bt trickier than adding. The difficult task would be, if the node we want to remove has children. We will see what happens then. The simple one, removing a node without children, is a very simple one so the reader will figure it out in no time. Let’s say we want to remove the subcat 2 node. Here is what we have to do. All the childrens’ nodes indexes have to be updated to index-1 and the other ones that have larger indexes than the right one of the one to be removed have to be index-2. On this example, removing Subcat 2, the subsubcat 1 new indexes should be 4,5 and the subcat 3 should have 6,7, finally the main category’s right index should be updated to 8. One more thing. Do not forget the level! Subsubcat 1’s level was 2, it has to be updated to 1.
Moving node: If we want to move a single node, without children, then things are pretty easy. All we have to do is remove the node and then add it to the new place we want to move it to. For instance, if we want to move subsubcat 1 and place it under subcat 1 all we have to do is remove it as a child from subcat 2, as instructed above, and then add it as a node under subcat 1, also as instructed above. But beware. If we want to move a node that has children, things are not so easy. Let’s say we want to move subcat 2 under subcat 1. The strategy is to remove the whole subtree under subcat 2 including this node and then add them under the subcat 1. Removing the subtree is fairly easy. All we need to do is update all the nodes with greater left or right index than the right index on removal to be right_index-left_index+1. For this example, all indexes with greater value than 7 (the right index of the subcat 2 we are removing) have to be index-(7-4+1)=index-4. So, subcat 3 for instance, will become from (8,9) to (4,5) and main category will have aright index of 6. Then, we have to add the removed subtree under the subcat 1. Here comes the tricky part. What we have to do is, renumber the indexes of all the nodes in the moved subtree to reflect the new situation, then update the indexes of all the rightmost nodes to the node we put the subtree under. Hey! Do not forget the level indicators 😉
Pretty complex situation don’t you think? Well, i do not want to be negative to any method but, in my oppinion, we add much more complexity than we can handle and even need to have. I guess, the usability should be in favor of the programmer on some case but for me, good ole adjucency matrix!