Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
Is it possible to create an interval tree using an array instead of the traditional pointer method? I know that for segment trees this is commonly done where the children of any element with index i are stored in 2i and 2i + 1 and the range is halved. For interval trees however, because the ranges added are not guaranteed to be halved each time, it seems like it might not be possible.
Could anyone prove or disprove whether interval trees can be implemented in this manner?
To a mathematician "prove or disprove" is a very strict requirement. I do not know how serious I should take this.
Every tree that has been implemented using pointers also has a array implementation. The trick is to do the addresses yourself as indexes to an array. That is usually called a cursor implementation.
Binary trees can be implemented, as you say, storing children of node $i$ at indices $2i$ and $2i+1$. This is sometimes called an implicit representation as no explicit structure is stored. The method is alwaus possible, but only advisable when the tree is perfect (all levels completely filled) or near perfect, like the complete trees used to store a binary heap. Otherwise it is a waste of space. When some node $i$ is missing in the tree then also nodes $2i$ and $2i+1$ are missing, and $4i,\dots, 4i+4$, etc.
