乔斯特尔树 JostleTree是部分求和树,其项目宽度存储在树的分支中,而不仅仅是叶子。 要了解锯木有什么用途,可以想象一下在狭窄的架子上紧紧捆在一起的一系列大小不同的物体。 它们之间没有空格。 当您插入一个新项目时,它之后的所有项目都需要移动一点。 同样,如果一件物品的尺寸发生变化,则需要稍微移动一下之后的所有物品,它将保持紧密包装。 jostletree支持插入,调整大小和删除,还支持按位置随机访问; 从起点选择距离并绘制任何内容。 此处提到的所有操作均以对数时间运行。 如果您需要使用这些属性为一系列事物建模,您将不会比jostletree做得更好。 其显着的应用之一是从大型集合中随机采样,其中集合中的每个元素可能具有不同的绘制概率。 这是我所知道的唯一的加权去除随机抽样解决方案。 您还可以偏向抽样,以偏向于从列表的一端或另一端抽取,例如,如果您想对内容聚合器进行抽样,以使评