Monthly Downloads: 7
Programming language: Haskell
License: MIT License
Tags: Data Structures    
Latest version: v0.0.0.1

rbst alternatives and similar packages

Based on the "Data Structures" category.
Alternatively, view rbst alternatives based on common mentions on social networks and blogs.

Do you think we are missing an alternative of rbst or a related project?

Add another 'Data Structures' Package


rbst: efficient randomized binary search trees

[RBST nodes](./images/rbst.png) Hackage GitHub CI Build Status [MIT license](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
>>> lookup 'd'
Just 4
>>> lookup 'a' $ insert 'a' 7 tree
Just 7
>>> lookup 'd' (delete 'd' tree)

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:

  1. Add the dependency in your project's .cabal file:
    build-depends: base ^>= 4.14
                 , rbst ^>=
  1. In the module where you wish to use rbst, add the (qualified) import:
   import qualified RBST
  1. If rbst is not available on your current Stackage resolver yet, you can still use it by adding the following in the extra-deps section of your stack.yaml file:

      - rbst-
  2. Then you can add it as a dependency in your package.yaml file as usual:

        - rbst


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.