4 releases (breaking)

0.4.0 Oct 17, 2020
0.3.0 May 29, 2019
0.2.0 Mar 2, 2019
0.1.0 Feb 15, 2019

#18 in #red-black-tree

AGPL-3.0

59KB
1.5K SLoC

Left Leaning Red Black Tree

Rustdoc Build Status License: AGPL v3

This package implements LLRB, Left Leaning Red Black, tree a popular data structured, with following features:

  • Self-balancing data structure.
  • Optimized for in-memory index.
  • Each entry in LLRB instance correspond to a {Key, Value} pair.
  • Parametrised over Key type and Value type.
  • CRUD operations, via create(), set(), get(), delete() API.
  • Read optimized.
  • Full table scan, to iterate over all entries.
  • Range scan, to iterate between a low and high.
  • Reverse iteration.

Note that this implementation of LLRB do not provide durability gaurantee and not thread safe.

Licensing

Default license for llrb-index is AGPL-3.0 license. For re-licensing this source, you can either contact the author(s) directly or post your request here #1.

Compatibility policy

llrb-index shall officially support the latest version of rust stable compiler and nightly builds.

Useful links

  • Refer to this Wikipedia link for more information on LLRB algorithm.
  • Discussion on the design choice over get() and range() API.

Dependencies

~570–800KB
~11K SLoC