4 ms·

For 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

For 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 ago
Do you mean OSTs? https://en.wikipedia.org/wiki/Order_statistic_tree https://en.wikipedia.org/wiki/Order_statistic_tree