现在的位置: 首页 > 综合 > 正文

杨氏矩阵 Young Tableau

2013年09月01日 ⁄ 综合 ⁄ 共 1766字 ⁄ 字号 评论关闭

from: http://blog.csdn.net/michealmeng555/archive/2008/05/28/2489923.aspx

 

 

杨氏矩阵 Young Tableau

前几天算法课上老师提到了一个数据结构--Young Tableau

,只是简单的提了一下,没有仔细的讲解,于是自己在网上搜集了一些资料,并且加以研究,感觉杨氏矩阵(Young Tableau

)是一个很奇妙的数据结构,他类似于堆的结构,又类似于BST
的结构,对于查找某些元素,它优于堆;对于插入、删除它比BST
更方便。

首先介绍一下这个数据结构的定义,Young Tableau

有一个m*n
的矩阵

,让后有一数组 a[k]

,
其中 k<=m*n

然后把a[k]

中的数填入 m*n
的矩阵

中,填充规则为(如

1-1


):

1. 


每一行每一列都严格单调递增
(有其他的版本是递减,其原理相同)。

2. 


如果将a[k]
中的数填完后,矩阵中仍有空间,则填入

 

1

2

3

4

5

6

 

1

3

5

7

8

11

a

4

6

9

14

15

19

b

10

21

23

33

56

57

c

34

37

45

55



d







e

1-1

则现在讨论,这个数据结构的几种操作,而在这些操作中,我们会发现堆排序的影子,并且这些操作具有很好的时间复杂度。

 

条件:

一个已经建好的杨氏矩阵(Young Tableau


操作:

【1】 


在杨氏矩阵中插入元素x ---- Insert(x)

【2】 


在杨氏矩阵中删除位于 (x, y)
位置的元素---- Delete(x, y)

【3】 


返回x
是否在矩阵中----Find(x)

其中1-2
操作类似于堆的操作,而4
操作类似于BST
的操作。下面我就用我

自己的理解把这几个操作加以解释。

【1】



插入操作

本操作的时间复杂度为O( n + m ),
其操作类似于堆排序的SIFT-UP
算法(
具体算法见《算法设计技巧与分析》 M.H,Alsuwaiyel
)

。它的堆的结构在这里表现为某个元素Y[x, y]
下面和右面的两个元素 Y[x, y+1] ,Y[x+1, y]
均比Y[x, y]
要大。于是其插入算法可以描述为,首先把待插入元素以行为主序置于所有有效数字(除了无穷以外的数)最后面,如将x=2
,放入 图1-1
d5
的位置,然后执行类似于SIFT-UP
的操作,将x
与它左边(记为x-l
)及上面(记为x-u
)的数进行比较,根据比较结果有三种可能的操作:

1
x-u > x
x-u >= x-l 

则将x
x-u
进行交换

2
x-l > x
x-l > x-u 

则将x
x-l
进行交换

3: x >= x-l
x > x-u 

x
不动,此时已经插入成功

(可以有其他合理的约定)

对例子插入2
进行操作如

1-2


箭头的操作方向。

1

2

3

4

5

6

 

1

3

5

7

8

11

a


2

6

9

14

15

19

b


4


10


21


23


33

57

c

34

37

45

55

56


d







e

1-2

 
 

由上述的操作知其时间复杂度最大为行列之和,即O(m+n)


【2】



删除操作

操作类似于插入操作,其时间复杂度也为O(m+n)

。其操作类似于堆排序的SIFT-DOWN
算法。删除算法可以描述为,首先将删除的位置(x, y)
的数字删除,然后调整,把杨氏矩阵中的最大值k

(可以行为主序进行搜索到最后)填入到被删除位置,然后让此数与其下面的数(k-d)

和右面的数进行(k-r)

比较,
此时比较结果为两种,因为此时元素一定会下移:

 
1

k-d > k-r
k-r
k
进行交换

 
2

k-d < k-r
k-d
k
进行交换

举例 删除图1-1
a3
位置的元素5


1-3

1

2

3

4

5

6

 

1

3

7



8


11


19

a

4

6

9

14

15

57

b

10

21

23

33

56


c

34

37

45

55



d







e

1-3

 

由操作知,删除算法时间复杂同样最多为行列之和,即O(m + n)

   

3
查找算法

 
  

查找算法类似于BST
二叉排序树,不过需要在其思想上稍微进行修改,才能满足杨氏矩阵的查找操作,同样利用杨氏矩阵的性质,不过此时应该换一个角度思考问题,因为与BST
二叉排序树类比,所以应该从左下角
开始看起(如

1-1


d1
位置),该元素的上面的元素比本身小和右面的元素比本身大,这样就与BST
二叉排序树具有相同的性质。所以在查找时从左下角不断的比较,从而最终确定所查找元素位置。

   

如查找19

比较顺序如

1-4

 

1

2

3

4

5

6

 

1

3

5

7

8

11

a

4



6


9


14


15

19

b



10

21

23

33

56

57

c

34

37

45

55



d




抱歉!评论已关闭.