数据结构之高级搜索树-伸展树

伸展树

  • 局部性:刚被访问过的数据,极有可能很快再次被访问。(如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. 所有底层节点的深度都完全一致

Author: NYY
Link: http://yoursite.com/2018/05/14/data_structure/高级搜索树/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.