CODEWITHSUNDEEP
data-structurestreesegment
AJAY HAYAGREEVE
AJAY HAYAGREEVE

Reputation: 168

why segment tree is implemented using arrays instead of BT

i ve a doubt on segment tree implementation. Why segment tree is implemented using arrays and not binary tree ?

if i implement it using arrays what benefits do i get and if implement as a binary tree then what is the problem ? For implementing using arrays we need to use the left child function as 2*i+1 and right child function as 2*i+2.If we implement as a binary tree we can simply do node -> lft & node->rht. But what is the problem ? Thanks

Upvotes: 2

Views: 374

Answers (2)

Ast15
Ast15

Reputation: 81

Another advantage of representing as an array is we have both links from parents to children as well as from children to parents.

Upvotes: 0

Stefan Haustein
Stefan Haustein

Reputation: 18803

The advantage is density. An array takes about as much space as the contents. For a binary tree, there is memory management overhead for each node. The child pointers need extra space, too. Also, an array is typically in a continuous memory location whereas tree nodes might get distributed all over the heap, meaning that memory caching is less likely to help.

Upvotes: 2

Related Questions