请教双键的动态结构用什么数据结构比较好？ - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Programming - 葵花宝典

请教双键的动态结构用什么数据结构比较好？

请教双键的动态结构用什么数据结构比较好？# Programming - 葵花宝典

g*s2008-06-19 07:06

1 楼

比如一个记录，id和name都是unique的，都可以用来做key。现在有这样一组记录，插
入/删除/查询的操作很频繁，而且可能用name也可能用id作key。用什么数据结构比较
好？
最简单的想法是两个balanced BST，一个用id作key，一个用name，但这样等于时间空
间都double了，虽然复杂度不变。
两个hash table的话也是同样的问题。另外因为记录是动态变化的，hash table的size
也不太好定。
有没有dual-key binary search tree之类的数据结构呢？

f*y2008-06-19 07:06

2 楼

要我看单独设置一个id和name的lookup表，加一个按照id或者name的树

size

【在 g*********s 的大作中提到】

: 比如一个记录，id和name都是unique的，都可以用来做key。现在有这样一组记录，插
: 入/删除/查询的操作很频繁，而且可能用name也可能用id作key。用什么数据结构比较
: 好？
: 最简单的想法是两个balanced BST，一个用id作key，一个用name，但这样等于时间空
: 间都double了，虽然复杂度不变。
: 两个hash table的话也是同样的问题。另外因为记录是动态变化的，hash table的size
: 也不太好定。
: 有没有dual-key binary search tree之类的数据结构呢？