Lib.rs

我们将累加器的元素排列成一棵完美的二叉树森林，最大的树在左侧，最小的树在右侧。这种排列使得在需要时树合并和分裂的直观可视化变得更加容易。行操作也是可能的，元素可以在子树之间移动。

由于森林中的树总是完美的，它们包含 2^h 个叶子，其中 h 是树的高度。任何自然数都可以组织成一个完美的二叉树森林，就像任何自然数都可以表示为二的幂之和一样。这种关系提供了一个方便的捷径：累加器中的树的数量是叶子数的二进制表示中1位的数量。这些树的高度是那个表示中1位的位位置。例如，一个包含133个叶子的森林将有3棵树：高度为7的树，高度为2的树，以及高度为0的树。这可以通过查看数字133的二进制表示（10000101）快速看到。

可以使用这种方法将任何一组叶子分组到二叉树中。在任何情况下，只需知道每棵树的根就可以向森林中添加一个额外的叶子。在133个叶子的例子中，添加额外的叶子会导致134个叶子，其二进制表示为10000110。0高度树（它本身是一个叶子）会与新添加的叶子结合，创建一个具有2个叶子的1高度树。然后，添加到135将创建一个包含额外叶子的0高度树。

• Thaddeus Dryja，Utreexo论文