seb*_*bas 2 algorithm data-structures
我正在寻找一种数据结构,它可以确保至少删除和插入节点的Log(n)复杂度以及接近O(1)或分摊的Log(n)以搜索最大(或最小)值.
我正在考虑使用自我平衡的BST(哪一个？)进行修改以记住插入的最大值(或最小值).
有什么建议吗？
对不起,我必须编辑问题...当然,自平衡BST可以允许在log(n)中搜索max和min,但我正在考虑更多关于O(1)的事情.
您可以使用任何自平衡BST(例如红黑,AVL).
如果跟踪最小值和最大值,获取它们的查询将采用O(1).
由于最小值和最大值只能在插入和删除时更改,因此在执行这些操作时(基本上它们的运行时间仍为O(log n))基本上可以重新确定它(在O(log n)中).
虽然在收到查询时重新确定最小值或最大值并且自上次查询后有插入或删除可能更好.
它也可能更加聪明 - 如果你到目前为止只离开了,你是最小的,如果你只是走了,你就是最大的.插入时,只需更换最小值/最大值即可.删除时,只需在已删除节点的树中查看,即可找到新的最小值/最大值.