3 ms·
This reads as an almost textbook description of Cartesian tree.
by kilotaras 7y ago
This reads as an almost textbook description of Cartesian tree.
- jhgg 7y agoCartesian trees do not provide the ability to get items at arbitrary indices within the data structure in an efficient member from my understanding. In order to get the Nth item in the tree, a linear traversal is required. Furthermore, to get the index at which an item is inserted or removed requires the same traversal to accumulate the index.
- kilotaras 7y agoThe common solution is to hold size of subtree in the nodes in addition to the value a.k.a treap with implicit keys.
- foobarqwertz 7y agoI propose a challenge: Provide the interface for the datastructure and the test tool.
- pornel 7y agoBut at this point you're adding even more bookkeeping and implementation complexity just to use a data structure that's not ideal in the first place (for performance, sequential memory layout is better than chasing pointers).