package splay_tree

  1. Overview
  2. Docs
A splay tree implementation

Install

Dune Dependency

Authors

Maintainers

Sources

splay_tree-v0.10.0.tar.gz
sha256=9ea952912c52a269757baa0bf08b060b34edd15c7061c1de60764213ddccae1e
md5=003fb5f4b0fbb71d86f200b9df90abba

Description

Splay trees are binary search trees that move recently accessed nodes closer to the root for easier access. They have amortized O(log n)-time access for a large enough sequence of primitive operations.

A splay trees may outperform other trees such as red-black trees when recently accessed items are more likely to be accessed in the near future.

Notably, this splay tree implementation is parameterized by a reduction operation which lets you specify an extra accumulator value, which can then be searched by efficiently.

Published: 30 Dec 2017

README

README.org

A splay tree implementation.

Splay trees are binary search trees that move recently accessed nodes
closer to the root for easier access.  They have amortized O(log
n)-time access for a large enough sequence of primitive operations.

A splay trees may outperform other trees such as red-black trees when
recently accessed items are more likely to be accessed in the near
future.

Notably, this splay tree implementation is parameterized by a
reduction operation which lets you specify an extra accumulator value,
which can then be searched by efficiently.

Dependencies (6)

  1. ocaml-migrate-parsetree >= "0.4" & < "2.0.0"
  2. jbuilder >= "1.0+beta12"
  3. ppx_jane >= "v0.10" & < "v0.11"
  4. ppx_driver >= "v0.10" & < "v0.11"
  5. core_kernel >= "v0.10" & < "v0.11"
  6. ocaml >= "4.04.1"

Dev Dependencies

None

Used by (1)

  1. incr_dom_widgets < "v0.11.0"

Conflicts

None

OCaml

Innovation. Community. Security.