PHPackages                             locr-company/splay-tree - PHPackages - PHPackages  [Skip to content](#main-content)[PHPackages](/)[Directory](/)[Categories](/categories)[Trending](/trending)[Leaderboard](/leaderboard)[Changelog](/changelog)[Analyze](/analyze)[Collections](/collections)[Log in](/login)[Sign up](/register)

1. [Directory](/)
2. /
3. [Utility & Helpers](/categories/utility)
4. /
5. locr-company/splay-tree

ActiveLibrary[Utility & Helpers](/categories/utility)

locr-company/splay-tree
=======================

Fast splay-tree data structure

1.0.2(1y ago)08[3 issues](https://github.com/locr-company/php-splay-tree/issues)[3 PRs](https://github.com/locr-company/php-splay-tree/pulls)MITPHPPHP >=8.1CI passing

Since Feb 3Pushed 3w ago1 watchersCompare

[ Source](https://github.com/locr-company/php-splay-tree)[ Packagist](https://packagist.org/packages/locr-company/splay-tree)[ RSS](/packages/locr-company-splay-tree/feed)WikiDiscussions main Synced today

READMEChangelogDependencies (7)Versions (14)Used By (0)

Fast splay tree
===============

[](#fast-splay-tree)

[Splay-tree](https://en.wikipedia.org/wiki/Splay_tree): **fast**(non-recursive) and **simple**(< 1000 lines of code) Implementation is adapted directly from this [GitHub Repository](https://github.com/w8r/splay-tree/).

[![php](https://camo.githubusercontent.com/183804d09fec16ca7b6209b007250b7d8db1b915042feb093a9f20e6e1f25359/68747470733a2f2f696d672e736869656c64732e696f2f62616467652f7068702d253345253344253230382e312d3838393242462e737667)](https://camo.githubusercontent.com/183804d09fec16ca7b6209b007250b7d8db1b915042feb093a9f20e6e1f25359/68747470733a2f2f696d672e736869656c64732e696f2f62616467652f7068702d253345253344253230382e312d3838393242462e737667)[![codecov](https://camo.githubusercontent.com/9c481ea43ea11caaf8f14109c931c800772561bdbf18341484910eae1ef3a726/68747470733a2f2f636f6465636f762e696f2f67682f6c6f63722d636f6d70616e792f7068702d73706c61792d747265652f6272616e63682f6d61696e2f67726170682f62616467652e7376673f746f6b656e3d4b45534c5230584c4a4a)](https://codecov.io/gh/locr-company/php-splay-tree)[![Quality Gate Status](https://camo.githubusercontent.com/c3bce7cf670338dd0bc8e24ca9035398362f254677a9b3db352daadfd3b7f530/68747470733a2f2f736f6e6172636c6f75642e696f2f6170692f70726f6a6563745f6261646765732f6d6561737572653f70726f6a6563743d6c6f63722d636f6d70616e795f7068702d73706c61792d74726565266d65747269633d616c6572745f737461747573)](https://sonarcloud.io/summary/new_code?id=locr-company_php-splay-tree)[![github_tag](https://camo.githubusercontent.com/fc210651c253e53b6c87419ef3f550a240d1516b0cce82751459395c67c7e08d/68747470733a2f2f696d672e736869656c64732e696f2f6769746875622f762f7461672f6c6f63722d636f6d70616e792f7068702d73706c61792d74726565)](https://github.com/locr-company/php-splay-tree/tags)[![packagist](https://camo.githubusercontent.com/0a840b12cb47ad9f4e8cafd34449efdf18a1a00d1b9913457f7f3709474bc84e/68747470733a2f2f696d672e736869656c64732e696f2f7061636b61676973742f762f6c6f63722d636f6d70616e792f73706c61792d74726565)](https://packagist.org/packages/locr-company/splay-tree)

This tree is based on **top-down** splaying algorithm by D.Sleator. It supports

- splitting, merging
- updating of the keys
- bulk loading of the items into an empty or non-empty tree
- insertion with duplicates or no duplicates
- lookup without splaying

[![Splay-tree](https://camo.githubusercontent.com/981930a8a4feef1ea057eda71bd631a23300ff169a7205783ad5287326ed9210/68747470733a2f2f692e737461636b2e696d6775722e636f6d2f434e53415a2e706e67)](https://camo.githubusercontent.com/981930a8a4feef1ea057eda71bd631a23300ff169a7205783ad5287326ed9210/68747470733a2f2f692e737461636b2e696d6775722e636f6d2f434e53415a2e706e67)

OperationAverageWorst caseSpace**O(n)****O(n)**Search**O(log n)****amortized O(log n)**Insert**O(log n)****amortized O(log n)**Delete**O(log n)****amortized O(log n)**Install
-------

[](#install)

```
composer require locr-company/splay-tree
```

```