使用哪种数据结构进行O(log n)键和值查找? [英] What data structure to use to have O(log n) key AND value lookup?

问题描述

具有排序的dict(哈希表，映射或任何键/值结构)，您可以轻松地进行二进制搜索来查找项目.如果我们假设键是唯一的，但是值可以重复，那么我们可以使用哪种数据结构对键进行O(log n)检索，还可以使用O(log n)查询来查找给定数据中的values=something计数? /p>

Having a sorted dict (hash table, map or whatever key/value structure) you can easily have a binary search to look for an item. If we assume the keys are unique but values could be repeated, what data structure can we use to have O(log n) retrieval for keys and also O(log n) query to find count of values=something in the given data?

推荐答案

两个二进制搜索树(一个用于键，第二个用于值，具有相互的指针)将提供所需的功能.指针从键到值可以是多对一，从值到键可以是一对多.

Two binary search trees, one for keys, second for values, with mutual pointers will provide the required functionality. The pointers can be many-to-one from keys to values and one-to-many from values to keys.

这篇关于使用哪种数据结构进行O(log n)键和值查找?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！