设计一个在恒定时间内支持build(s)、insert(s,k)、delete_max(s)、delete_old(s,



我正在上一门算法课程,遇到了一个问题。

我需要建议一个支持以下内容的数据结构:

build(S(:在O(n*lgn(中构建具有n个值的结构S

insert(S,k(:将值k插入O(lgn(中的S

delete_max(S(:删除O(lgn(中S的最大值

delete_old(S,t(:删除o(lng(中S中最旧的t值

add_to_new(S,d(:将值d加到O(Lng(中输入到S的最后一个值上

我们刚刚学习了红黑树,所以我想我可能需要使用这个结构并添加一些东西,或者添加另一个结构来帮助我处理delete_old(S,t(。我很难理解如何更新";年龄;在我使用";delete_old(S,t(";。

假设我进入了S:11,22,44,68,79…然后11是最老的,22是第二老的,等等。在我删除了第三个最老的值(值44(之后,现在68需要成为第三个最大的值,79将成为第四个最大的,等等-在我在O(lng(中删除的值之后,我将如何更新所有剩余值的年龄?

我希望我的问题很清楚。任何帮助都将不胜感激!谢谢:(

要支持两个排序,需要混合两个有序的数据结构。

例如,可以为每个值创建一个节点,并将其链接到两个独立的红黑树中,一个按值排序,另一个按年龄排序。当然,节点对象将需要两组链路和两个isRed字段。

如果您想利用您的语言已经提供的库,那么您可以创建一个只包含值和年龄的节点对象,并将其插入两个独立的树中。

最新更新