Binary Tree Algorithm (Different Approach)

Question

I'm trying to develop an algorithm for an mysql binary tree. It works like that:

Table "network": id_network, parent, child, position

Ir works like that, a new user enters the system with a parent. I search if the parent has childrens already, if doesnt, i add the new user as a child of parent and the position. (If has no childer, go to left first, then right)

Each parent can only have two children, so the next one will have to be his grandson and so on. (From left to right)

I have my php code:

function insertUser($user, $parent) {

    $childs = $db -> read('parent =' . $parent); // Return an array with the results from network

    $data['parent'] = $parent;
    $data['child'] = $user;

    if(!$childs[0]) {            
        $data['position'] = 'left';
        $db -> insert($user);
    }else{
        if(!$childs[1]) {
            $data['position'] = 'right';
            $db -> insert($user);
        }
    }
}

I have this block and I know that only with this I could traverse the whole tree, even if had 300 children below parent.

Could anybody help me what could I do now to achieve an insertion in the first empty space from the left to right. I think it's worth it to notice... I ahve serched the whole internet but the approach I want, I cannot find and cannot create too.

if you only began, i'd recommend you to do switch this to noSQL db like mongoDB, you can actually save references and build the stored data as a tree — Daniel Krom, Aug 14 '15 at 18:46
As in matter of fact, I have pretty good experience in MongoDB and with it would be perfect and easy. The big problem is that my client uses a server that is not a VPC and doesnt have noSQL. — Raf Zeres, Aug 14 '15 at 18:53
maybe interesting? [mysql hierarchy storage with large trees](http://stackoverflow.com/questions/14114280/mysql-hierarchy-storage-with-large-trees). Also: [Nested set model practical examples, part I](http://we-rc.com/blog/2015/07/19/nested-set-model-practical-examples-part-i). All untested — Ryan Vincent, Aug 14 '15 at 20:45
@RyanVincent Thank you so much, man. I took a look there and seems to be what I need. Cheers — Raf Zeres, Aug 16 '15 at 10:11

score 0 · Answer 1 · answered Aug 17 '15 at 19:36

After a lot of searches, study and the amazing link shared by @Ryan Vincenti - I got a solution.

To make something like that you will have to use a few things:

Power of 2 (2, 4, 8, 16, 32, 64 ...) for each level you want
To get the childrens on left, you use this (2*n)
To get childrens on right, you use this (2*n + 1)

In this approach I used this kind of db schemma:

Table "network":

id_network (primary key | auto increment)
id_user (int)
location (int)

When you want to insert a new user on the tree, you check each level from the location of parent (using power of 2). For example: If we wanted to insert a new "user"... Lets say this new "user" has a parent (his location is 3).

First we get the "parent" location. Let's say that parent has location 3 and has no children. You know before insert it that new "user" would be the left son of "parent". But how would we insert it into the tree? Simple enough:

You loop trought 2, 4, 8 ... And check each level if has all the childrens, if hasnt, you take the last children position and add 1+ (you got the new location of your new user)

A few observations:

To get each level, you can use BETWEEN first_level_number AND last_level_number. To get your first number, use the formula (2*n) and to get your last, use (2*n+1)

I hope this helps other people.

Binary Tree Algorithm (Different Approach)

1 Answers1