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:
    5,873
    Likes Received:
    137
    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,374
    Likes Received:
    28
    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:
    808
    Likes Received:
    2
    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:
    5,873
    Likes Received:
    137
    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