Skip to content
A splay tree implementation.
OCaml Makefile
Branch: master
Clone or download
Latest commit f9d83c5 Aug 30, 2019
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
src v0.13-preview.120.41+204 Jun 24, 2019
test v0.13-preview.120.49+223 Aug 19, 2019
.gitignore v0.13-preview.120.27+112 Mar 14, 2019
CONTRIBUTING.md v0.11.120.08+153 Nov 6, 2018
LICENSE.md v0.12-preview.120.18+252 Jan 16, 2019
Makefile v0.12-preview.120.18+252 Jan 16, 2019
README.org v0.13-preview.120.34+189 May 3, 2019
dune-project v0.12-preview.120.18+252 Jan 16, 2019
splay_tree.opam v0.13-preview.121.01+128 Aug 30, 2019

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.

You can’t perform that action at this time.