具有分摊O(1)删除和O(log n)搜索的数据结构 [英] Data structure with amortized O(1) delete and O(log n) search

问题描述

我需要一个支持两种操作的数据结构-删除和搜索.现在，删除操作应在摊销O(1)时间内运行，而搜索应在 O(log n)时间内运行.

I need a data structure that supports two operations - delete and search. Now, the delete operation should run in amortized O(1) time, while search should run in O(log n) time.

搜索操作应按以下方式工作:查找指定的值，如果在此处，则返回值本身.否则，返回最接近的较大值(返回顺序后继).

Search operation should work as follows: look for value specified and if it is here, return value itself. Otherwise, return the nearest greater value (return inorder successor).

这个数据结构可能是什么?

What could this data structure be?

推荐答案

可能是一对数据结构:

• 二进制搜索树，包含值
• 哈希表，用于保存指向二进制搜索树中节点的指针

要搜索时，请在O(log n)时间在二进制搜索树中进行搜索.如果要删除，请首先在摊销的O(1)中的哈希表中找到该节点，然后在摊销的O(1)中的二叉搜索树中删除.

When you want to search, do the search in binary search tree in O(log n) time. When you want to delete, first find the node in hash table in amortized O(1) and delete in binary search tree in amortized O(1).

这篇关于具有分摊O(1)删除和O(log n)搜索的数据结构的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！