admin 管理员组文章数量: 1086866
8.1 伸展树
一、伸展树
- 引入伸展树的最初动机：具体来说，也就是试图利用所谓的局部性
- 局部性(Locality):刚被访问过的数据，极有可能很快地再次被访问，这一现象在信息处理过程中数见不鲜
- 局部性的BST描述：刚刚访问过的节点，极有可能很快地再次被访问。下一将要访问的节点，极有可能就在刚被访问过的节点的附近
- 连续的m次查找(m >> n = |BST|), 采用AVL共需O(mlogn)时间
- 仿照自适应链表，利用局部性，能否更快？
- 逐层伸展
- 节点v一旦被访问，随即转移至树根（通过左旋和右旋使之上升）
- 自下而上，逐层单旋
- zig( v->parent)
- zag(v->parent)
- 直到v最终被推送至树根
- 根据最坏情况，对该策略进行改进
- 双层伸展
- 构思的精髓：向上追溯两层，而不是一层
- 反复考察祖孙三代：g = parent§, p = parent(v), v
- 根据它们的相对位置，经两次旋转，使得v上升两层，成为（子）树根
- zig - zag / zag - zig
- 与AVL树双旋完全等效，与逐层伸展别无二致
- 与AVL树双旋完全等效，与逐层伸展别无二致
- zig - zig / zag - zag
- 折叠效果：一旦访问坏节点，对应发路径长度随即减半，最坏情况不致持续发生
- 单趟伸展操作，分摊O(logn)时间
- 实现：伸展树接口
template<typename T>
class Splay:public BST<T>{//由BST派生protected:BinNodePosi(T) splay(BinNodePosi(T) v);//将v伸展至根public://伸展树的查找也会引起整树的结构调整，故search()也需要重写BinNodePosi(T) & search(const T & e);//查找（重写）BinNodePosi(T) insert(const T & e);//插入（重写）bool remove(const T& e);//删除（重写）
};
- 实现：伸展算法
template <typename T> 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;//每轮之后，v都将以原曾祖父为父if(IsLChild(*v))if(LsLChild(*p)){/*zig - zig*/}else{/* zig - zag*/}else if(IsRChild(*p)){/*zag - zag*/}else{/*zag - zig*/}//每经过一次双层伸展，我们都需要将局部这棵新的子树接入到原树中对应 的位置，并更新相应节点的高度信息if(!gg) v->parent = NULL;//若无曾祖父gg，则v现即为树根；否则，gg此后应为以v为左或右孩子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;//伸展完成，v抵达树根
}
//使用直接拼接的方式实现左旋或右旋
if(IsLChild(*v))if(IsLChild(*p)){attachAsLChild(g, p->rc);//p的右孩子当作g的左孩子attachAsLChild(p, v->rc);attachAsRChild(p, g);attachAsRChild(v, p);}else{/*zig - zag*/}
elseif(IsRChild(*p)){/*zag - zag*/}else{/*zag - zag*/}
- 查找接口：伸展树的查找操作，与常规BST::search()不同，很可能会改变树的拓扑结构，不再属于静态操作
template <typename T> BinNodePosi(T) & Splay<T>::search(const T& e){//调用标准BST的内部接口定位目标节点BinNodePosi(T) p = searchIn(_root, e, _hot = NULL);//无论成功与否，最后被访问的节点都将伸展至根_root = splay(p ? p : _hot);//总是返回根节点return _root;
}
- 插入算法
- 重写后的Splay::search()已集成了splay（）操作，查找失败后，_hot即是根节点
- 直接在根节点附近插入目标节点
- 删除算法
- Splay::search()查找（成功）之后，目标节点即是树根
- 在树根附近完成目标节点的删除
- 找到右子树中的最小者，将其伸展到右子树根节点的位置，同时连接左子树，就能获得删除目标节点后的伸展树
- 综合评价
- 无需记录节点高度或平衡因子；编程实现简单易行——优于AVL树；分摊复杂度O(logn)——与AVL树相当
- 局部性强，缓存命中率极高时（即k << n << m)
- 效率可以更高——自适应的O(logk)
- 任何连续的m次查找，都可在O(mlogk + nlogn)时间内完成
- 仍不能保证单次最坏情况的出现，不适应于对效率敏感的场合
本文标签： 81 伸展树
版权声明：本文标题：8.1 伸展树 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.roclinux.cn/b/1688023876a170043.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论