您当前位置：首页 > php开源 > php教程 > 伸展树 - 二叉搜索树的扩展2

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

来源：程序员人生发布时间：2015-05-08 08:28:08 阅读次数：3053次

- 舒展树的介绍
- 舒展树的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

生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
程序员人生

------分隔线----------------------------

上一篇 Microsoft Build 2015

下一篇 日志收集系统Flume调研笔记第1篇 - Flume简介

分享到:

------分隔线----------------------------

为码而活

积分：4237

15粉丝

7关注

栏目热点