template<class DataType>
class SplayTree{
#define null 0
private:
int MAXSIZE;
int *l,*r,*p,*pool,*depth;
int top,root,tot;
DataType *key;
int malloc(DataType k){
int node;
if(top!=0){
node = pool[--top];
}else{
node = ++tot;
}
key[node] = k;
return node;
}
void free(int node){
l[node] = r[node] = p[node] = null;
pool[top++] = node;
}
void zig(int x){
int fa = p[x];
int ga = p[fa];
l[fa] = r[x];
p[l[fa]] = fa;
r[x] = fa;
p[fa] = x;
if(ga) l[ga]==fa?l[ga] = x:r[ga] = x;
p[x] = ga;
}
void zag(int x){
int fa = p[x];
int ga = p[fa];
r[fa] = l[x];
p[r[fa]] = fa;
l[x] = fa;
p[fa] = x;
if(ga) l[ga]==fa?l[ga] = x:r[ga] = x;
p[x] = ga;
}
/**
伸展到根rt处
**/
void splay(int x,int &rt){
while(p[x]){
int fa = p[x],ga = p[p[x]];
if(ga==null){
l[fa]==x?zig(x):zag(x);
}else{
if(l[ga]==fa){
if(l[fa]==x){
zig(fa);
zig(x);
}else{
zag(x);
zig(x);
}
}else{
if(r[fa]==x){
zag(fa);
zag(x);
}else{
zig(x);
zag(x);
}
}
}
}
rt = x;
}
int find_help(DataType goal,int rt){
if(rt==null) return null;
if(key[rt]==goal)return rt;
return goal<key[rt]?find_help(goal,l[rt]):find_help(goal,r[rt]);
}
//fa = p[rt]
int insert_help(DataType goal,int &rt,int fa){
if(rt==null){
rt = malloc(goal);
p[rt] = fa;//必须得修改新结点的父亲指针
return rt;
}
return goal<key[rt]?insert_help(goal,l[rt],rt):insert_help(goal,r[rt],rt);
}
int findmax_help(int rt){
int node = rt;//考虑空树的情况
while(node!=null&&r[node]!=null) node = r[node];
return node;
}
int findmin_help(int rt){
int node = rt;
while(node!=null&&l[node]!=null) node = l[node];
return node;
}
/**
将rt1 rt2 两颗BST合并成一棵BST
返回新BST的根
**/
int join(int &rt1,int &rt2){
if(rt1==null)return rt2;
if(rt2==null)return rt1;
int node = findmax_help(rt1);
splay(node,rt1); r[rt1] = rt2; p[rt2] = rt1;
return rt1;
}
/**
根据goal将一棵BST分裂成两颗BST
返回goal结点的位置
**/
int split(DataType goal,int &rt,int &rt1,int &rt2){
int node = find_help(goal,rt);
if(node!=null){
splay(node,rt);
rt1 = l[rt];
rt2 = r[rt];
p[rt1] = p[rt2] = null;
l[rt] = r[rt] = null;
}
return node;
}
//更新各结点深度
int refreshDepth(int rt,int dep){
if(rt==null)return 0;
depth[rt] = dep;
int t1 = refreshDepth(l[rt],dep+1);
int t2 = refreshDepth(r[rt],dep+1);
return max(max(t1,t2),dep);
}
public:
SplayTree(int maxsize){
MAXSIZE = maxsize;
depth = new int[MAXSIZE];
l = new int[MAXSIZE]; memset(l,0,sizeof(int)*MAXSIZE);
r = new int[MAXSIZE]; memset(r,0,sizeof(int)*MAXSIZE);
p = new int[MAXSIZE]; memset(p,0,sizeof(int)*MAXSIZE);
pool = new int[MAXSIZE]; memset(pool,0,sizeof(int)*MAXSIZE);
key = new DataType[MAXSIZE]; memset(key,0,sizeof(DataType)*MAXSIZE);
top = root = tot = 0;
}
~SplayTree(){
delete[] depth;
delete[] l;
delete[] r;
delete[] p;
delete[] pool;
delete[] key;
}
int find(DataType goal){
int node = find_help(goal,root);
if(node!=null){
splay(node,root);
return 1;
}
return 0;
}
int findmax(){
int node = findmax_help(root);
if(node!=null) splay(node,root);
return node;
}
int findmin(){
int node = findmin_help(root);
if(node!=null) splay(node,root);
return node;
}
void insert(DataType goal){
int node = insert_help(goal,root,p[root]);
splay(node,root);
}
int remove(DataType goal){
int rt1,rt2;
int node = split(goal,root,rt1,rt2);
if(node!=null){
free(root);
root = join(rt1,rt2);
}
return node;
}
DataType getValue(int node){
return key[node];
}
/*debug 查看树形*/
void bfs(){
int termi = refreshDepth(root,1);
cout<<termi<<endl;
queue<int> Q;
Q.push(root);
int flag = 1,dep = 1,cond = dep;
while(1){
int now = Q.front(); Q.pop();
if(cond==0){
dep++;
flag = flag*2;
cond = flag;
cout<<endl;
}
if(dep>termi)break;
cout<<"["<<key[now]<<"]"; cond--;
Q.push(l[now]);
Q.push(r[now]);
}
}
};
分享到:
相关推荐
**Erlang中的Splay Tree实现** Erlang是一种功能强大的并发编程语言,以其轻量级进程、消息传递和容错能力而闻名。在Erlang中实现数据结构可以帮助优化性能,特别是在处理大量数据时。Splay Tree是一种自调整的二叉...
- 考虑到C#的面向对象特性,可以设计一个`SplayTree`类,包含树的根节点,并提供`Insert`, `Delete`, `Find`等公共方法。 5. **性能分析**:伸展树的平均性能优于普通的二叉搜索树。虽然最坏情况下的性能与普通BST...
### 伸展树(Splay Tree)概述 伸展树(Splay Tree)是一种自调整的二叉搜索树,由Daniel Sleator和Robert Tarjan在1985年提出。其核心思想是在每次访问节点后,通过一系列的旋转操作将被访问的节点调整到树根的位置...
伸展数的主要难点:展开函数的实现。 基本操作插入、删除、查找都和展开函数相关。 插入:在根处按要插入的元素展开树,如果树中已经存在此节点,则此节点在展开后就是根;如果不存在节点,根处的元素是比欲插入节点...
游戏树展开树的简单实现。 所有函数都具有与 STL 映射函数类似的调用。细节此实现是出于教育目的。 对该库进行了基本测试。 如果您发现错误,请报告它,我会尝试修复它。特征C++11 组件前向迭代器和 const_iterator ...
我们涉及到了五种特定的树型数据结构,它们是BTree(B树)、AVLTree(AVL树)、RBTree(红黑树)、BinarySearchTree(二叉搜索树)以及SPlayTree(自旋搜索树),并且这些数据结构的C++源码实现被包含在一个压缩包内...
在"Algorithm-splay_tree.zip"的压缩包内,"splay_tree-master"可能包含一个Splay Tree的实现,包括源代码、示例、测试用例等,供学习和参考。研究这些内容可以帮助深入理解Splay Tree的工作原理以及如何在实际应用...
POJ 3580代码 Splay tree实现
快速八叉树 :(非递归)和简单(<1000行代码)实现是直接从Wikipedia改编而成的,使用与相同的API来针对其他树运行基准测试。 该树基于D.Sleator自上而下的展开...S splaytree import SplayTree from 'splaytree'
### 伸展树(Splay Tree)详解 #### 一、伸展树简介 **伸展树**(Splay Tree)是一种特殊的二叉搜索树(Binary Search Tree),它能够在平均情况下达到 O(log n) 的时间复杂度,对于插入、查找和删除操作均适用。...
在JavaScript编程环境中,`node-splay-tree`库提供了一个用于创建和操作展开树的实现。 展开树的核心思想是**Splay操作**,它包括三种基本操作:**旋转**(zig,zag,zig-zag,zig-zig),**插入**和**删除**。这三...
在描述中提到的“An solution of a problem using Splay Trees”,这表明该压缩包内的内容可能包含一个程序或代码实现,利用Splay Tree的数据结构解决了一个具体的问题。通常,这样的解决方案会包括以下部分: 1. *...
在`splaytree-master`这个压缩包中,我们可以推测它包含了`splaytree`的源代码实现,`SplayTree`是八卦树的一种优化形式,即自旋树。自旋树是一种自调整的树结构,它通过旋转操作使得最近频繁访问的节点更靠近根部,...
给定一个长度为N的序列,每个序列的长度是一个整数。要支持以下三种操作: 将[L,R]这个区间所有数加上V. 将[L,R]这个区间翻转,例如 1234变成 4321 ...能力有限,实现可能有纰漏,也没有用到lazy_tag
此实现提供了类似哈希的界面,并且提供了Splay树中通常不存在的几个功能-有效删除通常访问最少的项,并提供额外的快速搜索选项。叶修剪由于八字树倾向于将自身与最常访问的元素一起组织到树的根部,因此最不频繁...
在二叉树的基础上,二叉查找树(Binary Search Tree,BST)是一种特殊的二叉树,其每个节点的值都大于其左子树中的任何节点的值,并小于其右子树中的任何节点的值。这种性质使得二叉查找树在查找特定值时具有较高的...
在本资源中,我们将探讨几种常见的平衡二叉树实现,包括AVL树、红黑树和SBT(Splay Tree)。 1. AVL树:AVL树是由G. M. Adelson-Velsky和E. M. Landis于1962年提出的,它是第一种自平衡二叉搜索树。AVL树的平衡因子...
这些文件分别对应了哈希表、自旋平衡二叉搜索树(Splay Tree)和哈希集合这三种重要的数据结构。 首先,哈希表(HashMap)是一种基于键值对的数据结构,它的设计原理是通过哈希函数将键映射到数组的特定位置,实现...