Here is the situation, I need to organize some users like an binary tree to explain organization workflow, but organization can change.

Here is how its look like:

      /     \
     2       3
    / \     / \
   4   5   6   7

Its sounds easy:

Lets imagine this is the user table:

id | user  | position | who_contracted
1  | ana   | 1        | null
2  | bob   | 2        | 1
3  | joe   | 3        | 1
4  | Nik   | 6        | 3
5  | Ahn   | 4        | 1
6  | Rob   | 5        | 2
7  | Chloe | 7        | 1

Ana contracted 4 people in organization, IDs [2,3,5,7] They are organized as they come to business.

But, when Ana was inviting they, Joe[3] invited Awn[5] to business. Its seat goes to be seat [6].

When Ana[1] invite 1 more, the next opened seat is 4, because each invited people get first seat from left to right down the user who contracted him

It makes easy to build an strong sales team.

Now, I need to know how to find next seat to user in position 3.

I know how to do it with math, but do not know how to organize correctly the database.

For sample, if User id 3 invite one more, will get the seat 12, but if user id 6, invite first, seat will be 12 also.

I need to calculate just in time when insert into table.

Any ideas??

ps. One more thing, I'm trying a way, that if I delete user 3, the users down come to up automatically, user on seat 6 will up to seat 3, because it is on low position compared with next user position, that is 7.

closed as unclear what you're asking by ypercubeᵀᴹ, Erik Darling, Philᵀᴹ, hot2use, Mr.Brownstone Dec 15 '17 at 13:57

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 2
    If you figured it out in math, just put that value into "position". What you are trying to do is called a "self balancing binary tree". That's actually not a trivial task (and the data model is the least relevant part of it). A standard implementation of that is an AVL-tree or the red-black-tree. You have to implement functions for insert/delete in sql. Or implement e.g. the (slow) DSW-algorithm after a change to the tree. – Solarflare Aug 15 '17 at 7:53
  • Why does the tree have to be self-balancing? For internal storage reasons? – Evan Carroll Aug 15 '17 at 18:19
  • @EvanCarroll because business logic... or I'll need recalculate entire tree to save on database on each new register or delete of user – Raphael Schubert Aug 16 '17 at 19:49
  • 1
    I guess I just don't see how this is business logic. It's not clear why you're allocating seats in such a bizarre fashion. – Evan Carroll Aug 16 '17 at 19:51
  • 1
    @RaphaelSchubert so tell us how the bonus structure is not some goofy problem with seats. Use math stop trying model arbitrary structures in a relational database. It's not how the data relates. – Evan Carroll Aug 16 '17 at 20:52

I think this question is principally, "how do you incentivize salesmen in a pyramid scheme?" That's cute, so yeah let's do it. Let's assume

  1. We have 7 people in our scheme.
  2. We allocate bonuses based on the tier of pyramid.

You don't have to place them in a visual pyramid to figure this out..

CREATE TABLE my_pyramid_scheme(empid, name, is_active)
  SELECT id::int, (id+64)::int::"char", true
  FROM generate_series(1,7) AS gs(id);

Now you've got

 empid | name | is_active 
     1 | A    | t
     2 | B    | t
     3 | C    | t
     4 | D    | t
     5 | E    | t
     6 | F    | t
     7 | G    | t

So first we need to know what tier they're on... For that we use 2n-1. For example, if your number is 1.

2n-1 = 1
2n = 2
n = 1 -- you're on tier one

Now if your number is 6

2n-1 = 6
2n = 7
n = 3.5 -- trunc(3.5) you're on tier three.

So after you know what tier they're on. You need to find how much of a bonus they get.. That's a function of the tier they're on, and the maximum amount of tiers, to find that take the largest number and run it through the same process. With those two things, you typically have some geometric function that determines "incentive."

And, now you can run illicit drug cartel or compete with Herbalife.

Disabling members

If in the above you ever set is_active = false run these super fast operations on the row_number..

SELECT *, row_number() OVER (ORDER BY empid) AS newid
FROM my_pyramid_scheme;

On Oct 26, 2012, I answered the post How badly does innodb fragment in the face of somewhat out-of-order insertions?, where I briefly discussed loading a Binary Tree without any AVL rotations.

Here is the example from that old post: For the numbers 1-15, when balancing the tree by numerical order, you have these four(4) combinations that will require not a single AVL rotation:

  • 8,4,12,2,6,10,14,1,3,5,7,9,11,13,15
  • 8,12,4,14,10,6,2,1,3,5,7,9,11,13,15
  • 8,4,12,2,6,10,14,15,13,11,9,7,5,3,1
  • 8,12,4,14,10,6,2,15,13,11,9,7,5,3,1

This is what the tree would look like

             / \
            /   \
           /     \
          /       \
         /         \
        /           \
      04             12
     /   \         /   \
   02     06     10     14
  /  \   /  \   /  \   /  \
 01  03 05  07 09  11 13  15

What you must determine is the the order to insert based on the tree's maximum height.The maximum height for a binary tree would be (LN(number of nodes) / LN(2)) + 1.

This means the following:

       1 person in a 1-level tree
       3 people in a 2-level tree
       7 people in a 3-level tree
      15 people in a 4-level tree
      31 people in a 5-level tree
(2^N -1) people in a N-level tree

You should create the tree first and then fill in the ids to associate to each node. This is all based on a binary tree with AVL balancing but without the rebalancing.

The math is very straightforward.

Let's say you have N people. (Let's say N is 15)

The formula (LN(N) / LOG(2)) + 1 gives the maximum tree height ( MTH ).

Get the average of 1 and (2^MTH - 1). That becomes the root.

Take half the distance and go forward and back (4 and 12)

Repeat this until half the distance is less than one.

Sorry, for the vague recursion but the end result is drawn for you.

Now, go about assigning the user ids to each number starting from the root.

  • mmm sounds interesting, will do some tests this weekend and see how my current logic works with this approach... ty for now! – Raphael Schubert Aug 16 '17 at 19:50

Not the answer you're looking for? Browse other questions tagged or ask your own question.