4 ms·
Correct me if I'm wrong, but isn't this exactly the case where you don't want an unbalanced tree? A degenerate tree is bad enough; a degenerate tree implemented
by jhgb 5y ago
Correct me if I'm wrong, but isn't this exactly the case where you don't want an unbalanced tree? A degenerate tree is bad enough; a degenerate tree implemented as an array in this way is catastrophic. So it seems to me that if you're refining the topic further in some sort of talk, the topic of balancing should precede the topic of physically representing the tree as an array.
- ascar 5y agoIt all depends on the specific topic. If I just want to store my data in binary tree structure without the possibility of deletes and just with an insertion-order requirement, then the tree is automatically balanced and using an array like that is totally fine. The use-cases are probably rare (I can't think of a situation from the top of my head), but binary tree doesn't have to mean search tree. The self-balancing part is usually added after the search part as balance is trivial/unimportant when the order/position of the elements has no constraints.
- jhgb 5y ago> The use-cases are probably rare (I can't think of a situation from the top of my head) I imagine there's quite a lot of them. Things like VP-trees and such get often built statically and could be implemented in a similar way. Not sure if the simple (2i, 2i+1) schema is optimal for this but perhaps it could be adapted.
- sureglymop 5y agoYes, you are of course correct. I was thinking of a heap, which is a complete binary tree.