你的位置:首页 > 信息动态 > 新闻中心
信息动态
联系我们

数据结构红黑树题

2021/11/19 5:55:26

(Application of Data Structure) A sequence of numbers are to be instered to your data structure. Whenever a number is inserted, you will be asked to report the maximum gap between two consecutive numbers in their sorted order. For example, 

output: /

1 22

output: 21

1 22 15 

output: 14 (because the sorterd oeder is 1 15 22, and 15-1 = 14 > 7 = 22-15)

1 22 15 5

ourput: 10

1 22 15 5 18

output: 10

1 22 15 5 18 9

output: 10

Show how to report the maximum hap in O(log n) time per insertion.

Solution:

解题思路:能保证所有操作都是O(log n)的数据结构是红黑树。所以先把数字插入到红黑树中,这一步用时O(log n)。插入数字后,可以计算被插入元素到successor和predecessor(和这个元素相邻的稍大一点和稍小一点的元素),这一步用时O(h)=O(log n), h是树的高度。计算与successor和predecessor的差值(gap)。每插入一个新元素时,最多有一个之前存在的gap被删除,与此同时并且产生两个新的gap。例如:1 22 gap:21 -> 1 15 22 gap:删除21 产生14 7

每次插入新元素前,我们还要记录下之前所有的gap,并且用gap组建一个新的红黑树。我们已经知道,每次插入新元素,最多会删除一个gap并产生两个新gap,所以在用gap组建的红黑树中,我们要进行三次操作:删除老gap,两次插入新gap。这一步用时3O(log n)。最后,找到gap组建的红黑树中的最大值,用时O(log n).

总用时O(log n)。