8.1 伸展树

局部性(Locality)：刚被访问过的数据，极有可能很快再次被访问
逐层伸展：节点v一旦被访问，随即转移至根
自上而上，逐层单旋(zig, v->parent; zag, v->parent)，直至v最终被推送至根
最坏情况：旋转次数呈周期性算术级数演变，每一周期累计Ω(n²)，分摊Ω(n)
双层伸展：向上追溯两层，反复考察三代g = parent(p), p = parent(v), v，根据其相对位置，经两次旋转使得v上升两层，成为子树根
zig-zag / zag-zig，与AVL树双旋完全等效，与逐层伸展一致
zig-zig / zag-zag，一旦访问坏节点，对应路径长度将随即减半（折叠效果），最坏情况不致持续发生，单次伸展操作分摊O(logn)
zig / zag，此时必有parent(v) == root(T)，且每轮调整中至多（在最后）出现一次该情况

接口

template <typename T> class Splay: public BST<T> { // 由BST派生
protected:
    BinNodePosi(T) splay(BinNodePosi(T) v); // 将v伸展至根
public:
    BinNodePosi(T) & search(const T & e); // 查找重写
    BinNodePosi(T) insert(const T & e); // 插入重写
    bool remove(const T & e); // 删除重写
}

伸展算法

template <typename T> BinNodePosi(T)::splay(BinNodePosi(T) v) {
    if (!v)
        return NULL;
    BinNodePosi(T) p;
    BinNodePosi(T) g;
    while ((p = v->parent) && (g = p->parent)) { // 自下而上，反复双层伸展
        BinNodePosi(T) gg = g->parent;
        if (IsLChild(*v)) {
            if (IsLChild(*p)) { // zig-zig
                attachAsLChild(g, p->rc);
                attachAsLChild(p, v->rc);
                attachAsRChild(p, g);
                attachAsRChild(v, p);
            } else { // zig-zag
                attachAsLChild(p, v->rc);
                attachAsRChild(g, v->lc);
                attachAsLChild(v, g);
                attachAsRChild(v, p);
            }
        } else {
            if (IsRChild(*p)) { // zag-zag
                attachAsRChild(g, p->lc);
                attachAsRChild(p, v->lc);
                attachAsLChild(p, g);
                attachAsLChild(v, p);
            } else { // zag-zig
                attachAsRChild(p, v->lc);
                attachAsLChild(g, v->rc);
                attachAsRChild(v, g);
                attachAsLChild(v, p)
            }
        }
        if (!gg)
            v->parent = NULL;
        else
            (g == gg->lc) ? attachAsLChild(gg, v) : attachAsRChild(gg, v);
        updateHeight(g);
        updateHeight(p);
        updateHeight(v);
    } // 双层伸展结束时必有g == NULL，但p可能非空
    if (p = v->parent) {
        /* 若p为根，则只需再单旋至多一次 */
    }
    v->parent = NULL;
    return v;
}

查找算法

template <typename T> BinNodePosi(T) & Splay<T>::search(const T & e) {
    BinNodePosi(T) p = searchIn(_root, e, _hot=NULL); // 调用标准BST内部接口定位目标节点
    _root = splay(p ? p : _hot); // 无论成功与否，最后被访问的节点将伸展至根
    return _root; // 总是返回根节点
} // 伸展树查找操作与常规BST::search()不同，可能改变树的拓扑结构，不属于静态操作

插入算法

template <typename T> BinNodePosi(T) Splay<T>::insert(const T & e) {
    if (!_root) { // 处理原树为空的退化情况
        _size++;
        return _root = new BinNode<T>(e);
    }
    if (e == search(e)->data) // 确认目标节点不存在
        return _root;
    _size++;
    BinNodePosi(T) t = _root; // 创建新节点
    if (_root->data < e) { // 插入新根节点，以t与t->rChild为左右子节点
        t->parent = _root = new BinNode<T>(e, NULL, t, t->rChild);
        if (HasRChild(*t)) {
            t->rChild->parent = _root;
            t->rChild = NULL;
        }
    } else { // 插入新根节点，以t->lChild与t为左右子节点
        t->parent = _root = new BinNode<T>(e, NULL, t->lChild, t);
        if (HasLChild(*t)) {
            t->lChild->parent = _root;
            t->lChild = NULL;
        }
    }
    updateHeightAbove(t); // 更新高度
    return _root; // 新节点必然位于树根，返回
}

删除算法

template <typename T> bool Splay<T>::remove(const T& e) {
    if (!_root || (e != search(e)->data))
        return false; // 若树为空或目标不存在，则无法删除
    BinNodePosi(T) w = _root; // 经search()后节点e已被伸展至树根
    if (!HasLChild(*_root)) { // 若无左子树，则直接删除
        _root = _root->rChild;
        if (_root)
            _root->parent = NULL;
    } else if (!HasRChild(*_root)) { // 若无右子树，则直接删除
        _root = _root->lChild;
        if (_root)
            _root->parent = NULL;
    } else { // 若左右子树同时存在
        BinNodePosi(T) lTree = _root->lChild;
        lTree->parent = NULL;
        _root->lChild = NULL; // �暂时删除左子树
        _root = _root->rChild;
        _root->parent = NULL; // 保留右子树
        search(w->data); // 以原树根为目标进行查找（必失败），至此右子树中最小节点必伸展至根，且因无相同节点，左子树必空
        _root->lChild = lTree;
        lTree->parent = _root; // 左子树接回原位
    }
    release(w->data);
    release(w);
    _size--; // 释放节点，更新规模
    if (_root)
        updateHeight(_root); // 若树非空，则更新树根高度
    return true;
}

伸展树无需记录节点高度或平衡因子，编程实现简单易行，优于AVL树
分摊复杂度O(logn)，与AVL树相当
局部性强，缓存命中率极高时(k << n << m)，效率可以更高，任何连续的m次查找，可在O(mlogk + nlogn)时间内完成
仍无法保证单次最坏情况出现，不适用于对效率敏感的场合