package splay_tree

  1. Overview
  2. Docs
A splay tree implementation

Install

Dune Dependency

github.com Readme MIT License Edit opam file Versions (7)

Authors

  1. J
    Jane Street Group, LLC

Maintainers

  1. J
    Jane Street developers

Sources

splay_tree-v0.13.0.tar.gz
md5=fd926dcdef1c6db78f450687c7e40cde

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: 20 Nov 2019

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 (4)

  1. dune >= "1.5.1"
  2. ppx_jane >= "v0.13" & < "v0.14"
  3. core_kernel >= "v0.13" & < "v0.14"
  4. ocaml >= "4.08.0"

Dev Dependencies

None

Used by (2)

  1. incr_dom_partial_render = "v0.13.0"
  2. incr_dom_widgets >= "v0.13.0"

Conflicts

None