PHP 实现跳表

跳表（Skip List）是一种用于有序元素集合的数据结构，支持快速的插入、删除和搜索操作。它通过多层链表来实现 O(log n) 的平均时间复杂度。

下面是一个简单的 PHP 实现跳表的示例，包括基本的插入、搜索和删除功能。

跳表节点类

首先，我们需要定义一个跳表节点类。

class SkipListNode {
    public $value;
    public $forward; // 指向下一个节点的数组

    public function __construct($value, $level) {
        $this->value = $value;
        $this->forward = array_fill(0, $level + 1, null); // 创建一个包含 null 的数组
    }
}

跳表类

接下来，我们定义跳表类，包含插入、搜索和删除的方法。

class SkipList {
    private $maxLevel;
    private $header;
    private $level;

    public function __construct($maxLevel) {
        $this->maxLevel = $maxLevel;
        $this->level = 0;
        $this->header = new SkipListNode(null, $maxLevel); // 创建头节点
    }

    // 随机生成节点的层级
    private function randomLevel() {
        $level = 0;
        while (mt_rand(0, 1) && $level < $this->maxLevel) {
            $level++;
        }
        return $level;
    }

    // 插入新值
    public function insert($value) {
        $update = array_fill(0, $this->maxLevel + 1, null);
        $current = $this->header;

        // 从最高层开始查找
        for ($i = $this->level; $i >= 0; $i--) {
            while ($current->forward[$i] !== null && $current->forward[$i]->value < $value) {
                $current = $current->forward[$i];
            }
            $update[$i] = $current; // 记录前驱节点
        }

        // 移动到下一层
        $current = $current->forward[0];

        // 如果当前值不存在，插入新节点
        if ($current === null || $current->value !== $value) {
            $newLevel = $this->randomLevel();
            
            if ($newLevel > $this->level) {
                for ($i = $this->level + 1; $i <= $newLevel; $i++) {
                    $update[$i] = $this->header;
                }
                $this->level = $newLevel;
            }

            $newNode = new SkipListNode($value, $newLevel);
            for ($i = 0; $i <= $newLevel; $i++) {
                $newNode->forward[$i] = $update[$i]->forward[$i];
                $update[$i]->forward[$i] = $newNode;
            }
        }
    }

    // 搜索值
    public function search($value) {
        $current = $this->header;

        for ($i = $this->level; $i >= 0; $i--) {
            while ($current->forward[$i] !== null && $current->forward[$i]->value < $value) {
                $current = $current->forward[$i];
            }
        }

        $current = $current->forward[0];

        return $current !== null && $current->value === $value; // 返回是否找到
    }

    // 删除值
    public function delete($value) {
        $update = array_fill(0, $this->maxLevel + 1, null);
        $current = $this->header;

        for ($i = $this->level; $i >= 0; $i--) {
            while ($current->forward[$i] !== null && $current->forward[$i]->value < $value) {
                $current = $current->forward[$i];
            }
            $update[$i] = $current; // 记录前驱节点
        }

        $current = $current->forward[0];

        if ($current !== null && $current->value === $value) {
            for ($i = 0; $i <= $this->level; $i++) {
                if ($update[$i]->forward[$i] !== $current) {
                    break;
                }
                $update[$i]->forward[$i] = $current->forward[$i];
            }

            // 更新层级
            while ($this->level > 0 && $this->header->forward[$this->level] === null) {
                $this->level--;
            }
        }
    }
}

使用示例

以下是如何使用跳表的示例：

$skipList = new SkipList(3); // 创建一个跳表，最大层数为 3
$skipList->insert(3);
$skipList->insert(6);
$skipList->insert(7);
$skipList->insert(9);
$skipList->insert(12);
$skipList->insert(19);
$skipList->insert(17);
$skipList->insert(26);
$skipList->insert(21);
$skipList->insert(25);

echo "Searching for 19: " . ($skipList->search(19) ? "Found" : "Not Found") . "\n";
$skipList->delete(19);
echo "Searching for 19 after deletion: " . ($skipList->search(19) ? "Found" : "Not Found") . "\n";