recursively split line into smaller segments

Question

I have a line. It starts with two indexes, call them 0 and 1, at the outermost points. At any point I can create a new point which bisects two other ones (there must not already be a point between them). However when this happens the indexes need to increment. For example, here's a potential series of steps to achieve N=5 since there are indexes in the result.

              (graph)                 (split between)   (iteration #)
    < ============================ >
    0                              1    0,1          0
    0              1               2    1,2          1
    0              1        2      3    0,1          2
    0      1       2        3      4  

I have two questions:

1. What pseudocode could be used to find the "split between" values given the iteration number?
2. How could I prevent the shape from being unbalanced? Are there certain restrictions I should place on the value of N? I don't particularly care what order the splits happen in, but I do want to make sure the result is balanced.

This is an issue I've encountered when developing a video game.

Answer 1

I agree with jdehesa in that what you are doing does have its similarities with a binary tree. I would recommend looking in using that data structure if you can, since it is highly structured, well-defined, and many great algorithms exist for working with them.

Additionally, as mentioned in the comment section above, a linked list would also be a nice option, since you are adding in a lot of elements. A normal array (which is contiguous in memory) will require you to move many elements over and over again as you insert additional elements, which is slow. A linked list would allow you to add your element anywhere in memory, and then just update a few pointers in the linked list on both sides of where you want to insert it, and be done. No moving things around.

However, if you really just want to put together a working solution using array and aren't concerned with using other data structures, here is the math for the indexing you requested:

Each pair can be listed as (a, b), and we can quickly see b = a + 1. Thus, if you find a, you know b. To get these, you'll need two loops:

iteration := 0
i := 0
while iteration < desired_iterations
    for j = (2 ^ i) - 1; j >= 0 && iteration < desired_iterations; j--
        print j, j + 1
        iteration++
    i++

Where ^ is the exponentiation operator. What we do is find the second to last element in the list (2^i)-1 and count backwards, listing off the indices. We then increment "i" to signify that we've now doubled our array size, and then repeat again. If at any point we research our desired number of iterations, we break out of both loops because we're finished.

Answer 2

I'm not sure if this is the kind of answer you are looking for, but I see this as a binary tree structure. Every tree node contains its own label and its left and right labels. The root of the tree (level 0) would be (2, 0, 1) (split 2 with 0 on the left and 1 and the right). Every node would be split into two children. The algorithm would go something like this:

1. At step N, pick the leftmost node without two children in level floor(log2(N - 1)).
2. Take the node label T and the left and right labels L and R from that node.
   • If the node does not have a left child, add a left child node (N, L, T).
   • If the node already has a left child, add a right child node (N, T, R).
3. N <- N + 1

For example, at iteration 5 you would have something like this:

Level 0:               (2, 0, 1)
                       /        \
                      /          \
                     /            \
Level 1:      (3, 0, 2)          (4, 2, 1)
               /
              /
Level 2: (5, 0, 3)

Now, to reconstruct the current split, you would do the following:

1. Initialize a list S <- [0].
2. For every node (T, L, R) in the tree traversed in postorder:
   • If the node does not have a left child, append T to S.
   • If the node does not have a right child, append R to S.

For the previous case, you would have:

             S = [0]
(5, 0, 3) -> S = [0, 5, 3]
(3, 0, 2) -> S = [0, 5, 3, 2]
(4, 2, 1) -> S = [0, 5, 3, 2, 4, 1]
(2, 0, 1) -> S = [0, 5, 3, 2, 4, 1]

So the complete split would be [0, 5, 3, 2, 4, 1]. The split would be perfectly balanced only when N = 2^k for some positive integer k. Of course, you can annotate the tree nodes with additional "distance" information if you need to keep track of something like that.