Splay Tree 是二叉查找树的一种，它与平衡二叉树、红黑树不同的是，Splay Tree从不强制地保持自身的平衡，每当查找到某个节点n的时候，在返回节点n的同时，Splay Tree会将节点n旋转到树根的位置，这样就使得Splay Tree天生有着一种类似缓存的能力，因为每次被查找到的节点都会被搬到树根的位置，所以当80%的情况下我们需要查找的元素都是某个固定的节点，或者是一部分特定的节点时，那么在很多时候，查找的效率会是O(1)的效率！当然如果查找的节点是很均匀地分布在不同的地方时，Splay Tree的性能就会变得很差了，但Splay Tree的期望的时间复杂度还是O（nlogn）的。
下图是对伸展树查询节点1和删除节点6的结果，利用我的伸展树来实现
头文件————————————————————————————
#ifndef _SPLAY_TREE_H_
#define _SPLAY_TREE_H_ #include <iostream>
#include <iomanip>
#include <cassert>
#include <stack> typedef struct splay_tree_node_t
{
int data;
struct splay_tree_node_t *left;
struct splay_tree_node_t *right;
} splay_tree_node, *position, *splay_tree; void print_splay_tree(splay_tree st, int depth, int ctrl);//ctrl:0=root 1=left 2=right
position find_max(splay_tree st);
void insert_splay_tree(splay_tree *pst, int x);
void delete_splay_tree(splay_tree *pst, int x);
int find_splay_tree(splay_tree *pst, int x); splay_tree rotate3(position child, position parent, position grand_parent, int *type);
splay_tree rotate2(position child, position parent); inline void fcn(int type, position cur, position parent, position grand_parent);
#endif 源文件——————————————————————————————
#include "./SplayTree.h" splay_tree rotate3(position child, position parent, position grand_parent, int *type)
{
assert(child != NULL && parent != NULL && grand_parent != NULL); if(parent->left == child && grand_parent->left == parent)//child, parent, grand_parent一字形东北方向 0
{
*type = ;
grand_parent->left = parent->right;
parent->right = grand_parent; parent->left = child->right;
child->right = parent;
}
else if(parent->right == child && grand_parent->right == parent)//child, parent, grand_parent一字形西北方向 1
{
*type = ;
grand_parent->right = parent->left;
parent->left = grand_parent; parent->right = child->left;
child->left = parent;
}
else if(parent->right == child && grand_parent->left == parent)//child, parent, grand_parent之字形<
{
*type = ;
grand_parent->left = child->right;
parent->right = child->left;
child->left = parent;
child->right = grand_parent;
}
else if(parent->left == child && grand_parent->right == parent)//child, parent, grand_parent之字形>
{
*type = ;
grand_parent->right = child->left;
parent->left = child->right;
child->right = parent;
child->left - grand_parent;
} return child;
}
splay_tree rotate2(position child, position parent)
{
assert(child != NULL && parent != NULL);
if(parent->left == child)
{
parent->left = child->right;
child->right = parent;
}
else//parent->right == child
{
parent->right = child->left;
child->left = parent;
}
return child;
} position find_max(splay_tree st)
{
while(NULL != st && NULL != st->right)
st = st->right;
return st;
} void print_splay_tree(splay_tree st, int depth, int ctrl)
{
if(NULL != st)
{
std::cout<<std::setw(depth);
if( == ctrl)
std::cout<<"root:";
else if( == ctrl)
std::cout<<"left";
else if( == ctrl)
std::cout<<"right";
std::cout<<st->data<<std::endl;
print_splay_tree(st->left, depth+, );
print_splay_tree(st->right, depth+, );
}
}
void insert_splay_tree(splay_tree *pst, int x)
{
if(NULL == *pst)
{
position tmp = new splay_tree_node;
if(NULL == tmp)
return ;
tmp->data = x;
tmp->left = tmp->right = NULL;
*pst = tmp;
}
else if(x < (*pst)->data)
insert_splay_tree(&((*pst)->left), x);
else if(x > (*pst)->data)
insert_splay_tree(&((*pst)->right), x);
else
return ;
}
void delete_splay_tree(splay_tree *pst, int x)
{
assert(NULL != pst);
int res = find_splay_tree(pst, x);
if(res == )//not found
return ;
//此时root指向的就是要删除的节点，因为find_splay_tree操作将节点推至向根
position root = *pst;
splay_tree splay_left = root->left;
splay_tree splay_right = root->right;
position tmp = find_max(splay_left);
if(NULL == tmp)//无左子树
*pst = splay_right;//将右子树为新树
else
{
find_splay_tree(&splay_left, tmp->data);
splay_left->right = splay_right;//将右子树为左子树的新右子树
*pst = splay_left;//将左子树为新树
}
}
int find_splay_tree(splay_tree *pst, int x)
{
assert(NULL != pst);
position cur = *pst;
std::stack<position> s; while(cur != NULL && cur->data != x)//沿着查找路径将树节点以此压入栈中
{
if(x < cur->data)
{
s.push(cur);
cur = cur->left;
}
else
{
s.push(cur);
cur = cur->right;
}
} if(NULL == cur)//not found
return false; position parent, grand_parent;
int type = -;//0一字形东北方向; 1一字形西北方向; 2之字形<; 3之字形<
//每次取父节点和祖父节点和当前节点进行伸展调节
while(s.size() >= )
{
parent = s.top();
s.pop();
//fcn判断伸展的类型以便重新调整原来的树指针，调整好了才可以再次伸展
fcn(type, cur, parent, grand_parent);
grand_parent = s.top();
s.pop();
cur = rotate3(cur, parent, grand_parent, &type);//after rotate, cur is the new "root"
}
if(s.empty())
*pst = cur;
else //rotate cur and the old root
{
parent = s.top();
s.pop();
fcn(type, cur, parent, grand_parent);
//此时只对cur和根节点进行伸展，完成后find_splay_tree函数结束
*pst = rotate2(cur, parent);
} return true;
} //fcn判断伸展的类型以便重新调整原来的树指针，调整好了才可以再次伸展
inline void fcn(int type, position cur, position parent, position grand_parent)
{
if(type == )
{
if(grand_parent == parent->left)
parent->left = cur;
else if(grand_parent == parent->right)
parent->right = cur;
}
else if(type == )
{
if(grand_parent == parent->left)
parent->left = cur;
else if(grand_parent == parent->right)
parent->right = cur;
}
else if(type == )
{
if(grand_parent == parent->left)
parent->left = cur;
else if(grand_parent == parent->right)
parent->right = cur;
}
else if(type == )
{
if(grand_parent == parent->left)
parent->left = cur;
else if(grand_parent == parent->right)
parent->right = cur;
}
}