扩充的数据结构_深度学习数据扩充怎么知道扩充了多少 - CSDN
精华内容
参与话题
  • 如何扩充数据结构

    千次阅读 2013-09-19 17:54:07
    我们在用数据结构的时候经常找不到适合的,树图堆栈这些根本满足不了我们的需要。有的时候我们不得不去设计一些数据结构,可是那会很麻烦,而且很难。所有我们在设计新的数据结构的...这就是我们要说的数据结构扩充

    如何扩充数据结构

    	我们在用数据结构的时候经常找不到适合的,树图堆栈这些根本满足不了我们的需要。有的时候我们不得不去设计一些数据结构,可是那会很麻烦,而且很难。所有我们在设计新的数据结构的时候经常拿现有的数据结构,然后在上边添加一些自己需要的功能,以便支持我们的新操作。这就是我们要说的数据结构的扩充。
    	如何扩充数据结构?我们由一个例子来引入。

    OS树

    之前我们说过TOPK问题,讲了很多方法,其中有一个就是快速选择QuickSelect可以在O(lgN)的时间内找到N个元素中的第i大的元素。 常规的遍历方法需要O(N)的时间才能在N个无序的序列中找到第i大的元素。这里我们来说一个别的方法,利用数据结构的扩充。 一个二叉排序树可以对N个元素的序列进行排序,可是这并不能在O(lgN)时间内找到第i大的元素。而且还会造成树的高度达到最坏的情况,即便是排序我们也要选择红黑树,不选择二叉查找树。 对于红黑树来说,可以做到很好的排序时间复杂度O(lgN),可是依旧没有办法在O(lgN)的时间内找到第i大的元素。可是如果我们在每个结点加一个域sizesize[X]就是以X为根的RB树的内部结点数目(没有NIL,包括X结点本身)。如果要定义NIL[T]结点的话,则size[NIL[T]]=0. 那么对于一个结点的size域的求解的表达式就有了: size[NIL[T]]=0;  size[X]=size[left[X]]+size[right[X]]+1 不过我们大多数的时候是给NIL[T]做一个特殊标记,这样就不需要分类求了。大多数的时候我们处理边界值都是这么做的,给边界初始化,或者其他的方法,为的就是不用麻烦的去分类处理边界。


    图中黑色结点是黑色,灰色结点代表红色,没有画NIL结点。

    这样的树我们称为顺序统计树(Order Select Tree),接下来将的都是中序遍历是有序的OS树。可以有关键字相同的结点,但是其size域不一定相等。这样的树对于我们寻找第i大的数或者是第i小的元素是很简单的了。我们来看一下,OS-SELECT(x,i)返回一个指向以x为根的OS树中第i小的结点的指针。 OS-SELECT(x, i)  1 r ← size[left[x]]+1  2 if i = r  3  then return x  4 else if i< r  5  then return OS-SELECT(left[x], i) 6 else return OS-SELECT(right[x], i - r)  伪代码中的r就是以x为根的子树中x的秩(从小到大),的意思就是动态序,就是中序遍历的时候x的位置罢了。每一次的递归调用都是下降一层,所以这个OS-SELECT的时间复杂度是O(lgN) 刚才说的一个RB树根结点的秩,那么如何在RB树中求一个任意一个结点的秩呢?一个结点的秩与他在OS树中的位置有关系。我们只知道每个结点的size域,而且每个结点的位置都要和根结点有关系,因为插入结点的时候我们是从根结点开始一路下降到合适的位置的,所以我们要求一个结点的秩就要从该结点开始一路上升到根结点。 假设要在T中求X的秩,如果X是根结点,直接返回size[left[X]]+1就好了。如果X不是根结点,那么首先X的位置要包括以X为根的子树的秩,也即是size[left[X]]+1。如果X结点是其父母P的右孩子,这说明左孩子left和父母P都是小于X的,所以X的秩就要加上size[left[P]]+1,如果是其父母的左孩子,那就什么都不加。这样一路升到根就像是插入的逆过程一样。 OS-RANK(T, x)  1 r ← size[left[x]] + 1  2 y ←  3 while y ≠ root[T]  4  do if y = right[p[y]]  5  then r ← r + size[left[p[y]]] + 1  6  y ← p[y]  7 return r  不过一个OS树是在一个RB树的基础上建立而来的,一个RB树不仅仅只是静态的操作,也会有动态的插入和删除。这些动态的操作会影响OS的新操作OS-SELECTOS-RANK吗?其实我们只要维护好每个结点正确的size域新的操作就不会受到影响。我们来分析一下。 之前我们讲过红黑树的插入和删除,这里的OS树就是多了一个size域而已。对于插入结点X来说,要一路查找下降到合适位置,这其中碰到的所有结点的size域都发生了变化,都要加上size[X],而X本身的size1。这不会使size域不正常,但是需要O(lgN)的额外时间。插入一个结点还要调整红黑树的结点颜色,这会牵涉到旋转,旋转会导致size域发生变化吗?对于插入来说,至多旋转2次而已。旋转会使两个结点的size域失效,可是这没关系,失效的size域可以根据未失效的孩子求出来。

    如果是左旋,仅仅在之前说过的代码中添加两行而已,时间代价O(1)        size[y]=size[x]
    	size[x]=size[left[x]]+size[right[x]]+1
    	删除的话也是从一路查找下降的X的位置,删除之后,一路下降碰到的结点的size域都要减去size[X],代价是O(lgN)。而颜色的调整会发生旋转,这和刚才插入是一样的,不会改变size域。
    	所以来说OS树的动态操作不会改变OS树结点的size域,我们可以很好的维护,那么我们的新操作就不会受到影响。

    扩充的步骤

    说完了OS树,那我们来总结一下,如何对数据结构进行扩充。
    对一种数据结构的扩充过程可分为四个步骤:
    	 1、选择基础数据结构; (选择红黑树)
    	2、确定要在基础数据结构中添加哪些信息; (加入size域)
    	3、验证可用基础数据结构上的基本修改操作来维护这些新添加的信息; (插入和删除可以维护size域)
    	4、设计新的操作。 (OS--SELECTOS--RANK
    	不过这只是一个模式罢了,不是必须遵循的步骤,很多时候都是采用的试探法,这些步骤的顺序都是可以颠倒和并行的。就像刚才OS树就不是按这个步骤来的。这里只是给出一个参考罢了。不要那么的循规蹈矩啊!

    对于在红黑树上的扩充,我们这有一个定理,只要满足,就可以在红黑树上扩充: 定理:设域f对含n个结点的红黑树进行扩充的域,且假设某结点x的域f的内容可以仅用结点xleft[x]right[x]中的信息计算,包括f[left[x]]f[right[x]]。这样,在插入和删除操作中,我们可以在不影响这两个操作O(lgN)渐近性能的情况下,对T的所有结点的f值进行维护。

    区间树

    	既然红黑树很好扩充,那么我们再来扩充一个,区间树。我们假设区间都是闭区间,我们用一个闭区间[t1,t2](t1<=t2)表示一个区间树的元素X。则区间X表示为int[X]t1是低端点,t2是高端点,即low[int[X]]=t1,high[int[x]]=t2.
    	区间树是在红黑树基础上进行扩充得到的支持以区间为元素的动态集合的操作的树。其中每个节点的关键值是区间的左端点(key[int[x]]=low[int[X]])。通过建立这种特定的结构,可是使区间的元素的查找和插入都可以在O(lgn)的时间内完成。
    	这只是第一步选择基础的数据结构红黑树。
    	我们需要的操作是INTERVAL-SEARCH(T,i)给定一个区间i,然后从区间树T中找到一个和i区间重叠的区间返回指针,否则返回NIL。(要注意的是T中可能有很多和i重叠的区间,我们找到一个即返回。)
    首先要明白重叠是什么,重叠有好多种情况,对于区间ii丿。

    图中(a)表示两个区间重叠的情况,其他的(b)(c)表示没有重叠的情况。
    	也即是对于两个区间ij,如果low[i]<=high[j] and low[j]<=high[i],ij就是重叠了,其他情况都不是重叠。
    	这便是第四步,设计新的操作INTERVAL-SEARCH(T,i)	要实现新的操作,这些还不够,我们呢无法求出所要的结果。我们需要在区间树的结点里添加一些域,我们可以添加一个max域,max[x]是以x为根的子树中所有元素的高端点的最大值,这样就可以了。当然添加什么域不是随便就能想出来的,肯定需要好多次的试探,加入max域可以使i区间在和结点区间比较是否重叠的时候选择是进入左子树还是右子树。对于区间树每一个结点Xmaxmax[X]=max(high[int[X]],high[left[X]],high[right[X]])
    	这便是第二步添加域max[x],以x为根的子树中所有元素的高端点的最大值。
    这样一个区间树就可以出来了,途中黑色是黑色,灰色是红色。


    	我们先来实现一下新的操作,刚才说根据max域可以判断出进入哪个子树。如何判断?判断i区间是否和T中元素重叠,从根结点开始一路下降。如果左子树的max值小于low[i],则说明左子树中肯定不存在和i重叠的区间,转到右子树;否则,转到左子树。我们为什么要选择max域代表高端点最大值而不是低端点的最大值呢?因为这是根据重叠的性质来的,如果是低端点的最大值,即便是max<low[i],这说明不了要进入哪个子树中。而如果是高端点的最大值的话,max<low[i],说明肯定在右子树中,即便不在右子树中,也肯定不在左子树中。如果max>=low[i],这说明肯定要进入左子树,因为即便是不在左子树中,肯定也不在右子树。这都是因为左子树的max要小于左子树的max    INTERVAL-SEARCH(T, i)
        1 x ← root[T]
        2 while xNIL[T] and (low[i]>high[int[x]]or low[int[x]]>high[i])
        3      do if left[x]NIL[T] and max[left[x]]>=low[i]
        4             then x ← left[x]
        5         else x ← right[x]
        6 return x
    时间复杂度很明显是O(lgN)
    	如何维护添加的域max,和之前说的OS树是一样的道理,插入X和删除X需要向上升或向下降O(lgN),则max[X]=max(high[int[X]],high[left[X]],high[right[X]])。而旋转和之前也是一样,这里不再说了。
    	这便是第三步,维护结点的域OK,说完了。
    转载请注明出处:http://blog.csdn.net/liangbopirates/article/details/9858563


    展开全文
  • (1)以红黑树作为underlying data structure,在树的每个节点增加一个int域储存该节点的subtree节点个数(包含自身) node_size(x) = node_size(left[x]) + node_size(right[x]) + 1; 设nil节点的node_size返回0;...

    (1)以红黑树作为underlying data structure,在树的每个节点增加一个int域储存该节点的subtree节点个数(包含自身)

    node_size(x) = node_size(left[x]) + node_size(right[x]) + 1;

    设nil节点的node_size返回0;

    typedef struct node{
        int key;    int color;  //Augment field: the number of all nodes in the subtree of current node, including its self
        struct node *left;  struct node *right;  struct node *p;
        int node_size();
    }*pnode, node;
    node sentinel = {0,1,NULL,NULL,NULL};  //初始化列表赋值,initializer_list
    pnode nil= &sentinel;
    
    int node::node_size(){
        if(this != nil)
            return left->node_size()+right->node_size()+1;
        else
            return 0;
    }

    测试:

    void test_RBtree(){
        vector<int> A = {7,3,18,10,22,8,11,26};
        pnode root = nil;
        for(int i = 0; i < A.size(); i++){
            pnode z = (pnode)malloc(sizeof(node));
            z->key = A[i];  z->left = nil;  z->right = nil;
            RB_insert(root, z);
        }
    
        inorder_walk(root);
        cout<<endl;
    
        pnode z = (pnode)malloc(sizeof(node));   z->left = nil;  z->right = nil;  z->key = 15;
        RB_insert(root, z);
        pnode rr = find_root(z);
    
        inorder_walk(rr);
        cout<<endl;
        cout<<rr->node_size()<<endl;
    }

    结果:


    (2)order statistic:OS_select()以及OS_rank:

    int OS_rank(pnode x){
        int r = x->right->node_size();
        while(x == x->p->right)
            x = x->p;
        return x->node_size()-r;
    }
    
    pnode OS_select(pnode root, int rank){
        if(root->node_size() >= rank){
            int r = root->right->node_size();
            if(root->node_size()-r == rank)
                return root;
            if(root->node_size()-r > rank)
                return OS_select(root->left, rank);
            if(root->node_size()-r < rank)
                return OS_select(root->right, rank-root->node_size()+r);
        }
        return nil; //如果给出的rank值超出树的大小,则返回nil指针
    }

    (3)Update subtree sizes when inserting or deleting, 与第(1)种方法不同,在node内直接定义一个int size域,对RB_insert进行修改,使其在插入时就直接修改各个相关节点的size大小。注意rotation操作需要修改size大小,时间复杂度为O(1):just look at children size. (待完成

    展开全文
  • 跳跃表

    不记录元素的秩,是为了维护花销小。
    区间数查找的证明:

    1. 如果搜索走向右边,左边则不能有寻找的区间。
    2. 向左走没找到,向右走也没用。

    跳跃表

    期望时间O(lgn),出现概率极大。
    两个双向链表,一个是全集,另一个是子集,相同的元素之间有连接。子集的模取n,期望搜索时间为2n
    k个双向链表,子集的模取nk,期望搜索时间为knk。取k=lgn,搜索时间为2lgn
    如此每一次子集包含的元素数目是上一级的一半。(理想跳跃表)
    其类似于二叉树。

    插入

    链表插入;子集的插入依赖于概率,一个元素被插入,连续的使用0-1分布得到他是否被连续的提升。
    分析使用回溯分析。

    自组织表

    • 访问元素的花费是从表头到元素的距离
    • L的循序可以通过置换相邻元素进行调整,并且置换操作花费为O(1)

    存在一个操作序列:
    在线算法:依次执行每一个操作,对后续操作是未知的。
    离线算法:提前获知所有操作。

    竞争分析:

    如果一个在线算法A是αcompetitive的,则存在一个常数k使得一个操作序列S有

    CA(S)αCopt(S)+k

    其中opt是最优离线算法。α可能是一个函数式。
    不需要S的概率分布。
    展开全文
  • 算法导论(六)——扩充数据结构的应用   选择数据结构(红黑树);决定附加信息(计算节点子树大小);验证数据结构不受修改操作影响(插入删除后需旋转);在新的结构上进行新的操作   1. 动态有序统计:...

    算法导论(六)——扩充的数据结构的应用

     

    选择数据结构(红黑树);决定附加信息(计算节点子树大小);验证数据结构不受修改操作影响(插入删除后需旋转);在新的结构上进行新的操作

     

    1.    动态有序统计:(SELECT在动态集中返回第i小的数,RANK在有序集中返回排名为i的元素)

    【已知】对于一个无序的集合,能够在O(n)的时间内确定任何的顺序统计量

    【目标】修改红黑树,使得在O(lgn)时间内确定任何的顺序统计量

    ——>顺序统计树: 在每个结点上存储附加信息的一棵红黑树。

    【节点信息】附加属性x.size = x.left.size + x.right.size + 1

    【对子树规模的维护】维护size时间复杂度:O(1)。所以插入、删除,包括维护size属性,都只需要O(lgn)时间。

     

    OS-SELECT( x, i ) // 过程返回一个指针,指向以x为根的子树中包含第i小关键字的结点 

        r= x.left.size + 1 

       if i == r 

           return x 

       else if i < r 

          return OS-SELECT( x.left, i ) 

       else 

           return OS-SELECT( x.right, i - r ) 

    OS-RANK( T, x ) // 过程返回T中序遍历对象的线性序中x的位置 

        r= x.left.size + 1 

        y= x 

       while y != T.root 

            if y == y.p.right 

               r += y.p.left.size + 1 

           y = y.p 

       return r 

     

    2.    区间树(找到与目标区间重合的区间)

    【节点信息】每个结点的关键字为区间int(低端点x.int.low)。附加信息包含一个值x.max,它是以x为根的子树中,所有区间的端点的最大值。

    【对子树规模的维护】一次旋转后,更新max属性只要O(1)的时间;所以插入和删除的运行时间为O(lgn)

    参考:

    http://blog.csdn.net/loveprogram_1/article/details/32318211

    http://blog.csdn.net/lu597203933/article/details/43459035

    展开全文
  • 动态有序统计 主要操作: OS-Select(i)//返回动态集中第i小的...新增数据: 在每个结点中保存其子树的结点个数。 size[x]=size[left[x]]+size[right[x]]+1 size[nil]=0 处理nil的通用技巧: 标记法,给空结...
  • 扩充数据结构

    2019-12-26 13:57:57
    编程中常常会遇到已有的数据结构无法解决问题,这时不要急着创建新的数据结构,可以在已有数据结构的基础上添加新的字段。本节在红黑树这一基础数据结构上进行扩展,得出两个重要的应用—动态顺序统计和区间树。 一...
  • 算法导论-数据结构的扩张

    千次阅读 2012-11-25 20:38:23
    首先给出数据结构的扩张的四个步骤: 1)选择基础的数据结构; 2)确定要在基础数据结构中添加哪些信息; 3)验证可以用基础数据结构上的基本修改操作来维护这些新添加的信息; 4)设计新的操作。 算法导论...
  • 本节课主要讲了如何构造自己想要的数据结构,或者扩充已有数据结构的功能,以实现想要的特定功能 比如设计一个动态结构...构造自己需要的扩充数据结构的基本流程 1.选择一个基本的数据结构 例如红黑树 2.决定要
  • Java数据结构和算法(一)——开篇

    万次阅读 多人点赞 2019-09-18 12:31:42
    看的是——《Java数据结构和算法》一书,作者Robert Lafore。 目录 1)数据结构算法有什么用? 2)技术与通俗 3)驱动力学习 1)数据结构算法有什么用? 当你用着java里面的容器类很爽的时候,你有没有想过,怎么...
  • JAVA常用数据结构

    万次阅读 多人点赞 2018-07-30 14:12:59
    所有JAVA开发工程师在日常开发工作中,离不开JAVA常用数据结构,比如List、Map、Set等。对其内部原理的了解能够更好地理解这些数据结构的适用场合,避免使用不当引发的诡异问题。本文将对这些常用的JAVA中的数据结构...
  • 数据结构——小白入门篇

    万次阅读 多人点赞 2018-07-14 19:35:07
    数据结构——小白入门篇浅谈学习心得- 我为什么想要学数据结构?****在计算机界有这样一个万能公式:数据结构 + 算法 = 程序。****在如今这计算机引领风骚的时代,不学数据结构,你凭什么想要做时代的弄潮儿;所以我...
  • HashSet数据结构原理

    万次阅读 2018-09-06 00:26:08
    hashSet数据结构原理 从源码中发现HashSet源码内部维护一个HashMap变量,来看看add方法: add添加的元素存放在HashMap中,其他方法结合源码分析,参考HashMap HashMap数据结构分析链接: 特性 HashSet为...
  • 数据结构(python)

    千次阅读 2019-01-28 21:53:25
    一、数据结构 student_list = [ {'name': 'zs', 'age': 12}, {'name': 'ls', 'age': 23} ] student_dic = { {'zs'}:{'sx',23}, {'ls'}:{'ls',24} } 数据结构也就是存储数据的结构,我们对数据组织的方式就...
  • 数据结构(c语言版)代码

    千次阅读 2019-07-07 03:26:27
    文档中源码及测试数据存放目录:数据结构\▲课本算法实现\▲01 绪论 概述 第一章作为绪论,主要介绍了数据结构与算法中的一些基本概念和术语。对于这些概念术语,我个人不推崇死记硬背,记住了当然好,记不住也...
  • 数据增强与数据扩充

    千次阅读 2019-02-26 15:06:02
    数据扩充方法 在图像上很常用: 方法有:左右翻转、随机裁剪、旋转、平移、噪声扰动、亮度对比度变换等许多简单高效的方法; 其作用是增大数据集且提高泛化效果,随手百度都有很多讲解。 在文本上的使用: 方法...
  • 数据结构算法有什么用? 当你用着java里面的容器类很爽的时候,你有没有想过,怎么ArrayList就像一个无限扩充的数组,也好像链表之类的。 好用吗?好用,这就是数据结构的用处,只不过你在不知不觉中使用了。只...
  •  1)数据结构:数据模型中的数据结构主要描述数据的类型、内容、性质以及数据间的联系等。数据结构是数据模型的基础,数据操作和约束都建立在数据结构上。不同的数据结构具有不同的操作和约束。   2)数据操作:数据...
  • 各类数据结构的特点

    万次阅读 2013-08-23 11:33:18
    数据结构是对在计算机内存中(有时在磁盘中)的数据的一种安排。数据结构包括数组、链表、栈、二叉树、哈希表等等。算法对这些结构中的数据进行各种处理。例如,查找一条特殊的数据项或对数据进行排序。 掌握这些...
  • HashMap的数据结构

    千次阅读 2018-05-25 21:02:11
    原文出处: 李大辉的博客HashMap...HashMap的数据结构在Java编程语言中,最基本的结构就是两种,一个是数组,另外一个是模拟指针(引用),所有的数据结构都可以用这两个基本结构来构造的,HashMap也不例外。HashMa...
  • Python数据结构底层实现浅析——list和tuple Python数据结构底层实现浅析——list和tuple 提到python中list和tuple的底层实现,就要回到最基本的数据结构——线性表。 把一组数据元素,通常它们还是同一类型,...
1 2 3 4 5 ... 20
收藏数 117,308
精华内容 46,923
关键字:

扩充的数据结构