This repository contains an implementation of order statistic tree in Haskell programming language.
I could not find an order statistic tree at Hackage, so I have to develop one.
This implementation uses weight-balanced trees as desribed in
Also some of its code is based on code from containers package.
Implementation of order statistic tree is described in
This package will be deployed to hackage, so you can install it using cabal:
cabal install order-statistic-tree
cabal configure
cabal build
cabal configure --enable-tests --enable-benchmarks
cabal test
I tried to make this tree as fast as possible. I'm not bos, but results on my i7-4790 with 16Gb RAM are following:
cabal configure --enable-tests --enable-benchmarks
cabal bench
If someone knows how to improve these results or benchmarking itself, please don't hesitate to contact me