Joh*_*ier 19 algorithm tree scala clojure data-structures
宽松基数平衡树(RRB-trees)是不可变向量(在Clojure和Scala中使用)的推广,它具有"有效恒定"的索引和更新时间.RRB树保持有效的索引和更新,但也允许有效的连接(log n).
作者以我难以理解的方式呈现数据结构.我不太清楚每个节点维护的不变量.
在2.5节中,他们描述了他们的算法.我认为他们确保索引到节点只需要在基数搜索后进行线性搜索的额外步骤.我不明白他们是如何得出他们的额外步骤的公式,我想也许我不确定每个变量是什么意思(特别是"总共p个子树分支").
RRB树连接算法的工作原理是什么？
它们确实在第2.4节中描述了不变量，但是，如前所述，B树节点不便于基数搜索。相反，我们选择允许节点大小在m和m 1之间变化的初始不变量。这定义了一组平衡树从众所周知的2-3棵树，3-4棵树和（对于m = 32而言）31-32棵树开始，这种不变量可确保平衡并在大多数情况下实现基数分支搜索。基数搜索以找到正确的分支。所需的额外步骤在更高的级别上会增加。”
查看他们的公式，看起来他们已经计算出存储在子树中的最大和最小数量的值。两者之间的差异是一个点下面的最大和最小数量的值之间的最大可能差异。如果将其除以插槽下面的值数，则可以算出要查看哪个插槽以查看其中是否包含要搜索的索引，从而可以使用的最大插槽数将被关闭。