JostleTree

JostleTree支持插入、调整大小和删除，还支持在特定位置随机访问；从一个位置选择一个距离，并获取该位置的内容。所有提到的操作都在对数时间内运行。

了解JostleTree的优点的一个好方法是想象它是一系列不同大小物体在长而浅的架子上的排列，它们总是紧密排列在一起。它们之间没有空隙。你可以在任何地方插入一个新项目，之后的所有项目都会滑动一点来适应它。你可以改变其中一个项目的尺寸，同样，之后的所有项目也会移动一点，保持紧密排列。你可以指向架子上任意位置，并快速取出那里的内容，而无需计算它之前或之后的所有项目。这些大多是相当普通的项目属性，但在此之前，在数据结构中并不常见。

它的一个显著应用是从大型元素序列中随机采样，其中集合中的每个元素被抽取的概率可能不同。这是我了解的唯一随机加权抽样带删除的解决方案。你也可以对采样进行偏置，以便更喜欢从列表的一端或另一端抽取，例如，如果你想抽样内容聚合器，以便评分更高、更近期的帖子更有可能被选中，你可以按年龄对jostletree的内容进行排序，然后使用以下代码进行抽样：posts.get_item(oldest_allowed*random().powf(3.0))。

let mut candidate = JostleTree::<usize, char>::new();
candidate.insert_back(1, 'a');
candidate.insert_back(9, 'b');
candidate.insert_back(1, 'c');
candidate.insert_back(1, 'd');
assert_eq!(candidate.get_item(5).unwrap(), &'b');
assert_eq!(candidate.get_item(10).unwrap(), &'c');
assert_eq!(candidate.get_item(11).unwrap(), &'d');

candidate.insert_at(5, 1, 'e');
assert_eq!(candidate.get_item(1).unwrap(), &'e');

它是如何工作的？

基本上，想象一棵二叉树，其中每个分支存储一个width值，即其子节点的宽度的总和，在叶子节点终止，叶子节点的宽度是你设置的。你可以通过查看你的两个子节点并确定左边的子节点是否大于或小于你需要的值，然后根据这个值向下导航来快速导航到特定偏移量的子节点。还有额外的细节和优化，但这为你提供了一个基本理解。

这些优化包括：项目存储在分支中，没有独立的叶子类型。每个分支有两个宽度值，它们的项目跨度以及子项的总跨度。我们可以进一步优化（取而代之）存储左子项的总跨度，这样在搜索应该继续到右子项时，左子项就不必进行解引用；但我不打算这样做；如果我们认真对待优化，分支应该更大，它们应该包含尽可能多的可以在缓存行中容纳的项目。）

使用浮点数作为跨度

该数据结构是泛型，适用于跨度类型，但 f32 和 f64 无法使用，因为它们没有实现 Ord。 (它们没有实现 Ord 的原因是存在一个浮点数，它既不小于也不大于另一个浮点数。你能猜到是哪一个吗？它是 NaN。 NaN 也是浮点数不能实现 Eq 的原因。有一些数据结构，如果你用浮点数欺骗它们，实际上会破坏并执行不安全的事情，因此出于这个原因。 NaN 实际上非常糟糕。)

但不必担心。你只需使用 https://crates.io/crates/noisy_float。这是一个无开销的浮点数包装器，不允许 NaN。

相关数据结构

它与在 AN EFFICIENT METHOD FOR WEIGHTED SAMPLING WITHOUT REPLACEMENT* C. K. WONG AND M. C. EASTON 中描述的部分和树非常相似。区别在于，它将元素和元素权重存储在分支中，而不是在特殊的独立叶子节点中，这减少了大约一半的分配，并将每次查询的访问次数对数减少。我不确定为什么有人会这样做。）

似乎 别名方法 是随机加权采样的一个更快替代品，但据我所知，它似乎不支持快速编辑（必须重建？）。因此，它不会进行带有删除的随机采样，可能还有其他它不会做的事情。