首页 > 试题广场 >

(y-fast检索树)本题讨论的是D.Willard的y-f

[问答题]
(y-fast检索树)本题讨论的是D.Willard的y-fast检索树。它与van Emde Boas树类似,一个全域大小为u的y-fast检索树的MEMBER,MINIMUM,MAXIMUM,PREDECSSOR和SUCCESSOR操作的最坏运行时间是O(lglgu)。INSERT和DELETE操作的摊还时间为O(lglgn)。想缩减空间的van Emde Boas树一样,y-fast检索树存储n个元素的空间仅需要O(n)空间,y-fast检索树的设计依赖于完全散列。
     假设创建一个完全散列表作为初步的结构,该散列表中不仅包含动态集合中的每个元素,而且还包含这些元素的二进制前缀,例如如果u=16,那么lgu=4,并且x=13在集合中,由于13的二进制表示为1101,因此完全散列表应含有1,11,110,和1101.除了该散列表外,还要创建一个该集合当前元素以升序排列的双向链表。
a.这个数据结构的空间需求是多少?
b.如何在O(1)时间内完成MINIMUM和MAXIMUM操作?如何在O(lglgu)时间内完成MEMBER,PREDECSSOR和SUCCESSOR操作?如何在O(lgu)时间内完成INSERT和DELETE操作?
    为了将空间减少到O(n),我们对数据结构做出如下修改:
  • 将n个元素分为大小为lgu的n/lgu的个组(假设lgu可以整除n)第一组由最小的lgu个元素组成,第二组由下面lgu个最下的元素组成,以此类推。
  • 对每个组都设置一个“代表”,第i组的代表至少与组里的最大元素一样大。而且比第i+1组的最下元素要小。(最后一组的代表可以是最大的可能元素u-1),注意,代表可能是一个值并不包含在集合中。
  • 把每组的lgu个元素存储在一个二叉平衡搜索树中,比如红黑树。每个代表指向它所在组中的平衡二叉搜索树,而且每个平衡二叉搜索树指向它的代表。
  • 完全散列表只存储这些代表,也是用双向链表按升序排列来存储。
    我们称这种结构为一个y-fast检索树
c.说明一个y-fast检索树存储n个元素的空间需求仅为O(n)。
d.说明使用y-fast检索树,如何在O(lglgu)时间内完成MINIMUM,MAXIMUM操作。
e.说明如何在O(lglgu)时间内完成MEMBER操作?
f.说明如何在O(lglgu)时间内完成PREDECSSOR和SUCCESSOR操作
g.解释为什么INSERT和DELETE操作要耗费O(lglgu)时间?
h.在y-fast检索树中每组需要精确的lgu个元素存储,试说明如何放松这个存储需求来保证在O(lglgu)摊还时间内完成INSERT和DELETE操作,并同时不影响其他操作的渐近运行时间?

这道题你会答吗?花几分钟告诉大家答案吧!