rbst alternatives and similar packages
Based on the "Data Structures" category.
Alternatively, view rbst alternatives based on common mentions on social networks and blogs.
-
Agda
Agda is a dependently typed programming language / interactive theorem prover. -
vinyl
Extensible Records for Haskell. Pull requests welcome! Come visit us on #vinyl on freenode. -
repa-convert
High performance, regular, shape polymorphic parallel arrays. -
repa-scalar
High performance, regular, shape polymorphic parallel arrays. -
parameterized-utils
A set of utilities for using indexed types including containers, equality, and comparison. -
ethereum-client-haskell
A Haskell version of an Ethereum client -
type-level-sets
Type-level sets for Haskell (with value-level counterparts and various operations) -
justified-containers
Standard containers, with keys that carry type-level proofs of their own presence. -
bytestring-trie
An efficient finite map from (byte)strings to values. -
nonempty-containers
Efficient non-empty variants of containers data types, with full API -
claferIG
Support for reasoning on Clafer models by instantiation and counter example generation. -
selections
Haskell Package for operating with selections over an underlying functor -
map-syntax
Syntax sugar and explicit semantics for statically defined maps -
igraph
Incomplete Haskell bindings to the igraph library (which is written in C)
WorkOS - The modern identity platform for B2B SaaS
Do you think we are missing an alternative of rbst or a related project?
README
rbst: efficient randomized binary search trees
[RBST nodes](./images/rbst.png) [](LICENSE)
Efficient implementation of the Randomized Binary Search Trees data structure.
When to use this package?
Randomized Binary Search Trees are useful when you cannot make assumptions on the input distribution but you still need fast (logarithmic time complexity) insert
/lookup
/delete
/at
/union
/etc. operations. It is guaranteed efficient self-balancing. Below you can find the table of time complexity for all operations (where n
is the size of the tree):
Operation | Time complexity | Description |
---|---|---|
size |
O(1) |
Count elements in the tree |
height |
O(log n) w.h.p |
Height of the tree |
lookup |
O(log n) |
Access by key |
insert |
O(log n) |
Insert an element with the given key |
delete |
O(log n) |
Delete the element associated to the given key |
take |
O(log n) |
Take first i-th elements |
drop |
O(log n) |
Drop first i-th elements |
at |
O(log n) |
Access by index |
remove |
O(log n) |
Remove the i-th element |
union |
O(m + n) |
Union of two trees |
intersection |
O(m + n) |
Intersection of two trees |
subtraction |
O(m + n) |
Subtraction of two trees |
difference |
O(m + n) |
Symmetric difference of two trees |
Usage example
>>> :set -XOverlodadeLists
>>> import GHC.Exts
>>> import RBST
-- Manually created
>>> let tree = insert 'a' 1
$ insert 'b' 2
$ insert 'c' 3
$ insert 'd' 4
$ insert 'e' 5
$ empty
-- Using 'OverloadedLists'
>>> let tree = (fromList $ zip ['a'..'e'] [1..5]) :: RBST Char Int
>>> RBST.prettyPrint tree
('b',2) [5]
╱╲
╱ ╲
╱ ╲
╱ ╲
╱ ╲
╱ ╲
╱ ╲
╱ ╲
╱ ╲
('a',1) [1] ('d',4) [3]
╱╲
╱ ╲
╱ ╲
╱ ╲
╱ ╲
╱ ╲
('c',3) [1] ('e',5) [1]
-- Queries
>>> size tree
5
>>> lookup 'd'
Just 4
>>> lookup 'a' $ insert 'a' 7 tree
Just 7
>>> lookup 'd' (delete 'd' tree)
Nothing
How to use it
In order to start using rbst
in your project, you will need to set it up with the two easy steps:
- Add the dependency in your project's
.cabal
file:
build-depends: base ^>= 4.14
, rbst ^>= 0.0.0.0
- In the module where you wish to use
rbst
, add the (qualified) import:
import qualified RBST
Stack
If
rbst
is not available on your current Stackage resolver yet, you can still use it by adding the following in theextra-deps
section of yourstack.yaml
file:extra-deps: - rbst-0.0.0.0
Then you can add it as a dependency in your
package.yaml
file as usual:library: dependencies: - rbst
Acknowledgement
To the authors C. Martinez and S. Roura.
To D. Kovanikov and his project implicit treap.
Icons designed by Freepik from www.flaticon.com.
*Note that all licence references and agreements mentioned in the rbst README section above
are relevant to that project's source code only.