Building segment tree without adding extra elements to its size

Question

I recently learned about segment trees as data structures, and what I learned was that we are always building segment tree with size $N$ such that $N$ is power of two. If $N$ is not power of two we can add more elements to the end of the tree.

However, I was wondering is the segment tree going to work normally if we don't add more elements to make its size power of two.

Example

If the size of segment tree is 8, then we have array of size 15, 15ドル = 2 \cdot 8-1$ In this array we keep track of the intervals, where we have the interval $[1,8]$ on index 1, and on index 2ドル\cdot 1$ we keep the left child, and the right child is on index 2ドル\cdot1+1$.

So our array looks like following:

index 1ドル: [1, 8], 2: [1, 4], 3: [5, 8], 4: [1,2], 5:[3, 4],6:[5, 6], 7:[7, 8],ドル 8ドル[1, 1], 9:[2, 2], 10:[3,3], 11:[4,4], 12:[5,5], 13:[6,6], 14:[7, 7], 15:[8,8]$

Now my question is this: If we run this algorithm for dividing and building the segment tree for numbers that are not power of two (ex. 7, 11, 15).. is it going to build the segment tree normaly, because the segment tree is not going to be full balanced then.

Answer 1

A segment tree is not required to be full (which is what I believe you mean), however it will always be complete. That is, every level, except possibly the last, is filled.

Take a look at the structure and construction to see that it says nowhere that was must have 2ドル^k - 1$ nodes in the tree. For example we may have 2ドル^{k-1} < c < 2^{k}$ elementary intervals, making our tree non-full, but absolutely complete.

---

Example, let's say we have intervals:

$$I = \{[1, 5]^A, [2, 3]^B, [2, 8]^C, [4, 6]^D, [4, 10]^E, [5, 9]^F, [7, 8]^G\}$$

We then have the endpoints of the elementary intervals:

$$I' = \{1, 2, 3, 4, 5, 6, 7, 8, 9, 10\}$$

Now we construct a balanced tree with just the end points as leaves:

elemtree

Next when we insert intervals to get:

segtree

This is fine. Adding in the extra elements is usually a convenience. This is mostly a convenience when using an array to implement the tree. For efficiency reasons, using an array is almost always preferable to an actual tree (Node) object because there is much less overhead. Arrays also make it easier/more natural to implement searching/insertion iteratively rather than recursively which decreases another factor of overhead. The sacrifice of adding at most 2ドルx$ as many nodes is generally worth it. Asymptotically there is no difference.

---

Okay, so using an array is preferable, but why do we need 2ドル^k - 1$ elements? If we have a full binary tree there is almost no edge case handling. Imagine in a recursive procedure we produced a tree like the one above. What would it look like in an array?

I'll show the two different proposals.

1. Our tree if we filled up the last layer and moved all elementary boundaries to leaves (leaves in red and the gradient shows least to greatest boundary, levels are different colored blue boundaries)

arraytree1

2. Our tree if we do not fill up the last layer and left leaves as is.

arraytree2

Clearly (1) should look more appealing, but it is also functionally more appealing. There is only one leaf level, so we need no conditional checking if we are at a leaf or not, we just check which iteration into the tree we are at. There are simply more checks to do per iteration and it is not worth it over filling in the final level. So you can do it, but I wouldn't.

• someone12321: Thank you for your answer, so to sum it up, it is okay if we build the segment tree without having size power of two, and array indexing will work as it should, but adding more elements in the tree would be better because it is easier to iterate through it.
• ryan: @someone12321, yes it is possible, but typically not worth the extra effort and overhead.