Hacker News Reader

The order statistic tree was covered in the CLRS book. In the 4th edition, it is chapter 17 "Augmenting Data Structures", subchapter 1 "Dynamic order statistics". (I know for a fact it was present in the 3rd and 2nd editions too; did not check the 1st.)

I used this knowledge to implement a tree-based list data structure, with no set functionality at all: https://www.nayuki.io/page/avl-tree-list

View on HN

By separating "seek" (min/max/key/nth) from "edit" (in-del) and "balance" (AVL, red-black, etc.) operations, you can indeed cover a lot of bases as elaborated here: https://github.com/c-blake/bst (including also how you handle duplicate keys as well as the perhaps less useful neither-ranked-nor-keyed access, wherein the trees are kind of a double-ended queue with just "edge access").

>perhaps less useful neither-ranked-nor-keyed access, wherein the trees are kind of a double-ended queue with just "edge access"

For normal btrees this is absolutely true. For b+trees you will see this basically everywhere.

Reply on news.ycombinator.com