Is there any speed/space/general performance gains in using array based implementation of a binary tree rather than the old node-based implementation? I understand rotations or any other complex modifications of an array based tree would be horrific but in the case of a simple binary tree implementation would you say one would be better off doing it via arrays?
Add a comment
|
3 Answers
I guess that you are looking for a Binary Heap.
3 Comments
Bober02
yeah, I know abot heaps, but is there any gain in space/performanceof doing that over node-based implementation?
Jack
You surely have a gain in space, since you don't need to store any pointer (two per node), regarding performance it mainly depends on what kind of operations you are going to do with the data. A heap can be used to store a binary tree but it's not exactly the same thing (just because it enforces some constraints that a binary tree doesn't have)
Bober02
Well I think we can make a binary tree in the similar fashion as heaps with a help of an array. Only deletion would be tricky...
The array based version doesn't use an heap allocations, so it will most likely all fit in cache and require simpler pointer math speeding up the amount of reads it takes to traverse. If you now the size is limited and bounded at compile time, it's the faster solution.
Comments
If your primary workflow consists of building a tree and then tearing it down by a series of delete and delete-range operations, then a binary tree embedded in array can be much faster than a pointer-based tree. See TeardownTree. Also see this answer.
