小编dat*_*jko的帖子

Cross posted:需要对简洁数据结构算法有一个很好的概述

由于我了解简洁数据结构,因此迫切需要对该领域的最新发展进行良好的概述.

我谷歌搜索并阅读了很多文章,我可以在google结果的顶部看到我的头顶请求.我仍然怀疑我错过了一些重要的事情.

以下是我特别感兴趣的主题:

二进制树的简洁编码,具有获得父,左/右子,子树中元素数的有效操作.

这里的主要问题如下:我所知道的所有方法都假设以节点优先顺序枚举的树节点(就像在这个领域的先驱工作中Jacobson,G.J(1988).简洁的静态数据结构),它没有似乎适合我的任务.我处理深度优先布局中给出的巨大二叉树,深度优先节点索引是其他节点属性的关键,因此更改树形布局对我来说有一些成本,我想最小化.因此,有兴趣参考考虑其他BF树布局的工作.
外部存储器中的大型可变长度项目数组.数组是不可变的:我不需要添加/删除/编辑项目.唯一的要求是O(1)元素访问时间和尽可能低的开销,比直接的偏移和大小方法更好.以下是我收集的有关我的任务典型数据的一些统计信息:

典型的物品数量 - 数亿,高达数十万;

约30%的物品长度不超过1 位 ;

40%-60%的项目长度小于8位;

只有少数百分比的项目长度在32到255位之间(255位是限制)

平均项目长度~4位+/- 1位.

项目长度的任何其他分布在理论上是可能的,但所有实际上有趣的情况都具有接近上述的统计数据.