伸展树 – 二叉搜索树的扩展2

目录

    • 舒展树的介绍
    • 舒展树的C实现
      • 1 节点定义
      • 2 旋转
      • 3 舒展树的舒展
      • 4 搜索
      • 4 舒展树的插入和删除
    • 全部代码和参考资料

1. 舒展树的介绍

舒展树(splay tree)是1种搜索2叉树,它能在O(log n)内完成插入、查找和删除操作。
(1)舒展树满足搜索2叉树的性质,左子节点小于根节点,右子节点大于等于根节点。
(2)舒展树独有特点:当某个节点被访问时,舒展树会通过旋转使该节点成为树的根。

舒展树的动身点是这样的:斟酌到局部性原理(刚被访问的内容下次更大的可能仍会被访问)和28原则(80%的时间只会访问20%的节点),为了使全部查找时间更小,被查找频率高的节点应当常常处于靠近根的位置。
因而提出以下方案:在每次查找以后对树进行重构,把查找到的节点移到离树根更近些。舒展树应运而生,它是1种自调剂情势的2叉搜索树,它会沿着从某个节点到树根的路径,通过1系列的旋转把这个节点搬到树根上去。
因此相对“2叉搜索树”和“AVL树”,对舒展树重点关注如何旋转的

2. 舒展树的C实现

以下舒展树的实现思想来源于2叉搜索树的根插法(先插入节点到叶子,然后递归旋转到根),我们将查找到的节点旋转到根,等价于将被查找节点插入到根部:

2.1 节点定义

typedef SplayTreeNode* SplayTree;
struct SplayTreeNode {
Item key;
SplayTree left;
SplayTree right;
};

舒展树不需要记录额外甚么值(如AVL的高度)来保护树的信息,节省了内存。

2.2 旋转

引入两种基本的旋转:左旋和右旋
当被查找节点在根节点的左子树上时,以根为轴,右旋,将该节点提升到根上

//右旋--k2是根,k1是k2的左子树,将k1旋转成根 -- 以k2为原点向右旋
SplayTree rotR(SplayTree k2)
{
SplayTree k1 = k2->left;
k2->left = k1->right;
k1->right = k2;
return k1;
}
  • 当被查找节点在根节点的右子树上时,以根为轴,左旋,将该节点提升到根上
//左旋---k2是根,k1是k2的右子树,(k1的右子树非空)将k1旋转成根 -- 以k2为原点向左旋
SplayTree rotL(SplayTree k2)
{
SplayTree k1 = k2->right;
k2->right = k1->left;
k1->left = k2;
return k1;
}

2.3 舒展树的舒展


<注>该算法实现没有经过严格的验证,自创;
如有疑问可参考经典算法:
舒展树(1)之 图文解析 和 C语言的实现:http://www.cnblogs.com/skywang12345/p/3604238.html

设被查找节点为 x , 当查找到 x 的先驱节点时:
(1) x 在当前根的左边,那末右旋,将和 x 接近的节点向上提升1步;
(2) x 在当前根的右边,那末左旋,将和 x 接近的节点向上提升1步;
(3) x 的值等于当前根的值,查找结束,在上述两步递归进程中完成旋转;
先驱节点不存在时,查找结束。

递归实现进程是自底向上的,当查找节点命中后,以它的父节点为轴旋转,提升查找节点为根;向上递归,在根与查找节点的路径每步都旋转1次,直至原树根。

//舒展进程:将key对应的节点舒展到根上,并返回根节点
SplayTree Splay(SplayTree tree, Item key)
{
if (tree == NULL)
return tree;
if (key == tree->key) //命中
return tree;
if (key < tree->key) { //左边
if (tree->left == NULL)
return tree;
tree->left = Splay(tree->left, key);
tree = rotR(tree);
} else { //右边
if (tree->right == NULL)
return tree;
tree->right = Splay(tree->right, key);
tree = rotL(tree);
}
return tree;
}

2.4 搜索

SplayTree SplayTreeSearch(SplayTree tree, Item key)
{

if (tree == NULL || tree->key == key)
return tree;
if (key < tree->key)
return SplayTreeSearch(tree->left, key);
else
return SplayTreeSearch(tree->right, key);
}

2.4 舒展树的插入和删除

(1)插入:和搜索2叉树的插入相同,省略

(2)删除: 删除舒展树中键值为key的节点。
先在舒展树中查找键值为key的节点:如果没找到,则直接返回;如果找到的话则将该节点旋转成根节点,然后在删除该节点,然后将该节点的两个子树连接到1起(根节点选用和key邻近的节点);

/*
*删除舒展树中键值为key的节点
*参数说明:
* tree: 根节点
* key: 待删除节点的键值
*返回:
* 根节点
*/

SplayTree SplayTreeDelete(SplayTree tree, Item key)
{
SplayTree x = NULL;
if (tree == NULL)
return tree;
tree = Splay(tree, key);
if (tree == NULL)
return tree;
if (tree->left != NULL) {
//将根的左边,邻近key的节点旋转成根
x = Splay(tree->left, key);
x->right = tree->right;
} else {
//tree->left == NULL
x = tree->right;
}
delete tree;
return x;
}

3. 全部代码和参考资料

#include <stdio.h>
#include <stdlib.h>
#define MAX(A, B) ((A > B) ? A : B)
typedef int Item;
typedef struct SplayTreeNode SplayTreeNode;
typedef SplayTreeNode* SplayTree;
struct SplayTreeNode {
Item key;
SplayTree left;
SplayTree right;
};
static int g_error = 0; //毛病代码
SplayTree NewNode(Item key, SplayTree left, SplayTree right)
{
SplayTree x = (SplayTree)malloc(sizeof(*x));
if (x == NULL) {
g_error = 1;
exit(-1);
}
x->key = key;
x->left = left;
x->right = right;
return x;
}

SplayTree SplayTreeInit()
{
return NewNode(10, NULL, NULL);
}

//左旋---k2是根,k1是k2的右子树,(k1的右子树非空)将k1旋转成根 -- 以k2为原点向左旋
SplayTree rotL(SplayTree k2)
{
SplayTree k1 = k2->right;
k2->right = k1->left;
k1->left = k2;
return k1;
}

//右旋--k2是根,k1是k2的左子树,将k1旋转成根 -- 以k2为原点向右旋
SplayTree rotR(SplayTree k2)
{
SplayTree k1 = k2->left;
k2->left = k1->right;
k1->right = k2;
return k1;
}

SplayTree Splay(SplayTree tree, Item key)
{
if (tree == NULL)
return tree;
if (key == tree->key)
return tree;
if (key < tree->key) { //左边
if (tree->left == NULL)
return tree;
tree->left = Splay(tree->left, key);
tree = rotR(tree);
} else { //右边
if (tree->right == NULL)
return tree;
tree->right = Splay(tree->right, key);
tree = rotL(tree);
}
return tree;
}
SplayTree SplayTreeSearch(SplayTree tree, Item key)
{

if (tree == NULL || tree->key == key)
return tree;
if (key < tree->key)
return SplayTreeSearch(tree->left, key);
else
return SplayTreeSearch(tree->right, key);
}

SplayTree SplayTreeInsert(SplayTree tree, Item key)
{
if (tree == NULL)
return NewNode(key, NULL, NULL);
if(key < tree->key)
tree->left = SplayTreeInsert(tree->left, key);
else
tree->right = SplayTreeInsert(tree->right, key);
return tree;
}

void traversal(SplayTree tree)
{
if (tree == NULL) {
printf("NIL ");
return;
}
printf("%d ", tree->key);
traversal(tree->left);
traversal(tree->right);
return;
}

SplayTree SplayTreeDelete(SplayTree tree, Item key)
{
SplayTree x = NULL;
if (tree == NULL)
return tree;
tree = Splay(tree, key);
if (tree == NULL)
return tree;
if (tree->left != NULL) {
x = Splay(tree->left, key);
x->right = tree->right;
} else {
//tree->left == NULL
x = tree->right;
}
delete tree;
return x;
}

int main()
{
SplayTree splay_tree = NULL;
//for (int i = 0; i < 10; i++) {
// int key = rand()%100;
// splay_tree = SplayTreeInsert(splay_tree, key);
// printf("%d ", key);
//}
splay_tree = SplayTreeInsert(splay_tree, 1);
splay_tree = SplayTreeInsert(splay_tree, 5);
splay_tree = SplayTreeInsert(splay_tree, 4);
splay_tree = SplayTreeInsert(splay_tree, 2);
splay_tree = SplayTreeInsert(splay_tree, 6);

printf("
Traversal
"
);
traversal(splay_tree);
splay_tree = Splay(splay_tree, 6);
splay_tree = SplayTreeDelete(splay_tree, 4);
printf("
Deleted Traversal
"
);
traversal(splay_tree);
getchar();
}

参考资料:
舒展树-维基百科:https://zh.wikipedia.org/wiki/%E4%BC%B8%E5%B1%95%E6%A0%91
舒展树(1)之 图文解析 和 C语言的实现:http://www.cnblogs.com/skywang12345/p/3604238.html
2叉搜索树的实现:http://blog.csdn.net/quzhongxin/article/details/45038399

波比源码 – 精品源码模版分享 | www.bobi11.com
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,请使用WINRAR解压,如遇到无法解压的请联系管理员!

波比源码 » 伸展树 – 二叉搜索树的扩展2

发表评论

Hi, 如果你对这款模板有疑问,可以跟我联系哦!

联系站长
赞助VIP 享更多特权,建议使用 QQ 登录
喜欢我嘛?喜欢就按“ctrl+D”收藏我吧!♡