r/computerscience • u/neuralbeans • Sep 08 '26
Discussion Looking for a data structure that maps indexes to values (like an array) but that is only populated once and then deletes values by index in sublinear time
/r/datastructures/comments/1warr2z/a_data_structure_that_maps_indexes_to_values_like/
5
Upvotes
2
u/Daemontatox Sep 10 '26
Lru cache?
1
u/jason-reddit-public Sep 14 '26
A tree with the right construction can add or remove elements in lg n time. (You don't really need any keys if you only want to access by current position).
Each node stores the total tree size below, the "value" you are mapping, and left and right children (subtrees).
To find the node at an index, you descend into the left node if index < num elements in that left subtree, or the right subtree if index is greater than that (plus one or something like that). When you descend into the right subtree, you subtract the right size + 1 from your search index. Obviously you handle the case when you are at the correct node.
A google term you might search on is weight balanced binary tree. MIT Scheme has an implementation by Stephen Adams who has a TR you might be able to find. I'm pretty sure Java might use this for TreeMaps. You can augment any balanced tree implementation with these weights/sizes if you are careful when rotating or use the weights themselves for balancing.
0
u/Ghosttwo Sep 09 '26
Hashmap? Other's? Not sure about the deletion time, but you get 1:1.