1. Hey Guest Did you know you can win an Honor 10 phone worth ₹33,000 and an additional ₹70,000 in paytm vouchers, just by replying to some threads and taking part in the discussions happening in the Honor Hub?

    What are you waiting for? Start commenting and start winning! Remember to read the instructions posted here.

    Dismiss Notice

C/C++ Beginner's Guide and Post Basic Questions here

Discussion in 'Programming' started by Liverpool_fan, Oct 14, 2010.

  1. Nerevarine

    Nerevarine Well-Known Member

    Joined:
    Feb 6, 2011
    Messages:
    6,155
    Likes Received:
    218
    Trophy Points:
    63
    Location:
    Pune
    Index n = root
    Index 2n+1 = left child
    Index 2n+2 = right child
    If im not mistaken.
     
  2. quicky008

    quicky008 Well-Known Member

    Joined:
    Nov 27, 2007
    Messages:
    1,494
    Likes Received:
    38
    Trophy Points:
    48
    Location:
    Kolkata
    i remember reading somewhere that in an array representation of a tree,

    if node: i

    Child: 2*i, 2*i+1

    Parent: i/2

    Is this a correct way to represent the array elements as nodes of a binary tree?
     
  3. pkkumarcool

    pkkumarcool Game & anime Lover

    Joined:
    Sep 19, 2010
    Messages:
    825
    Likes Received:
    9
    Trophy Points:
    18
    Location:
    Florence
    so both child will be greater than parent? as far as i reme,
    any explanation why i dont get why child is 2*i
     
  4. Nerevarine

    Nerevarine Well-Known Member

    Joined:
    Feb 6, 2011
    Messages:
    6,155
    Likes Received:
    218
    Trophy Points:
    63
    Location:
    Pune
    Simple reason is that we should have a formula for properly mapping out a root node to 2 different unique child nodes which can be easily tracked and there is no collision.
    To be absolutely fair, you can make a binary tree with ANY formula, it is not a given that it should be 2*i, as long as there is a one to one mapping between root -> left child and root -> right child.
    What I mean is, there should not be a situation where
    root1 index -> leftchild1 index
    root1 index -> rightchild1 index

    root2 index -> leftchild1 index
    root2 index -> rightchild2 index


    As you can see from the above example root1 and root2 are both mapped to leftchild1 index, which causes a collision.
    To sum up, a binary tree is just a mapping of root to 2 unique and retrievable child nodes without any collision.

    We use the 2*i format because it is very simple, and wastes very little space. You could literally use ANY hash function to make a custom tree of your own, as long as there is no collision.


    This is wiki's defination
    Arrays[edit]
    Binary trees can also be stored in breadth-first order as an implicit data structure in arrays, and if the tree is a complete binary tree, this method wastes no space. In this compact arrangement, if a node has an index i, its children are found at indices {\displaystyle 2i+1}[​IMG] (for the left child) and {\displaystyle 2i+2}[​IMG] (for the right), while its parent (if any) is found at index {\displaystyle \left\lfloor {\frac {i-1}{2}}\right\rfloor }[​IMG] (assuming the root has index zero). This method benefits from more compact storage and better locality of reference, particularly during a preorder traversal. However, it is expensive to grow and wastes space proportional to 2h - n for a tree of depth h with n nodes.

    This method of storage is often used for binary heaps. No space is wasted because nodes are added in breadth-first order.

    Correct me If I'm wrong.
     

Share This Page