CODEWITHSUNDEEP
c++algorithmbinary-tree
user1021852
user1021852

Reputation: 146

"Climbing" a binary tree

Is there some way to climb tree directly to the number without visiting other branches? For example if I have number 11 I have to visit it going to 2 then to 5 and than to 11 without any kind of search.

                                 0
                            /         \
                           /           \
                          /             \
                        1                2
                      /    \           /    \
                     /      \         /      \ 
                    3        4        5       6
                   / \      / \      / \     / \
                  /   \    /   \    /   \   /   \
                 7     8  9    10   11  12  13  14

I have killed a lot of time the only thing I got by now is that to get the first route(1 or 2) of number N you have to (n-1)/2 till n is equal to 1 or 2. Example: (12 - 1)/2 => (5 - 1)/2 => 2. (7-1)/2=>(3-1)/2 => 1. (11-1)/5=>(2-1)/2 => 1. But end then it would be correct to cut the root (0) and treat 2 like a new one:

          2
         / \
        /   \
       /     \
     5        6
    / \      / \
   /   \    /   \ 
  11   12  13   14

         to

          0
         / \
        /   \
       /     \
     1        2
    / \      / \
   /   \    /   \ 
  3     4  5     6

Solution:

int climb(int ID, Tree<int> t)
{

    int time = 0;
    if (tree.exists()) {
        time += t.value();
        tree t1, t2;
        t.branches(t1, t2);
        int branch = ID;
        while (branch > 2) branch = (branch - 1)/2;
        int offset = 1;
        while (offset*2 < ID - 1) offset *= 2;
        if (aux == 1) time += climb(ID - offset2/, a1);
        if (aux == 2) time += climb(ID - offset, a2);
    }
    return time;
}

You can access ANY(1, 5, 13, etc) element of full binary tree.

Upvotes: 1

Views: 1196

Answers (4)

user1021852
user1021852

Reputation: 146

Other way was to make a stack:

void solve(int n)
{
  stack<direction> path;
 //Calculate the way 
  while (n > 0)
  {
    if (n & 1) // if n is odd;
      path.push_back(left);
    else
      path.push_back(right);

    n = (n - 1) / 2;
  }

  //Do actual "climbing"

  while (!path.empty())
  {
    if (path.top() == left)
    {
      go left
    }
    else
    {
      go right
    }

    path.pop();
  }
}

Thx to Raving_Zealot from linux.org.ru

Upvotes: 0

user1021852
user1021852

Reputation: 146

I wanted to "climb" to any branch or leaf without accessing branches that are not in the way(if I am climbing to '4' then I go directly 0 -> 2 -> 4). And only path I missed was offset that will "morph" branch to tree(see question).

I am getting offset like that:

int offset = 1;
while (offset*2 < ID - 1) offset *= 2;

It works for branch '2' and offset/2 will work for branch '1'.

int climb(int ID, Tree<int> t)
{

    int time = 0;
    if (tree.exists()) {
        time += t.value();
        tree t1, t2;
        t.branches(t1, t2);
        int branch = ID;
        while (branch > 2) branch = (branch - 1)/2;
        int offset = 1;
        while (offset*2 < ID - 1) offset *= 2;
        if (aux == 1) time += climb(ID - offset2/, a1);
        if (aux == 2) time += climb(ID - offset, a2);
    }
    return time;
}

Upvotes: 0

Kashyap
Kashyap

Reputation: 17466

If you want to skip going through all nodes in between use a hash container (e.g. std::map or std::set) and hash search. Binary trees are meant to be traversed recursively. Note that set is not associative so you'll have to work around it a bit.

If you try too hard to add customized code/member-variables to tree/tree-nodes you might end up with a tree impl that's heavy on memory (answer by David is a very bright example of this).

-- edit --

If your IDs are always a sequence without too many holes (e.g. 0, 1, 2,..., 50 OR 68, 69,...,230,231) I recommend the plain old array! Let me know if you want to know more.

In general my msg is to pick the right container/structure first, and then only if needed make "minor" modifications to the structure itself.

Upvotes: 1

pnezis
pnezis

Reputation: 12321

I assume that you have a perfect binary tree (all leaves are at the same depth, and in every parent has two children) and the values of all nodes are like in the example you provided.

In this case, notice the following:

  • A node n has as children the nodes with values 2*n+1, 2*n+2
  • If you want to go to a node with odd value K, then its parent is the node (K-1)/2
  • If you want to visit a node with even value K, its parent is the node (K-2)/2

You repeat the same procedure since you reach node 0 and you have all the nodes you have to visit.

So for your example you want to visit node 11. 

11 is odd so its parent is (11-1)/2 = 5
5 is odd so its parent is (5-1)/2 = 2
2 is even so its parent is (2-2)/0 = 0

we have reached the root node, so you have to follow the path 0->2->5->11

Upvotes: 0

Related Questions