我正在上一门算法课程,遇到了一个问题。
我需要建议一个支持以下内容的数据结构:
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
字段。
如果您想利用您的语言已经提供的库,那么您可以创建一个只包含值和年龄的节点对象,并将其插入两个独立的树中。