2014-06-19 11:20:40 loveprogram_1 阅读数 994
  • iOS开发教程之OC语言

    Objective-C是扩充C的面向对象编程语言,iOS开发是用的Objective-C语言,本专题更系统的讲解Objective-C语言当中的一些要点,类的封装、基本数据结构(NSString、NSData)、继承、内存管理(retain点语法、MyArray、AutoreleasePool、浅拷贝详述、深拷贝详述)等内容。

    40600 人正在学习 去看看 欧阳坚

算法导论第14章 【数据结构的扩张】
    为应对新的应用需求,经常是通过存储额外信息的方法来扩张一种标准的数据结构,
然后对这种数据结构,编写新的操作来支持所需要的应用。


一、动态顺序统计
一种支持一般动态集合上,顺序统计操作的数据结构。
通过这种数据结构,可以快速地找到一个集合中的第i小的数,(select)
或给出一个指定元素在集合的全序中的位置。(rank)
【已知】对于一个无序的集合,能够在O(n)的时间内确定任何的顺序统计量。
rank(x):获得x在数组中的位置,遍历数组并统计比x.key小的元素数即可。
select(i):利用random-partion()函数,二分地去定位即可。
【目标】修改红黑树,使得在O(lgn)时间内确定任何的顺序统计量。
【顺序统计树】在每个结点上存储附加信息的一棵红黑树。
除了基本结点属性x.key、x.color、x.p、x.left、x.right之外,还附加x.size属性。
设哨兵T.nil的x.size为0,则有等式: x.size = x.left.size + x.right.size + 1。

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
【OS-RANK解释】
如果y是y.p的左孩子,y.p和y.p的右子树中所有结点都不会先于x,r保持不变。
如果y是y.p的右孩子,y.p和y.p的左子树中所有结点都先于x,r要加上y.p.left.size + 1。
【对子树规模的维护】
LEFT-ROTATE( T, x )的代码,要添加下面两行:
y.size = x.size // y = x.right
x.size = x.left.size + x.right.size + 1
RIGHT-ROTATE( T, x )的代码,要添加下面两行:
y.size = x.size
x.size = x.left.size + x.right.size + 1
维护size时间复杂度:O(1)。所以插入、删除,包括维护size属性,都只需要O(lgn)时间。


二、如何扩张数据结构(Ex. OS-trees)
(1)选择一种基础数据结构。(red-black tree)
(2)确定基础数据结构中要维护的附加信息。(subtree size,直接记录秩也可以,不过速度太慢了)
(3)检验基础数据结构上的基本修改操作能否维护附加信息。(Insert、Delete/Rotate是否可以维持子树大小的信息)

(4)设计一些新操作。(怎么使用这些信息:OS-Select、OS-Rank)


【实际使用时】上面可能更像一个checklist,而设计时可以先设计一个些新操作(4),再去验证附加信息维护等。

【2+2】2组数据 + 2组操作:基础操作+附加操作 : 基本操作+新添操作



三、区间树
一个区间[t1, t2]表示成一个对象i,其中属性i.low = t1为低端点, i.high = t2为高端点。
【区间i与i'重叠(overlap)】
如果i与i'的交集非空,即如果i'.low <= i.high and i.low <= i'.high。
任何两个区间i与i'满足【区间三分定律】,即下面三条性质之一成立:
(1)i和i'重叠。
(2)i在i'的左边,即i.high < i'.low

(3)i在i'的右边,即i.low > i'.high


Example Interval Trees : Maintain a set of intervals.

eg : time intervals.




【区间树】一种对动态集合进行维护的红黑树,其中每个元素x都包含一个区间x.int。
区间树支持下列操作:
(1)INTERVAL-INSERT( T, x ):将包含区间属性的int的元素x插入到树T中。
(2)INTERVAL-DELETE( T, x ):从T删除x。
(3)INTERVAL-SEARCH( T, i ):返回一个指向T中元素x的指针,使x.int与i重叠。不存在返回T.nil。
【扩张数据结构】
步骤1:基础数据结构
一棵红黑树,每个结点x包含一个区间属性x.int,且x的关键字为区间int的低端点x.int.low。
所以该数据结构的中序遍历,就是按低端点的次序排列的各区间。
步骤2:附加信息
包含一个值x.max,它是以x为根的子树中,所有区间的端点的最大值。
步骤3:对信息维护
通过x.int和x子结点的max,有 x.max = max( x.int.right, x.left.max, x.right.max )。
故一次旋转后,更新max属性只要O(1)的时间;所以插入和删除的运行时间为O(lgn)。
步骤4:设计新操作。
INTERVAL-SEARCH( T, i )
	x = T.root
	while x != T.nil and i does not overlap x.int
		if x.left != T.nil and x.left.max >= i.low // i'.low <= i.high 
			x = x.left
		else
			x = x.right
	return x
【解释】
分支if执行时,如果在以x.left为根的子树中,没有与i重叠的区间,
则树的其他部分也不会包含与i重叠的区间。
分析:有x.left.max >= i.low,根据max属性定义,在x的左子树中必定存在某区间i',满足:
i'.high = x.left.max >= i.low,
如果i与i'不重叠,则i.high < i'.low <= i''.low,其中i''为右子树中任意区间,
所以右子树也不包含与i重叠的区间。

========================================================================

【图示化补充】

【顺序统计树】下面给出一个修改后的红黑树的例子,如下图所示:

【区间树】修改红黑树得到的区间树如下图所示:

从图可以看出,对区间树以每个节点的左端点值进行中序变量即可得到有序的序列。




2019-05-22 09:49:49 weixin_40205234 阅读数 266
  • iOS开发教程之OC语言

    Objective-C是扩充C的面向对象编程语言,iOS开发是用的Objective-C语言,本专题更系统的讲解Objective-C语言当中的一些要点,类的封装、基本数据结构(NSString、NSData)、继承、内存管理(retain点语法、MyArray、AutoreleasePool、浅拷贝详述、深拷贝详述)等内容。

    40600 人正在学习 去看看 欧阳坚

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

一、动态顺序统计

       一种支持一般动态集合上顺序统计操作的数据结构。通过这种数据结构,可以快速找到一个集合中的第i小的数,(select)或给出一个指定元素在集合的全序中的位置。(rank)

【思想】添加新项:在红黑树的结点上记录下该结点的子树个数。size[x] = size[left[x]] + size[right[x]] +1。 若结点为空,则为0。

此外当你对该扩展的数据结构进行插入和删除操作时,需随时更新子树的大小,与插入和删除操作同步进行,但是需要重新使其回到平衡。主要在于case2和case3这两种情况的旋转。<可以与算法系列笔记4>红黑树的插入代码进行对比,看修改情况。

代码:

返回第i 排名的元素os_select(i)
 

BSTNode* OSRBTree::os_select(BSTNode *p, const int &ith){
	if(p == NULL) return p;
	int k = 1;
	if(p->left != NULL){
		k = p->left->size + 1;           // 当前该结点所对应的rank
		
	}
	if(ith == k) return p;
	if(ith < k) return os_select(p->left, ith);
	else return os_select(p->right, ith - k);
}

给定一个元素x,返回其排名(os_rank(x))

//  return the rank of value
int OSRBTree::os_rank(BSTNode *p, const int &value){
	if(p == NULL) return 0;
	int k = 1;
	if(p->left != NULL)
		k = p->left->size + 1;
	if(p->val == value)
		return k;
	else if(p->val > value) return os_rank(p->left, value);
	else return os_rank(p->right, value)+k;
}

方法论:如<OSTree—顺序统计树>

1:选择一个基础的数据结构(red-black tree)

2:在数据统计中维护一些附加信息(子树大小)

3:验证这个数据结构上的信息不会受修改操作的影响(insert, delete---rotations)

4:建立新的运算。假设新的数据已经存好了,然后开始使用这些信息(os_select, os_rank).

二、区间树(Interval Tree)

【图示化补充】

问题:保存一系列的区间,比如说时间区间。需要查询集合中的所有区间,与给定区间发生重叠的有哪些?

我们按照上面提到的方法论来进行:

1:选择红黑树作为基本的数据结构,并将区间的较低值(low)作为键值

2:将结点子树的最大值作为新添加的项(m[x] = max{high[int[x]],m[left[x]], m[right[x]]}).

3:是否受插入删除等操作的影响?受,但是在O(1)时间内就能调整过来,见代码。

4:新的操作,查询集合中与给定区间重叠的一个区间。
 

#ifndef INTERVALTREE
#define INTERVALTREE
#include <iostream>
#include <string>
using namespace std;
struct dataNode{
    int low;
    int high;
};
class BSTNode{
public:
    BSTNode *left, *right;
    BSTNode *parent;
    int val;
    dataNode d;
    string color;
    int m;         // 最大值
};
 
class IntervalTree{
public:
    IntervalTree(const dataNode &d)
    {
        root = new BSTNode();
        root->d = d;
        root->color = "black";
        root->left = NULL;
        root->right = NULL;
        root->m = d.high;
        root->parent = NULL;
        root->val = d.low;
    }
 
    BSTNode* insertBST(BSTNode *p, const dataNode &d);
    void insertIntervalTree(BSTNode *root1, const dataNode &d);
    void inorderOSRBTree(BSTNode *p);
    BSTNode* intervalSearch(BSTNode *p, const dataNode &d);
public:
    BSTNode *root;
    void destroyBST(BSTNode *p);
};
 
#endif

【顺序统计树】下面给出一个修改后的红黑树的例子,如下图所示:

【区间树】修改红黑树得到的区间树如下图所示:

从图可以看出,对区间树以每个节点的左端点值进行中序变量即可得到有序的序列。



 

2017-11-04 10:52:05 u010385790 阅读数 151
  • iOS开发教程之OC语言

    Objective-C是扩充C的面向对象编程语言,iOS开发是用的Objective-C语言,本专题更系统的讲解Objective-C语言当中的一些要点,类的封装、基本数据结构(NSString、NSData)、继承、内存管理(retain点语法、MyArray、AutoreleasePool、浅拷贝详述、深拷贝详述)等内容。

    40600 人正在学习 去看看 欧阳坚

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

 

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

 

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

2015-04-26 23:28:33 lth404391139 阅读数 894
  • iOS开发教程之OC语言

    Objective-C是扩充C的面向对象编程语言,iOS开发是用的Objective-C语言,本专题更系统的讲解Objective-C语言当中的一些要点,类的封装、基本数据结构(NSString、NSData)、继承、内存管理(retain点语法、MyArray、AutoreleasePool、浅拷贝详述、深拷贝详述)等内容。

    40600 人正在学习 去看看 欧阳坚

本节课主要讲了如何构造自己想要的数据结构,或者扩充已有数据结构的功能,以实现想要的特定功能


比如设计一个动态结构,满足功能寻找第k大的数

其做法是维护每个结点的子结点个数来推导其秩,而不维护其秩,因为动态操作会使得其难以维护
红黑树的插入操作 1.树插入 2.rebalance


构造自己需要的扩充数据结构的基本流程

1.选择一个基本的数据结构 例如红黑树
2.决定要添加到结点的基本信息  例如实现查询第k大数功能,应添加的基本信息为所有子树结点之和,而非直接保存该结点键值的秩
3 维持 插入+旋转/删除+旋转

4 封装为函数,实现其功能


后面又介绍了一种区间树,其实相关的数据结构还有很多,包括线段树及其各种变体、名次树、主席树等等,其主要思想都是维护一些额外的信息,去实现想要的功能,之后我会实时更新一些例子
2015-07-21 11:03:43 sinat_28626091 阅读数 379
  • iOS开发教程之OC语言

    Objective-C是扩充C的面向对象编程语言,iOS开发是用的Objective-C语言,本专题更系统的讲解Objective-C语言当中的一些要点,类的封装、基本数据结构(NSString、NSData)、继承、内存管理(retain点语法、MyArray、AutoreleasePool、浅拷贝详述、深拷贝详述)等内容。

    40600 人正在学习 去看看 欧阳坚

(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. (待完成

如何扩充数据结构

阅读数 1678

没有更多推荐了,返回首页