Splay ДеревоTree

Splay — это операция "поднять узел x к корню", выполняемая парами ротаций, а не по одной, — именно попарность и делает амортизированный анализ работающим (одиночные ротации в этой роли дают лишь O(n) амортизированно, не O(log n)). Три случая на каждом шаге, в зависимости от положения x относительно родителя p и деда g: zig — p является корнем (p не имеет родителя): одна ротация x вокруг p, применяется только в самом последнем шаге; zig-zig — x и p оба левые дети (или оба правые): сначала ротация p вокруг g, затем x вокруг нового p — сначала "выпрямляем" линию, а не поднимаем x напрямую; zig-zag — x и p на разных сторонах: ротация x вокруг p, затем x (уже поднятого) вокруг g — тот же паттерн, что в LR/RL-случаях AVL, но применяемый на каждом доступе, а не только при нарушении инварианта.A splay is the operation "lift node x to the root," performed in pairs of rotations rather than one at a time — it's precisely this pairing that makes the amortized analysis work (single rotations in this role only give O(n) amortized, not O(log n)). Three cases at each step, depending on x's position relative to its parent p and grandparent g: zig — p is the root (p has no parent): a single rotation of x around p, applied only on the very last step; zig-zig — x and p are both left children (or both right): first rotate p around g, then x around the new p — "straighten" the line first rather than lifting x directly; zig-zag — x and p are on different sides: rotate x around p, then x (now raised) around g — the same pattern as AVL's LR/RL cases, but applied on every access, not just when the invariant is violated.

Практический эффект: если один и тот же узел (или соседние по значению узлы) запрашиваются повторно, второй и последующие запросы почти мгновенны, потому что узел уже у корня или рядом с ним — это и называется temporal locality (временная локальность). Плата за это — дерево не гарантирует хорошую форму для узлов, к которым давно не обращались: они постепенно опускаются вглубь, и доступ к ним снова может занять до O(n) в худшем единичном случае (хотя не в амортизированном).The practical effect: if the same node (or nearby-valued nodes) is requested repeatedly, the second and later requests are nearly instant, because the node is already at or near the root — this is called temporal locality. The price is that the tree gives no shape guarantee for nodes that haven't been touched in a while: they gradually sink deeper, and accessing them again can take up to O(n) in the single worst case (though not amortized).

struct Node { int key; Node *left=nullptr, *right=nullptr, *parent=nullptr; };

void rotate(Node* x) {                 // поднять x на один уровень относительно родителя// lift x by one level relative to its parent
    Node* p = x->parent; Node* g = p->parent;
    if (p->left == x) { p->left = x->right; if (x->right) x->right->parent = p; x->right = p; }
    else                { p->right = x->left;  if (x->left)  x->left->parent  = p; x->left  = p; }
    p->parent = x; x->parent = g;
    if (g) { if (g->left == p) g->left = x; else g->right = x; }
}

Node* splay(Node* x) {                    // поднять x до корня// lift x all the way to the root
    while (x->parent) {
        Node* p = x->parent; Node* g = p->parent;
        if (!g) { rotate(x); }                                    // zig// zig
        else if ((g->left == p) == (p->left == x)) { rotate(p); rotate(x); }  // zig-zig// zig-zig
        else { rotate(x); rotate(x); }                              // zig-zag// zig-zag
    }
    return x;                                                       // теперь x — корень// x is now the root
}

Node* find(Node* root, int key) {              // поиск завершается splay, даже если ключ не найден// search finishes with a splay, even if the key isn't found
    Node* cur = root; Node* last = root;
    while (cur) {
        last = cur;
        if (key == cur->key) return splay(cur);
        cur = key < cur->key ? cur->left : cur->right;
    }
    return last ? splay(last) : nullptr;         // splay последнего посещённого — стандартная практика// splaying the last node visited is standard practice
}

search(k) сначала спускается к узлу как в обычном BST, затем автоматически проигрывает splay — пары ротаций поднимают узел к корню шаг за шагом. Найденный узел подсвечен на всём протяжении подъёма.search(k) first descends to the node like a plain BST, then auto-plays the splay — pairs of rotations lift the node to the root step by step. The found node stays highlighted throughout the climb.

Классическое доказательство использует метод потенциалов (2.1.1): вводится "потенциал" дерева, зависящий от размеров поддеревьев, и показывается, что амортизированная стоимость одного splay (реальная стоимость минус изменение потенциала) равна O(log n), даже если реальная стоимость этой конкретной операции — O(n). Интуиция проще: узел на глубине d при доступе к нему поднимается к корню, а его прежние соседи по пути в среднем "выигрывают" от произошедших ротаций (их собственная глубина в среднем не увеличивается сильно) — по духу это похоже на "разгон-торможение" из амортизационного анализа динамического массива, только применённое к форме дерева, а не к размеру буфера.The classic proof uses the potential method (2.1.1): a "potential" of the tree is defined based on subtree sizes, and it's shown that the amortized cost of a single splay (actual cost minus the change in potential) is O(log n), even when the actual cost of that specific operation is O(n). The simpler intuition: a node at depth d, when accessed, rises to the root, and its former neighbors along the path benefit on average from the rotations that happened (their own depth doesn't increase much on average) — in spirit this resembles the "accelerate-brake" amortized analysis of a dynamic array, just applied to a tree's shape instead of a buffer's size.