README

Splay-tree: 快速(非递归)且 简单(小于 1000 行代码)的实现直接来自这个 GitHub 仓库.

此树基于 D.Sleator 的 自顶向下 splay 算法。它支持

• 分割、合并
• 更新键
• 将项目批量加载到空树或非空树中
• 插入重复或非重复项
• 无 splay 的查找

安装

composer require locr-company/splay-tree

<?php

use Locr\Lib\SplayTree\SplayTree;

$tree = new SplayTree();

API

• new SplayTree(callable $comparator = null)，其中 $comparator 是可选的比较函数
• $tree->insert(int|array $key, mixed $data = null): Node - 插入项目，允许重复键
• $tree->add(int|float $key, mixed $data = null): Node - 如果不存在则插入项目
• $tree->remove(int|float $key): void - 移除项目
• $tree->find(int $key): ?Node - 通过其键返回节点
• $tree->findStatic(int $key): ?Node - 通过其键返回节点（不重新平衡树）
• $tree->at(int $index): ?Node - 通过其键的排序顺序返回节点
• $tree->contains(int $key): bool - 是否存在具有给定键的节点
• $tree->forEach(callable $visitor): self 顺序遍历
• $tree->keys(): array - 返回按顺序排列的键数组
• $tree->values(): array - 返回按顺序排列的数据字段数组
• $tree->range(int $low, int $high, callable $fn): self - 按顺序遍历键的范围。如果访问者函数返回非零值，则停止。
• $tree->pop(): array - 移除最小节点
• $tree->min(): int|float|array|null - 返回最小键
• $tree->max(): int|float|array|null - 返回最大键
• $tree->minNode(?Node $t = null): ?Node - 返回具有最小键的节点
• $tree->maxNode(?Node $t = null): ?Node - 返回具有最大键的节点
• $tree->previousNode(Node $d): ?Node - 前驱节点
• $tree->nextNode(Node $d): ?Node - 后继节点
• $tree->load(array $keys, array $values = [], bool $presort = false): self - 批量加载项目。它期望值和键是有序的，但如果 presort 是 true，它将使用比较器对键和值进行排序（就地排序，您的数组将被修改）。

比较器

function(int|float $a, int|float $b): int - 两个键之间的比较器函数，它返回

• 0 如果键相等
• <0 如果 a < b
• >0 如果 a > b

比较器函数非常重要，如果在错误的情况下，您可能会得到一个错误构建的树，或者无法检索您的项目。测试您的 comparator(a, b) 和 comparator(b, a) 的返回值对于确保其正确性至关重要，否则您可能会遇到难以预测和捕捉的漏洞。

重复键

• insert() 方法允许重复键。这在某些应用程序中可能很有用（例如：2D中的重叠点）。
• add() 方法不允许重复键 - 如果键已存在于树中，则不会创建新节点

示例

<?php

use Locr\Lib\SplayTree\SplayTree;

$t = new SplayTree();
$t->insert(5);
$t->insert(-10);
$t->insert(0);
$t->insert(33);
$t->insert(2);

print_r($t->keys());
/**
 * Array(
 *  [0] => -10  
 *  [1] => 0  
 *  [2] => 2  
 *  [3] => 5  
 *  [4] => 33
 * )
 */
print $t->size;  // 5
print $t->min(); // -10
print $t->max(); // 33

$t->remove(0);
print $t->size;   // 4

自定义比较器（逆序排序）

<?php

use Locr\Lib\SplayTree\SplayTree;

$t = new SplayTree(function ($a, $b) {
    return $b - $a;
});
$t->insert(5);
$t->insert(-10);
$t->insert(0);
$t->insert(33);
$t->insert(2);

print_r($t->keys());
/**
 * Array
 *(
 *  [0] => 33
 *  [1] => 5
 *  [2] => 2
 *  [3] => 0
 *  [4] => -10
 *)
 */

批量插入

<?php

use Locr\Lib\SplayTree\SplayTree;

$t = new SplayTree();
$t->load([3, 2, -10, 20], ['C', 'B', 'A', 'D']);
print_r($t->keys());
/**
 * Array
 *(
 *  [0] => 3
 *  [1] => 2
 *  [2] => -10
 *  [3] => 20
 *)
 */
print_r($t->values());
/**
 * Array
 *(
 *  [0] => C
 *  [1] => B
 *  [2] => A
 *  [3] => D
 *)
 */

开发

composer install