3 ms·
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
by nayuki 2y ago
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 https://www.nayuki.io/page/avl-tree-list
- cb321 2y agoBy 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 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").
- turndown 2y ago>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.