伸展树

局部性：刚被访问过的数据，极有可能很快再次被访问。（如BST）

对此，考察列表结构。在列表中，相邻的元素通过引用确立前驱和后继关系，对任意一个元素的访问效率主要取决于它在序列中的秩。秩越小，访问效率越高，为了提高多次查找的访问效率，可以考虑将刚刚接受访问的元素移动到序列的最前端，提高访问效率。希望借助局部性对BST的访问效率做进一步的优化，参照对列表做出的技巧，将在某一段时间内经常要访问到的元素通过某种方式，尽可能的移送到更加接近树根的位置，尽可能降低他们的深度。

逐层伸展

节点v一旦被访问，随即将其转移至树根，具体操作方式为zig和zag，将节点v和其父亲节点p在高度上互换，多次进行旋转操作，使得节点v最终抵达树根节点。

但一层一层进行伸展，在最坏的情况下：

树退化为一个列表，此时逐层伸展需要的累计时间是\(\Omega(n^{2})\)，因此需要改进方法。

双层伸展

向上追溯两层，反复考察祖孙三代，根据相应的位置，经过两次旋转，使得v一次上升两层，成为子树根。

对于zig-zag和zag-zig而言，和逐层伸展没有区别，但在处理zig-zig和zag-zag时，颠倒上升的次序将彻底改变整体的结构。

具有路径折叠效果：一旦访问最深的那个节点，对应路径的长度随即减半。相当于对坏节点有修复的作用，使得最坏的情况不至于持续发生，按照当前策略，单趟伸展操作所需要的时间不会超过\(O(logn)\)。

伸展树接口

template <typename T>
class Splay:public BST<T>{
    protected:
        BinNodePosi(T) splay(BinNodePosi(T) v);  // 将v伸展至v
    public:                                      
        BinNodePosi(T) & search(const T & e);    // 查找重写，查找会引起整树的结构调整
        BinNodePosi(T) insert(const T & e);      // 插入重写
        bool remove(const T & e);                // 删除重写
}

与AVL树不同，需要重写search接口，因为在伸展树中，它会导致树中节点之间拓扑关系的变化。splay是保护类型接口。

伸展算法

template <typename T> BinNodePosi(T) Splay<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 */
            }else{
                /* zig-zag */
            }
        }else{
            if(isRChild(*p)){
                /* zag-zag */
            }else{
                /* zag-zig */
            }
        }
        
        if(!gg) v->parent = NULL;     // 若无曾祖父，则现在的v为树根
        else{                         // 否则，gg此后以v为左或右孩子
            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;
}

四种情况的分别处理： 1. zig-zig 类似于3+4重构，只需考虑最后的构造而忽略过程。

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
        attachAsRChild(p, v->lc);
        attachAsLChild(g, v->rc);
        attachAsRChild(v, g);
        attachAsLChild(v, p);
    }
}

zag-zag和zag-zig情况类似于上面。

查找

template <typename T> BinNodePosi(T) & Splay<T>::search(const T & e){   
    // 标准BST内部接口定位目标节点
    BinNodePosi(T) p = searchIn(_root, e, _hot = NULL);
    // 无论成功与否，最后被访问的节点都将伸展至根
    _root = spaly(p ? p : _hot);
    return _root;
}

无论是成功或者失败，都会在树根处获得一个相等或者近似的节点，这种处理手法的原理正是为了充分利用我们此前介绍的局部性。既然在其内部需要调用splay算法调整树的拓扑结构，所以对于伸展树而言，search接口不再是一个静态的操作，这也是伸展树区别于其他同类BBST的最本质特点。

插入

按照直观的思维，调用BST标准的插入算法，然后再按照伸展树的规则，将新节点伸展至树根的位置。这种实现方法在这里显得过于迂回曲折，因为无论如何在真正实施插入操作之前，已经调用过一次search接口，而刚刚业已重写过的search接口实际上已经集成了一个splay操作。也就是说，即便查找可能失败，根节点也必然是_hot节点。新的节点本来就应该作为_hot的左或右孩子接入树中，因此进行一下操作：

调用重写后的search接口，查找失败，记录失败前最终的节点t，即_hot
集成在search接口内部的splay操作将_hot推送到树根位置
将此时的树拆分为两部分，引入节点v，将t及其后代作为v的左子树，从t分离出来的右子树作为v的右子树

删除

同样的，按照直观的思维，首先按照BST的标准删除算法实施删除，再按照伸展树的约定，将与之临近的节点比如_hot伸展到树根的位置，但是在此时，也依然显得有些迂回。因为如果在删除操作之前的search操作是成功的，那么在查找之后，待删除的目标节点必然已经被推送到了树根的位置，因此可以随即就在树根的位置附近完成删除操作。具体过程为：

调用重写后的search接口，定位待删除节点
查找成功，但删除节点被伸展到树根
释放树根节点
重新组合两棵子树。如在右子树中找到最小节点，也就是右子树的树根节点的直接后继，因为它虽然是右子树最下的节点，但它比左子树的节点都大。将左子树作为这个节点的左子树连接上去。

伸展树总结

优点：

相对于AVL树，伸展树无需记录节点高度或平衡因子，编程简单易行，其分摊复杂度\(O(logn)\)和AVL相当。
局部性强，缓存命中率极高时\((k << n << m)\)，效率更高。其中m为操作次数，n为数据集数量，k为访问数据的数量。此时的效率可以自适应达到\(O(logk)\)。

缺点：

不能杜绝单次最坏的情况，不适用于对效率敏感的场合
复杂度分析较为复杂

B-树

与二叉查找树类似，B树也是用来存放一组具有关键码的词条的数据结构。它有两个特点： 1. 每个节点未必只有两个分叉 2. 所有底层节点的深度都完全一致