我正在寻找c++中的数据结构,我需要一个建议。
我有节点,每个节点都有unique_id和group_id:
1 1.1.1.1
2 1.1.1.2
3 1.1.1.3
4 1.1.2.1
5 1.1.2.2
6 1.1.2.3
7 2.1.1.1
8 2.1.1.2
我需要一个数据结构来回答这些问题:
是否存在可以回答这些问题的数据结构(插入和回答的复杂时间是多少?)?还是应该实现?
我将不胜感激。
编辑:
在开始时,我需要构建此数据结构。大多数操作是按组ID进行读取。插入会发生,但会少于阅读。
时间复杂度比存储空间更重要
最佳答案
对我来说,诸如组ID之类的分层数据需要树结构。 (我认为对于500个元素来说,这并不是真正必要的,但是看起来很自然并且可以很好地扩展。)
树的前两层中的每个元素都将仅包含子ID的 vector (如果它们是有序的)或映射(如果它们是无序的)。
树层次结构中的第三级将再次在 vector 或映射中保留指向叶子的指针,这些指针包含第四组ID部分和唯一ID。
通过导航树,可以轻松快速地回答问题2-4。
对于问题1,需要一张从唯一ID到树上叶子的映射。插入到树中的每个元素还具有指向它插入到 map 中的指针。