前两天提出的那个数据结构已经写程序实现. 发现不如我需要的理想, 今天又熬通宵做新的了.
首先说说我的需求: 我需要一个映射表, 好象 std::map 那样的.希望能尽量节约内存. 查找速度要快. 在程序运行过程中, 会向这个表不定期添加数据. 但是绝对不会删除数据.查找的频率远比添加的高.因为只添加,查找, 不删除. 所以这个映射表在运用中, 会逐步处于一种稳定状态. 也就是说,添加的频率减少.
如果不希望浪费内存. 那么紧凑数据结构中. 有序表的查找速度最快. 2分查找的时间复杂度是 O(log(N))
用查找树来实现的话, 插入的复杂度比较低. 尤其是自平衡类型的树, 比如红黑树, AVL 树等等。它的插入时间复杂度也在 O(log(N))
如果结合树表, 是不是可以取得不错的成绩呢?
我构思了一种树表结合的数据结构. 分配了一个固定空间的内存保存一些树的节点. 用于映射表的插入操作.
一开始, 数据都是被插入到查找树中. 但是, 一旦满足某种条件, 我们把整个查找数序列化到一个数组里。并把树清空。
新的插入请求会重建这棵树，但是新的树的叶子节点会保留数组的某个区间信息。我们可以把数组的一个区间看成是查找树的一个节点，也符合规范。
序列化的条件可以有两种，一是，预先为树分配的内存满，二是，长时间只有查找请求而无插入请求。这样，在映射表趋于稳定后，整个数据结构就退化为一张有序表。
ps. 一些改进的思路：
1. 查找树的序列化可以放在系统空闲的时候做
2. 并不急于序列化查找树，而是在某次查找结果落在树节点上，而非表区间中(树的叶子节点) 时，判断树节点对其下区间的分割比例。把节点向中间移动。(把节点和表中的一向对换即可)
3. 序列化查找树的时候并不全部清空，而是保留 3 层树结构，作为对表的一种索引。根据用户查找的喜好, 可以不断调整这个索引树，调整查找树和对应的表区间分割的位置。有望得到比高于二分查找的效率(主要是对查找频率高的 key 的作用).