局部性(Locality)：剛被訪問(wèn)過(guò)的數(shù)據(jù)，極有可能很快再次被訪問(wèn)
逐層伸展：節(jié)點(diǎn)v一旦被訪問(wèn)迎瞧，隨即轉(zhuǎn)移至根
自上而上邓线，逐層單旋(zig, v->parent; zag, v->parent)顽频，直至v最終被推送至根
最壞情況：旋轉(zhuǎn)次數(shù)呈周期性算術(shù)級(jí)數(shù)演變，每一周期累計(jì)Ω(n²)篷帅，分?jǐn)偊?n)
雙層伸展：向上追溯兩層，反復(fù)考察三代g = parent(p), p = parent(v), v拴泌，根據(jù)其相對(duì)位置魏身，經(jīng)兩次旋轉(zhuǎn)使得v上升兩層，成為子樹(shù)根
zig-zag / zag-zig蚪腐，與AVL樹(shù)雙旋完全等效箭昵，與逐層伸展一致
zig-zig / zag-zag，一旦訪問(wèn)壞節(jié)點(diǎn)回季，對(duì)應(yīng)路徑長(zhǎng)度將隨即減半（折疊效果）家制，最壞情況不致持續(xù)發(fā)生，單次伸展操作分?jǐn)侽(logn)
zig / zag泡一，此時(shí)必有parent(v) == root(T)慰丛，且每輪調(diào)整中至多（在最后）出現(xiàn)一次該情況

接口

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

伸展算法

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)) { // 自下而上，反復(fù)雙層伸展
        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);
    } // 雙層伸展結(jié)束時(shí)必有g(shù) == 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); // 調(diào)用標(biāo)準(zhǔn)BST內(nèi)部接口定位目標(biāo)節(jié)點(diǎn)
    _root = splay(p ? p : _hot); // 無(wú)論成功與否，最后被訪問(wèn)的節(jié)點(diǎn)將伸展至根
    return _root; // 總是返回根節(jié)點(diǎn)
} // 伸展樹(shù)查找操作與常規(guī)BST::search()不同粥烁，可能改變樹(shù)的拓?fù)浣Y(jié)構(gòu)贤笆，不屬于靜態(tài)操作

插入算法

template <typename T> BinNodePosi(T) Splay<T>::insert(const T & e) {
    if (!_root) { // 處理原樹(shù)為空的退化情況
        _size++;
        return _root = new BinNode<T>(e);
    }
    if (e == search(e)->data) // 確認(rèn)目標(biāo)節(jié)點(diǎn)不存在
        return _root;
    _size++;
    BinNodePosi(T) t = _root; // 創(chuàng)建新節(jié)點(diǎn)
    if (_root->data < e) { // 插入新根節(jié)點(diǎn)，以t與t->rChild為左右子節(jié)點(diǎn)
        t->parent = _root = new BinNode<T>(e, NULL, t, t->rChild);
        if (HasRChild(*t)) {
            t->rChild->parent = _root;
            t->rChild = NULL;
        }
    } else { // 插入新根節(jié)點(diǎn)讨阻，以t->lChild與t為左右子節(jié)點(diǎn)
        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; // 新節(jié)點(diǎn)必然位于樹(shù)根芥永，返回
}

刪除算法

template <typename T> bool Splay<T>::remove(const T& e) {
    if (!_root || (e != search(e)->data))
        return false; // 若樹(shù)為空或目標(biāo)不存在，則無(wú)法刪除
    BinNodePosi(T) w = _root; // 經(jīng)search()后節(jié)點(diǎn)e已被伸展至樹(shù)根
    if (!HasLChild(*_root)) { // 若無(wú)左子樹(shù)钝吮，則直接刪除
        _root = _root->rChild;
        if (_root)
            _root->parent = NULL;
    } else if (!HasRChild(*_root)) { // 若無(wú)右子樹(shù)埋涧，則直接刪除
        _root = _root->lChild;
        if (_root)
            _root->parent = NULL;
    } else { // 若左右子樹(shù)同時(shí)存在
        BinNodePosi(T) lTree = _root->lChild;
        lTree->parent = NULL;
        _root->lChild = NULL; // ?暫時(shí)刪除左子樹(shù)
        _root = _root->rChild;
        _root->parent = NULL; // 保留右子樹(shù)
        search(w->data); // 以原樹(shù)根為目標(biāo)進(jìn)行查找（必失敯辶伞），至此右子樹(shù)中最小節(jié)點(diǎn)必伸展至根棘催，且因無(wú)相同節(jié)點(diǎn)劲弦，左子樹(shù)必空
        _root->lChild = lTree;
        lTree->parent = _root; // 左子樹(shù)接回原位
    }
    release(w->data);
    release(w);
    _size--; // 釋放節(jié)點(diǎn)，更新規(guī)模
    if (_root)
        updateHeight(_root); // 若樹(shù)非空醇坝，則更新樹(shù)根高度
    return true;
}

伸展樹(shù)無(wú)需記錄節(jié)點(diǎn)高度或平衡因子邑跪，編程實(shí)現(xiàn)簡(jiǎn)單易行，優(yōu)于AVL樹(shù)
分?jǐn)倧?fù)雜度O(logn)呼猪，與AVL樹(shù)相當(dāng)
局部性強(qiáng)画畅，緩存命中率極高時(shí)(k << n << m)，效率可以更高宋距，任何連續(xù)的m次查找轴踱，可在O(mlogk + nlogn)時(shí)間內(nèi)完成
仍無(wú)法保證單次最壞情況出現(xiàn)，不適用于對(duì)效率敏感的場(chǎng)合