Skip List

Каждый узел получает случайную "высоту" при вставке: подбрасывается монета (или генерируется случайное число), и пока выпадает "орёл" (с вероятностью p, обычно 0.5), высота узла увеличивается на 1 — в среднем высота узла равна 1/(1-p), геометрическое распределение. Узел присутствует на всех уровнях от 0 до своей высоты. Поиск начинается с самого верхнего уровня головного узла и движется вправо, пока следующий узел на этом уровне не превышает искомое значение — тогда поиск спускается на уровень ниже и продолжает оттуда. Инвариант: на уровне i в среднем остаётся n·p^i узлов — уровни становятся экспоненциально более разреженными, что и даёт логарифмическую высоту всей структуры (число уровней ~ log_{1/p}(n)) при линейном ожидаемом числе шагов на уровень.Every node gets a random "height" on insertion: a coin is flipped (or a random number generated), and as long as it comes up "heads" (with probability p, usually 0.5), the node's height grows by 1 — a node's average height is 1/(1-p), a geometric distribution. A node is present at every level from 0 up to its height. Search starts at the head node's topmost level and moves right as long as the next node at that level doesn't exceed the target value — then it drops down a level and continues from there. Invariant: level i has, on average, n·p^i nodes remaining — levels become exponentially sparser, which is exactly what gives the structure its logarithmic height (number of levels ~ log_{1/p}(n)) with a linear expected number of steps per level.

struct Node {
    int val;
    std::vector<Node*> next;  // next[i] — указатель на уровне i// next[i] — pointer at level i
};

bool search(Node* head, int level, int val) {
    Node* cur = head;
    for (int i = level; i >= 0; --i) {
        while (cur->next[i] && cur->next[i]->val < val)
            cur = cur->next[i];               // двигаться направо на текущем уровне// move right at the current level
    }                                          // затем неявно спуститься на уровень ниже// then implicitly drop a level
    cur = cur->next[0];
    return cur && cur->val == val;
}

int random_level() {                        // геометрическое распределение// geometric distribution
    int lvl = 0;
    while ((double)rand() / RAND_MAX < 0.5 && lvl < MAX_LEVEL) ++lvl;
    return lvl;
}

Узлы расположены на нескольких уровнях (высота каждого — результат случайного подбрасывания монеты при вставке). Жёлтая подсветка — путь поиска: движение вправо, затем вниз при перескоке цели.Nodes sit at several levels (each one's height is the result of a random coin flip on insertion). Yellow highlights the search path: moving right, then dropping down on overshooting the target.

Высота структуры (число уровней) — случайная величина, определяемая максимальной высотой среди всех вставленных узлов. Ожидаемая максимальная высота среди n независимых геометрических случайных величин — Θ(log n), что и даёт ожидаемую O(log n) сложность поиска. Но теоретически (с исчезающе малой, но ненулевой вероятностью) все n узлов могут получить высоту 0 — тогда структура вырождается в обычный связный список, и поиск деградирует до O(n). Это принципиально отличает skip list от детерминированно сбалансированных деревьев (2.3.2, AVL/Red-Black) — там O(log n) гарантирован структурными инвариантами, а не вероятностью; skip list — сознательный компромисс простоты реализации против абсолютной гарантии.The structure's height (number of levels) is a random variable, determined by the maximum height among all inserted nodes. The expected maximum height among n independent geometric random variables is Θ(log n), giving the expected O(log n) search complexity. But theoretically (with vanishingly small but nonzero probability) all n nodes could get height 0 — the structure would then degenerate into an ordinary linked list, and search would degrade to O(n). This is what fundamentally distinguishes skip lists from deterministically balanced trees (2.3.2, AVL/red-black) — there O(log n) is guaranteed by structural invariants, not probability; a skip list is a deliberate trade-off of implementation simplicity against an absolute guarantee.