3 ms·
We needed to support arbitrary index access into the sorted set - which is why stdlib btree map doesn't work.
by jhgg 6y ago
We needed to support arbitrary index access into the sorted set - which is why stdlib btree map doesn't work.
- c0deb0t 6y agoFor binary trees, indexing can be done by saving the subtree size of each node and doing a sort of binary search. Not sure if this is fast for B-trees that have more than 2 children nodes, though.
- Lichtso 6y agoDo you mean OSTs? https://en.wikipedia.org/wiki/Order_statistic_tree https://en.wikipedia.org/wiki/Order_statistic_tree
- ntonozzi 6y agoOh, that makes sense. I like the solution you arrived at!