Can I use a vector as the underlying data storage for a binary tree

Question

I am building a binary tree to search data. All the examples that I have come across use an array as the underlying data storage mechanism. However, my data is stored in a vector. Can I use a vector as the underlying data storage mechanism for a binary tree?

It depends on what you're doing. It's easier if it's static though you can do one that's dynamic too. The problem with a dynamic array is you have to keep track of indices as they may change over time as the array changes. btw: a *binary search* over a static (sorted) array is not the same thing. Perhaps that's what you want. — Robinson, Jul 04 '15 at 22:11

score 7 · Answer 1 · answered Jul 04 '15 at 22:05

The answer is, "yes you can - and it's desirable from a performance standpoint to do so". An implementation has handily been written for you in the boost library.

http://www.boost.org/doc/libs/1_58_0/doc/html/container/non_standard_containers.html#container.non_standard_containers.flat_xxx

score 1 · Answer 2 · answered Jul 04 '15 at 22:36

In C++, there are:

statically defined arrays - T[constant] - for which the dimension must be a compile-time constant,
dynamically allocated arrays a la new T[variable], where the size can vary at run-time
the Standard library class std::array<T, constant> that wraps a compile-time-sized array
the Standard library class std::vector<T>, which uses dynamically allocated memory and can vary its size at runtime as data is inserted, copying elements from the old to a larger newly dynamically allocated memory area when necessary

The latter library offerings are generally preferable to using T[constant] or new T[variable], as they add Object Oriented features such as member functions for .size(), iterators, and for vector - a destructor performing automatic destruction of elements and deletion of memory.

If your tree will have a compile-time constant upper bound to size, you could use a std::array, but std::vector would allow dynamic sizing which is a more flexible and robust solution.

More generally, your question may surprise or confuse C++ programmers as our common practice is to store binary trees having nodes linked by pointers, rather than contiguous storage. What you ask for is still considered a binary tree in Computing Science - see e.g. here - but most of us normally use the Standard library's std::set<> for this that happens to use nodes linked by pointers.

score 0 · Answer 3 · answered Jul 04 '15 at 22:04

0

Yes.

You use arrays if you want your calculations faster. However the size of your binary tree (or the depth, or order whatever) can not be changed if you use arrays.

answered Jul 04 '15 at 22:04

crbah

338
4
12

1

It can be changed. You can do anything you like with it. – Robinson Jul 04 '15 at 22:10
Array sizes are defined on compile time. So you define the size earlier. – crbah Jul 04 '15 at 22:15
std::array is, std::vector can .resize(n). – Robinson Jul 04 '15 at 22:19
@Robinson it's good to read http://stackoverflow.com/questions/4424579/stdvector-versus-stdarray-in-c – crbah Jul 04 '15 at 22:22
The OP question states that his data is stored in a vector, not an array. – Robinson Jul 04 '15 at 22:24

Can I use a vector as the underlying data storage for a binary tree

3 Answers3