PHPackages                             willvincent/splaytree - 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. willvincent/splaytree

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

willvincent/splaytree
=====================

A flexible PHP splay-tree implementation.

1.3(1y ago)15.4k↑21.3%11MITPHPPHP ^8.2.0

Since Feb 23Pushed 1y ago1 watchersCompare

[ Source](https://github.com/willvincent/splay-tree)[ Packagist](https://packagist.org/packages/willvincent/splaytree)[ RSS](/packages/willvincent-splaytree/feed)WikiDiscussions master Synced 2d ago

READMEChangelog (2)Dependencies (2)Versions (3)Used By (1)

PHP Splay Tree Implementation
=============================

[](#php-splay-tree-implementation)

[![PHP Version](https://camo.githubusercontent.com/0f16581d1180dbfd4c0e13166ec1267d4ad2f2fab8281ea6d6b284cf5c65d921/68747470733a2f2f696d672e736869656c64732e696f2f62616467652f5048502d382e322532422d626c75652e737667)](https://camo.githubusercontent.com/0f16581d1180dbfd4c0e13166ec1267d4ad2f2fab8281ea6d6b284cf5c65d921/68747470733a2f2f696d672e736869656c64732e696f2f62616467652f5048502d382e322532422d626c75652e737667)[![License](https://camo.githubusercontent.com/7013272bd27ece47364536a221edb554cd69683b68a46fc0ee96881174c4214c/68747470733a2f2f696d672e736869656c64732e696f2f62616467652f6c6963656e73652d4d49542d626c75652e737667)](https://camo.githubusercontent.com/7013272bd27ece47364536a221edb554cd69683b68a46fc0ee96881174c4214c/68747470733a2f2f696d672e736869656c64732e696f2f62616467652f6c6963656e73652d4d49542d626c75652e737667)[![Latest Version](https://camo.githubusercontent.com/8e3affa80b7624d12780c7db4c9fd3d63616e44e338b0ecf3e0aad6c0b9ce8e8/68747470733a2f2f696d672e736869656c64732e696f2f7061636b61676973742f762f77696c6c76696e63656e742f73706c6179747265652e737667)](https://camo.githubusercontent.com/8e3affa80b7624d12780c7db4c9fd3d63616e44e338b0ecf3e0aad6c0b9ce8e8/68747470733a2f2f696d672e736869656c64732e696f2f7061636b61676973742f762f77696c6c76696e63656e742f73706c6179747265652e737667)[![CI Tests](https://github.com/willvincent/splay-tree/actions/workflows/ci.yml/badge.svg)](https://github.com/willvincent/splay-tree/actions/workflows/ci.yml/badge.svg)

A robust and efficient [Splay Tree](https://en.wikipedia.org/wiki/Splay_tree) implementation in PHP, designed for scenarios where frequently accessed elements should be quickly retrievable. This library provides a self-balancing binary search tree that automatically adjusts to prioritize recently accessed nodes, making it ideal for use cases like caching, priority queues, or any application where recent access patterns matter.

Table of Contents
-----------------

[](#table-of-contents)

- [Installation](#installation)
- [Basic Usage](#basic-usage)
- [API Documentation](#api-documentation)
- [Advanced Usage](#advanced-usage)
- [Performance Considerations](#performance-considerations)
- [Testing](#testing)
- [Contributing](#contributing)
- [License](#license)

Installation
------------

[](#installation)

To install the SplayTree library, use Composer:

```
composer require willvincent/splay-tree
```

Basic Usage
-----------

[](#basic-usage)

### Creating a SplayTree

[](#creating-a-splaytree)

You can instantiate a `SplayTree` with or without a custom comparator. By default, it uses PHP’s [spaceship operator](https://www.php.net/manual/en/migration70.new-features.php#migration70.new-features.spaceship-op)(``) for comparisons.

```
use SplayTree\SplayTree;

// Default comparator (spaceship operator)
$tree = new SplayTree();

// Custom comparator for integers
$tree = new SplayTree(function ($a, $b) {
    return $a  $b;
});
```

### Inserting Elements

[](#inserting-elements)

Add elements to the tree using the `insert` method:

```
$tree->insert(5);
$tree->insert(3);
$tree->insert(7);
```

### Searching for Elements

[](#searching-for-elements)

Search for an element with the `search` method. If found, it splays the element to the root and returns it; otherwise, it returns `null`.

```
$found = $tree->search(3);
if ($found !== null) {
    echo "Found: " . $found . "\n"; // Found: 3
}
```

### Deleting Elements

[](#deleting-elements)

Remove an element from the tree with the `delete` method:

```
$tree->delete(3);
```

API Documentation
-----------------

[](#api-documentation)

Here’s a detailed breakdown of the `SplayTree` class’s public methods, including descriptions, parameters, return types, and examples.

### `insert($data): void`

[](#insertdata-void)

Inserts a new element into the tree and splays it to the root.

#### Parameters:

[](#parameters)

- `$data`: The data to insert (mixed type).

#### Example:

[](#example)

```
  $tree->insert(10);
```

---

### `search($data): mixed|null`

[](#searchdata-mixednull)

Searches for an element. If found, it splays the element to the root and returns it; otherwise, returns `null`.

#### Parameters:

[](#parameters-1)

- `$data`: The data to search for (mixed type).

#### Returns:

[](#returns)

- The found data or `null`.

#### Example:

[](#example-1)

```
  $result = $tree->search(10);
  echo $result !== null ? "Found: $result" : "Not found";
```

---

### `delete($data): void`

[](#deletedata-void)

Deletes an element from the tree if it exists.

#### Parameters:

[](#parameters-2)

- `$data`: The data to delete (mixed type).

#### Example:

[](#example-2)

```
  $tree->delete(10);
```

---

### `min(): mixed|null`

[](#min-mixednull)

Finds the minimum element, splays it to the root, and returns its data.

#### Returns:

[](#returns-1)

- The minimum data or `null` if the tree is empty.

#### Example:

[](#example-3)

```
  $min = $tree->min();
  echo $min !== null ? "Min: $min" : "Tree is empty";
```

---

### `max(): mixed|null`

[](#max-mixednull)

Finds the maximum element, splays it to the root, and returns its data.

#### Returns:

[](#returns-2)

- The maximum data or `null` if the tree is empty.

#### Example:

[](#example-4)

```
  $max = $tree->max();
  echo $max !== null ? "Max: $max" : "Tree is empty";
```

---

### `next($data): mixed|null`

[](#nextdata-mixednull)

Finds the successor of the given data, splays it to the root, and returns its data.

#### Parameters:

[](#parameters-3)

- `$data`: The data to find the successor of (mixed type).

#### Returns:

[](#returns-3)

- The successor’s data or `null` if no successor exists.

#### Example:

[](#example-5)

```
  $next = $tree->next(5);
  echo $next !== null ? "Next: $next" : "No successor";
```

---

### `prev($data): mixed|null`

[](#prevdata-mixednull)

Finds the predecessor of the given data, splays it to the root, and returns its data.

#### Parameters:

[](#parameters-4)

- `$data`: The data to find the predecessor of (mixed type).

#### Returns:

[](#returns-4)

- The predecessor’s data or `null` if no predecessor exists.

#### Example:

[](#example-6)

```
  $prev = $tree->prev(5);
  echo $prev !== null ? "Prev: $prev" : "No predecessor";
```

---

### `getSize(): int`

[](#getsize-int)

Returns the number of elements in the tree.

#### Returns:

[](#returns-5)

- The size of the tree (integer).

#### Example:

[](#example-7)

```
  $size = $tree->getSize();
  echo "Tree size: $size";
```

---

### `isEmpty(): bool`

[](#isempty-bool)

Checks if the tree is empty.

#### Returns:

[](#returns-6)

- `true` if empty, `false` otherwise.

#### Example:

[](#example-8)

```
  if ($tree->isEmpty()) {
      echo "Tree is empty\n";
  }
```

---

### `clear(): void`

[](#clear-void)

Removes all elements from the tree.

#### Example:

[](#example-9)

```
  $tree->clear();
```

---

### `contains($data): bool`

[](#containsdata-bool)

Checks if the tree contains the specified data without modifying the tree structure.

#### Parameters:

[](#parameters-5)

- `$data`: The data to check for (mixed type).

#### Returns:

[](#returns-7)

- `true` if the data exists, `false` otherwise.

#### Example:

[](#example-10)

```
  if ($tree->contains(5)) {
      echo "Tree contains 5\n";
  }
```

---

### `toString(callable $printNode): string`

[](#tostringcallable-printnode-string)

Converts the tree to a string representation using a provided callback to format each node’s data.

#### Parameters:

[](#parameters-6)

- `$printNode`: A callable that takes a node’s data and returns its string representation.

#### Returns\*\*:

[](#returns-8)

- A string representation of the tree (e.g., in-order traversal).

#### Example\*\*:

[](#example-11)

```
  echo $tree->toString(function ($data) {
      return (string)$data;
  });
```

---

### Iteration

[](#iteration)

The tree implements `IteratorAggregate`, allowing iteration over elements in order.

#### Example:

[](#example-12)

```
  foreach ($tree as $data) {
      echo $data . "\n";
  }
```

Advanced Usage
--------------

[](#advanced-usage)

### Using a Custom Comparator

[](#using-a-custom-comparator)

For complex data types like objects, define a custom comparator:

```
class Person {
    public $age;
    public function __construct($age) {
        $this->age = $age;
    }
}

$comparator = function ($a, $b) {
    return $a->age  $b->age;
};

$tree = new SplayTree($comparator);
$tree->insert(new Person(25));
$tree->insert(new Person(30));
$tree->insert(new Person(20));

$minPerson = $tree->min();
echo $minPerson->age; // 20
```

### Splaying Behavior

[](#splaying-behavior)

Operations like `search`, `insert`, or `delete` splay the accessed or modified node to the root, optimizing future access:

```
$tree->insert(3);
$tree->insert(5);
$tree->search(3); // Splays 3 to the root

echo $tree->getRoot(); // 3
```

Performance Considerations
--------------------------

[](#performance-considerations)

- **Time Complexity**: Operations (`insert`, `delete`, `search`) have an amortized time complexity of O(log n).
- **Splaying Advantage**: Frequent access to the same elements reduces access time, making this structure efficient for caching or similar use cases.

Testing
-------

[](#testing)

The library is thoroughly tested with PHPUnit. To run the tests:

1. Install dependencies: ```
    composer install
    ```
2. Run PHPUnit: ```
    vendor/bin/phpunit
    ```

Good news—**all tests are passing**! You’re ready to use this library with confidence.

Contributing
------------

[](#contributing)

Contributions are welcome! Please submit issues or pull requests to the [GitHub repository](https://github.com/willvincent/splay-tree). Follow standard guidelines for code style and include tests with your submissions.

License
-------

[](#license)

This project is licensed under the MIT License - see the [LICENSE](LICENSE.md) file for details.

###  Health Score

35

—

LowBetter than 77% of packages

Maintenance41

Moderate activity, may be stable

Popularity25

Limited adoption so far

Community10

Small or concentrated contributor base

Maturity52

Maturing project, gaining track record

 Bus Factor1

Top contributor holds 100% of commits — single point of failure

How is this calculated?**Maintenance (25%)** — Last commit recency, latest release date, and issue-to-star ratio. Uses a 2-year decay window.

**Popularity (30%)** — Total and monthly downloads, GitHub stars, and forks. Logarithmic scaling prevents top-heavy scores.

**Community (15%)** — Contributors, dependents, forks, watchers, and maintainers. Measures real ecosystem engagement.

**Maturity (30%)** — Project age, version count, PHP version support, and release stability.

###  Release Activity

Cadence

Every ~1 days

Total

2

Last Release

494d ago

### Community

Maintainers

![](https://www.gravatar.com/avatar/0c6239b14bdb77aba00cd0bc65f561ad8dd694ec4a18508c69eff119352d54fa?d=identicon)[willvincent](/maintainers/willvincent)

---

Top Contributors

[![willvincent](https://avatars.githubusercontent.com/u/689891?v=4)](https://github.com/willvincent "willvincent (18 commits)")

###  Code Quality

TestsPHPUnit

Static AnalysisPHPStan

Type Coverage Yes

### Embed Badge

![Health badge](/badges/willvincent-splaytree/health.svg)

```
[![Health](https://phpackages.com/badges/willvincent-splaytree/health.svg)](https://phpackages.com/packages/willvincent-splaytree)
```

###  Alternatives

[benjaminhirsch/nova-slug-field

A Laravel Nova field to generate a slugs.

1401.1M11](/packages/benjaminhirsch-nova-slug-field)[touskar/php-socket-io-event-emitter

2612.9k](/packages/touskar-php-socket-io-event-emitter)[wordpress/ai-provider-for-google

AI Provider for Google for the PHP AI Client SDK. Works as both a Composer package and WordPress plugin.

131.2k](/packages/wordpress-ai-provider-for-google)

PHPackages © 2026

[Directory](/)[Categories](/categories)[Trending](/trending)[Changelog](/changelog)[Analyze](/analyze)