divide a number by 2 recursively

what i needed is…(1) in the first iteration i want 10. (2) in the
second iteration i want 5, 15. (3) in the third iteration i want
3,8,13,18. and so on. – user4365176

I found a tool (in my libraries) which I used to transfer the contents of a vector (of non-decreasing integers) TO a binary tree SUCH-THAT the simple binary tree would be (mostly) balanced.

Here is a version of that code which I simplified for your purpose. This snippet is a method in a class, so the undefined variables prefixed with ‘m_’ (m_tree, m_ss, m_R) are data attributes of that class. m_tree is instance of my home-grown-simple binary tree, with method “insertVal(size_t i)”, m_ss is a pointer to a std::stringstream, and m_R is the user input number, the Range.

‘genSeqRR()’ is recursive. It chops a range in half, then processes the right then the left (somewhat in the form of depth-first-in-order. Currently, the sequence is perhaps slightly biased. Not sure how to describe. See Note 2 (in code).

I also inserted these sequences to an AVL tree (from rosettacode.org/wiki) and the result were disappointing. Possibly not wrong, but not useful here.

You might try this insert sequence with a RedBlack Trees.

---

example outputs after the code:

// Generate a Sequence of size_t values over a fixed limited Range,
// Recursively using binary-pattern through the range, to achieve approximate
// balance when inserting into a simple binary tree.
//
// Note1: 'index' is range (0..N-1), value to insert is (indx+1) i.e 1..N
// Note2: prefer to insert bigger indx first
//
void genSeqRR(size_t depth, const size_t si,  const size_t bi)
  {
     size_t rng = bi - si; // big indx - small indx
     switch (rng)
     {

     default: // 3 or more elements, insert mi, and recurse
     {
        size_t delta = rng / 2;
        size_t    mi = si + delta; // mid index

        (void)m_tree->insertVal(mi+1);  // Note1

        // if(m_ss)
        *m_ss << "    rng:" << std::setw(3) << rng
              << "   dpth:" << std::setw(3) << depth  // depth of genSeqRR
              << "   iVal:" << std::setw(3) << mi+1
              << std::endl;

        // Note2
        genSeqRR (depth+1, mi+1, bi); // recurse on max - (middle + 1) thru biggest index
        genSeqRR (depth+1, si, mi-1); // recurse on min - smallest index thru (middle - 1)
     }
     break;

     case 0: // 1 elment
     {
        (void)m_tree->insertVal (si+1); // Note1

        // if(m_ss)
        *m_ss << "    rng:__1"
              << "   dpth:" << std::setw(3) << depth
              << "   iVal:" << std::setw(3) << si+1 << std::endl;
     }
     break;

     case 1: // 2 consecutive elements
     {
        // Note1,  Note2
        (void)m_tree->insertVal(bi+1);
        (void)m_tree->insertVal(si+1);

        // if(m_ss)
        *m_ss << "    rng:__2"
              << "   dpth:" << std::setw(3) << depth
              << "   iVal:" << std::setw(3) << si+1 << std::setw(3) << bi+1  << std::endl;
     }
     break;

     }// switch
  } // void genSeqRR()

with range m_R = 20,

genSeqRR (1, 0, (m_R-1)); // start recursion over whole range

output:

Anchor->showTallView()
                   '1' 
             '2' 
                         '3' 
                   '4' 
       '5' 
                   '6' 
             '7' 
                         '8' 
                   '9' 
 '10' 
                   '11' 
             '12' 
                         '13' 
                   '14' 
       '15' 
                         '16' 
                   '17' 
             '18' 
                         '19' 
                   '20' 

with range m_R = 19,

genSeqRR (1, 0, (m_R-1)); // start recursion over whole range

output:

Anchor->showTallView()
                   '1' 
             '2' 
                         '3' 
                   '4' 
       '5' 
                   '6' 
             '7' 
                         '8' 
                   '9' 
 '10' 
                   '11' 
             '12' 
                         '13' 
                   '14' 
       '15' 
                   '16' 
             '17' 
                         '18' 
                   '19' 

with range m_R = 19,

Anchor->showTallView()
                   '1' 
             '2' 
                   '3' 
       '4' 
                   '5' 
             '6' 
                         '7' 
                   '8' 
 '9' 
                   '10' 
             '11' 
                         '12' 
                   '13' 
       '14' 
                   '15' 
             '16' 
                         '17' 
                   '18'