局部性(Locality)：刚被访问过的数据，极有可能很快再次被访问
逐层伸展：节点v一旦被访问，随即转移至根
自上而上，逐层单旋(zig, v->parent; zag, v->parent)，直至v最终被推送至根
最坏情况：旋转次数呈周期性算术级数演变，每一周期累计Ω(n2)，分摊Ω(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)时间内完成
仍无法保证单次最坏情况出现，不适用于对效率敏感的场合
网友评论