(1)
template<class DataType>
class SplayTree{
#define MAXN 1000010
private:
int ch[MAXN][2],pre[MAXN],pool[MAXN];
DataType key[MAXN];
int top,root,tot;
int malloc(DataType dt){
int x;
if(top!=0) x = pool[--top];
else x = ++tot;
key[x] = dt;
return x;
}
void free(int x){
ch[x][0] = ch[x][1] = pre[x] = 0;
pool[top++] = x;
}
void rotate(int x,int f){//f == 0 为zag f == 1 为zig
int y = pre[x]; int z = pre[y];
ch[y][!f] = ch[x][f];
if(ch[y][!f]) pre[ch[y][!f]] = y;
ch[x][f] = y;
pre[y] = x;
if(z) ch[z][0]==y?ch[z][0] = x:ch[z][1] = x;
pre[x] = z;
}
void splay(int x,int &rt){
int y,z;
while(pre[x]){
y = pre[x]; z = pre[y];
if(!z){
rotate(x,ch[y][0]==x);
}else{
int f = ch[z][0]==y;
if(ch[y][!f]==x){
rotate(y,f); rotate(x,f);
}else{
rotate(x,!f); rotate(x,f);
}
}
}
rt = x;
}
int find_help(DataType k,int rt){
if(!rt) return 0;
if(k==key[rt])return rt;
return k<key[rt]?find_help(k,ch[rt][0]):find_help(k,ch[rt][1]);
}
int findmax_help(int rt){
int x = rt;
while(x&&ch[x][1]) x = ch[x][1];
return x;
}
int findmin_help(int rt){
int x = rt;
while(x&&ch[x][0]) x = ch[x][0];
return x;
}
int join(int rt1,int rt2){
if(!rt1) return rt2;
if(!rt2) return rt1;
int x = findmax_help(rt1);
splay(x,rt1);
ch[rt1][1] = rt2;
pre[rt2] = rt1;
return rt1;
}
int split(DataType k,int &rt,int &rt1,int &rt2){
int x = find_help(k,rt);
if(!x) return 0;
splay(x,rt);
rt1 = ch[rt][0]?ch[rt][0]:0;
pre[rt1] = 0;
rt2 = ch[rt][1]?ch[rt][1]:0;
pre[rt2] = 0;
return rt;
}
int insert_help(DataType k,int &rt,int father){
if(!rt){
rt = malloc(k);
pre[rt] = father;
return rt;
}
return insert_help(k,ch[rt][!(k<key[rt])],rt);
}
public:
void insert(DataType k){
int x = insert_help(k,root,0);
splay(x,root);
}
void remove(DataType k){
int rt1,rt2;
int x = split(k,root,rt1,rt2);
if(!x) return;
free(x);
root = join(rt1,rt2);
}
int findmax(DataType &k){
int x = findmax_help(root);
if(x) splay(x,root);
k = key[x];
return x;
}
int findmin(DataType &k){
int x = findmin_help(root);
if(x) splay(x,root);
k = key[x];
return x;
}
};
(2)
template<class DataType>
class SplayTree{
#define MAXN 1000010
private:
int ch[MAXN][2],pre[MAXN],pool[MAXN];
DataType key[MAXN];
int top,root,tot;
int malloc(DataType dt){
int x;
if(top!=0) x = pool[--top];
else x = ++tot;
key[x] = dt;
return x;
}
void free(int x){
ch[x][0] = ch[x][1] = pre[x] = 0;
pool[top++] = x;
}
void rotate(int x,int f){//f == 0 为zag f == 1 为zig
int y = pre[x]; int z = pre[y];
ch[y][!f] = ch[x][f];
if(ch[y][!f]) pre[ch[y][!f]] = y;
ch[x][f] = y;
pre[y] = x;
if(z) ch[z][0]==y?ch[z][0] = x:ch[z][1] = x;
pre[x] = z;
}
void splay(int x,int &rt){
int y,z;
while(pre[x]){
y = pre[x]; z = pre[y];
if(!z){
rotate(x,ch[y][0]==x);
}else{
int f = ch[z][0]==y;
if(ch[y][!f]==x){
rotate(y,f); rotate(x,f);
}else{
rotate(x,!f); rotate(x,f);
}
}
}
rt = x;
}
int find_help(DataType k,int rt){
if(!rt) return 0;
if(k==key[rt])return rt;
return k<key[rt]?find_help(k,ch[rt][0]):find_help(k,ch[rt][1]);
}
int findmax_help(int rt){
int x = rt;
while(x&&ch[x][1]) x = ch[x][1];
return x;
}
int findmin_help(int rt){
int x = rt;
while(x&&ch[x][0]) x = ch[x][0];
return x;
}
int insert_help(DataType k,int &rt,int father){
if(!rt){
rt = malloc(k);
pre[rt] = father;
return rt;
}
return insert_help(k,ch[rt][!(k<key[rt])],rt);
}
void remove_help(DataType k,int &rt,int father){
if(!rt) return;
if(k==key[rt]){
if(ch[rt][0]==0||ch[rt][1]==0){
int x = rt;
rt = ch[rt][0]+ch[rt][1];
if(rt){ pre[rt] = father; splay(rt,root); }
free(x);
return;
}
int x = findmin_help(ch[rt][1]);
key[rt] = key[x];
remove_help(key[rt],ch[rt][1],rt);
splay(rt,root);
}
remove_help(k,ch[rt][!(k<key[rt])],rt);
}
public:
void insert(DataType k){
int x = insert_help(k,root,0);
splay(x,root);
}
void remove(DataType k){
remove_help(k,root,0);
}
int findmax(DataType &k){
int x = findmax_help(root);
if(x) splay(x,root);
k = key[x];
return x;
}
int findmin(DataType &k){
int x = findmin_help(root);
if(x) splay(x,root);
k = key[x];
return x;
}
};
分享到:
相关推荐
SplayTree优化版C源代码,带有完整的解释,其实就是置顶向下的Splay tree
splay tree C# code 伸展树的C#代码实现 我看到没有C#实现版本,所以就把java代码转化成C#实现了一把
SplayTree详细解释
展树(Splay Tree)是一种二叉搜索树,它能在O(log n)内完成插入、查找和删除操作。它由Daniel Sleator和Robert Tarjan创造。它的优势在于不需要记录用于平衡树的冗余信息。在伸展树上的一般操作都基于伸展操作。
伸展树(Splay tree)图解与实现(2020.10.22).pdf
top_down splay_tree 伸展树
伸展数的主要难点:展开函数的实现。 基本操作插入、删除、查找都和展开函数相关。 插入:在根处按要插入的元素展开树,如果树中已经存在此节点,则此节点在展开后就是根;如果不存在节点,根处的元素是比欲插入节点...
erl-splay-tree:Erlang中的splay-tree实现
此实现提供了类似哈希的界面,并且提供了Splay树中通常不存在的几个功能-有效删除通常访问最少的项,并提供额外的快速搜索选项。叶修剪由于八字树倾向于将自身与最常访问的元素一起组织到树的根部,因此最不频繁...
Splay_Trees_Semestrovka
该代码包括了二叉树、二叉查找树、平衡树的Java实现代码
游戏树展开树的简单实现。 所有函数都具有与 STL 映射函数类似的调用。细节此实现是出于教育目的。 对该库进行了基本测试。 如果您发现错误,请报告它,我会尝试修复它。特征C++11 组件前向迭代器和 const_iterator ...
伸展树(Splay Tree)是一种二叉排序树,它能在O(log n)内完成插入、查找和删除操作。它由Daniel Sleator和Robert Tarjan创造。它的优势在于不需要记录用于平衡树的冗余信息。在伸展树上的一般操作都基于伸展操作。
快速八叉树 :(非递归)和简单(<1000行代码)实现是直接从Wikipedia改编而成的,使用与相同的API来针对其他树运行基准测试。 该树基于D.Sleator自上而下的展开...S splaytree import SplayTree from 'splaytree'
红黑树、平衡二叉树、B树、二叉搜索树和SPlay树的C++源码实现,带工程
Algorithm-splay_tree.zip,具有摊销访问权的自平衡二叉树,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
splay_tree splay_tree提供基于自上而下的splay树的数据结构,例如map,set和heap。 扩展树是一种自我调整的二进制搜索树,具有最近访问的元素可以快速再次访问的附加属性。 它在O(log n)摊销时间内执行基本操作,...
一个简单的 AVL树、splay树、以及二叉搜索树的代码实现 也可在我的github仓库中下载: https://github.com/yunwei37/myClassNotes
展开树实现的集合,可用于用户应用程序编程。 用C编写,需要GNU C库。 由于splay树是一种特殊的二进制搜索树,因此该存储库中的工作源自我的其他工作 。 Splay树不考虑平衡,而是将树的根替换为最新的修改后的节点...
Splay树及其应用_朱全民.ppt