`
Coco_young
  • 浏览: 125720 次
  • 性别: Icon_minigender_1
  • 来自: 湖南长沙
社区版块
存档分类
最新评论

SplayTree实现_简化版

 
阅读更多

(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详细解释

    ### SplayTree(伸展树)详细解释 #### 基本概念 SplayTree,又称伸展树,是一种自调整的二叉搜索树。它虽然不像其他平衡二叉搜索树那样严格限制树的形状,但通过一种叫做伸展的操作,在访问节点后将其提升到根节点...

    splay tree C# code 伸展树的C#代码实现

    伸展树(Splay Tree)是一种自调整的二叉搜索树数据结构,它通过操作将最近访问的元素移动到树的根部,从而优化查找、插入和删除等操作的平均性能。C#语言中的伸展树实现涉及了对二叉树节点的操作、旋转算法以及对树...

    splaytree.zip

    展树(Splay Tree)是一种二叉搜索树,它能在O(log n)内完成插入、查找和删除操作。它由Daniel Sleator和Robert Tarjan创造。它的优势在于不需要记录用于平衡树的冗余信息。在伸展树上的一般操作都基于伸展操作。

    伸展树(Splay tree)图解与实现(2020.10.22).pdf

    ### 伸展树(Splay Tree)概述 伸展树(Splay Tree)是一种自调整的二叉搜索树,由Daniel Sleator和Robert Tarjan在1985年提出。其核心思想是在每次访问节点后,通过一系列的旋转操作将被访问的节点调整到树根的位置...

    Algorithm-splay_tree.zip

    在"Algorithm-splay_tree.zip"的压缩包内,"splay_tree-master"可能包含一个Splay Tree的实现,包括源代码、示例、测试用例等,供学习和参考。研究这些内容可以帮助深入理解Splay Tree的工作原理以及如何在实际应用...

    erl-splay-tree:Erlang中的splay-tree实现

    **Erlang中的Splay Tree实现** Erlang是一种功能强大的并发编程语言,以其轻量级进程、消息传递和容错能力而闻名。在Erlang中实现数据结构可以帮助优化性能,特别是在处理大量数据时。Splay Tree是一种自调整的二叉...

    top_down_splay_tree

    top_down splay_tree 伸展树

    Splay Tree

    伸展数的主要难点:展开函数的实现。 基本操作插入、删除、查找都和展开函数相关。 插入:在根处按要插入的元素展开树,如果树中已经存在此节点,则此节点在展开后就是根;如果不存在节点,根处的元素是比欲插入节点...

    splay_tree_map.cr:这是Splay Tree的Crystal实现。 这是一种半平衡的二叉搜索树,易于自我优化,因此访问最多的项最快。

    此实现提供了类似哈希的界面,并且提供了Splay树中通常不存在的几个功能-有效删除通常访问最少的项,并提供额外的快速搜索选项。叶修剪由于八字树倾向于将自身与最常访问的元素一起组织到树的根部,因此最不频繁...

    BTree、AVLTree、RBTree、BinarySearchTree和SPlayTree的C++源码实现

    我们涉及到了五种特定的树型数据结构,它们是BTree(B树)、AVLTree(AVL树)、RBTree(红黑树)、BinarySearchTree(二叉搜索树)以及SPlayTree(自旋搜索树),并且这些数据结构的C++源码实现被包含在一个压缩包内...

    BinaryTree_BinarySearchTree_AVLTree

    在二叉树的基础上,二叉查找树(Binary Search Tree,BST)是一种特殊的二叉树,其每个节点的值都大于其左子树中的任何节点的值,并小于其右子树中的任何节点的值。这种性质使得二叉查找树在查找特定值时具有较高的...

    SplayTree:展开树的简单实现。 所有函数都具有与 STL 映射函数类似的调用

    游戏树展开树的简单实现。 所有函数都具有与 STL 映射函数类似的调用。细节此实现是出于教育目的。 对该库进行了基本测试。 如果您发现错误,请报告它,我会尝试修复它。特征C++11 组件前向迭代器和 const_iterator ...

    Splay_Trees_Semestrovka

    在"Splay_Trees_Semestrovka"项目中,可能包含了以下内容: 1. `SplayTree`类的实现,包含插入、删除、查找等方法。 2. 旋转函数,如`zig()`, `zag()`, `zigZag()`, `zagZag()`,用于将节点上移至根部。 3. 测试...

    splay-tree:快速的splay-tree数据结构

    快速八叉树 :(非递归)和简单(&lt;1000行代码)实现是直接从Wikipedia改编而成的,使用与相同的API来针对其他树运行基准测试。 该树基于D.Sleator自上而下的展开...S splaytree import SplayTree from 'splaytree'

    伸展树(Splay Tree)

    ### 伸展树(Splay Tree)详解 #### 一、伸展树简介 **伸展树**(Splay Tree)是一种特殊的二叉搜索树(Binary Search Tree),它能够在平均情况下达到 O(log n) 的时间复杂度,对于插入、查找和删除操作均适用。...

    splay_tree:Rust的基于Splay树的集合(例如,地图,集合,堆)库

    splay_tree splay_tree提供基于自上而下的splay树的数据结构,例如map,set和heap。 扩展树是一种自我调整的二进制搜索树,具有最近访问的元素可以快速再次访问的附加属性。 它在O(log n)摊销时间内执行基本操作,...

    splay-trees_c:展开树实现的集合,可用于用户应用程序编程。 用C写

    展开树实现的集合,可用于用户应用程序编程。 用C编写,需要GNU C库。 由于splay树是一种特殊的二进制搜索树,因此该存储库中的工作源自我的其他工作 。 Splay树不考虑平衡,而是将树的根替换为最新的修改后的节点...

    node-splay-tree:展开树实现

    在JavaScript编程环境中,`node-splay-tree`库提供了一个用于创建和操作展开树的实现。 展开树的核心思想是**Splay操作**,它包括三种基本操作:**旋转**(zig,zag,zig-zag,zig-zig),**插入**和**删除**。这三...

    yandex_tree_3.rar_tree

    Yandex_tree_3.rar_tree 文件可能包含了关于这个算法的具体实现或相关测试数据。 最低共同祖先问题指的是,在一棵树中找到两个指定节点的最近公共祖先。这个祖先节点应该满足两个条件:一是它位于两个节点的路径上...

Global site tag (gtag.js) - Google Analytics