rbst: Randomized Binary Search Trees

[ data-structures, library, mit ] [ Propose Tags ]

This package contains an implementation of a Randomized Binary Search Tree.

Randomized Binary Search Trees are guaranteed to be Random BST irrespective of the number of insert / delete operations. This guarantees logarithmic time operations (with a constant factor) in the worst case.

[Skip to Readme]

Modules

[Index] [Quick Jump]

RBST
- RBST.Pretty

Downloads

rbst-0.0.0.1.tar.gz [browse] (Cabal source package)
Package description (as included in the package)

Maintainer's Corner

Package maintainers

ArnauAbella

For package maintainers and hackage trustees

edit package information

Candidates

No Candidates

Versions [RSS]	0.0.0.0, 0.0.0.1
Change log	CHANGELOG.md
Dependencies	base (>=4.12 && <4.15), bytestring (>=0.10.8.2 && <0.11.0.0), containers (>=0.5.0.1 && <0.7), deepseq (>=1.4 && <1.5), mersenne-random-pure64 (>=0.2.2.0 && <0.3), text (>=1.2.3.0 && <2.0.0.0), transformers (>=0.5.0.0 && <0.6.0.0) [details]
License	MIT
Copyright	2020 Arnau Abella
Author	Arnau Abella
Maintainer	arnauabella@gmail.com
Category	Data Structures
Home page	https://github.com/monadplus/rbst
Bug tracker	https://github.com/monadplus/rbst/issues
Source repo	head: git clone https://github.com/monadplus/rbst.git
Uploaded	by ArnauAbella at 2020-05-09T18:00:31Z
Distributions
Downloads	355 total (7 in the last 30 days)
Rating	(no votes yet) [estimated by Bayesian average]
Your Rating	λ λ λ
Status	Docs available [build log] Last success reported on 2020-05-09 [all 1 reports]

Readme for rbst-0.0.0.1

[back to package description]

rbst: efficient randomized binary search trees

RBST nodes

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
`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 the extra-deps section of your stack.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.