绳子和自平衡二叉树混合？ （即具有快速第 n 个元素查找的排序集）
Rope and self-balancing binary tree hybrid? (i.e Sorted set with fast n-th element lookup)
是否有一个排序集的数据结构允许快速查找第 n 个（即最少但第 n 个）项目？也就是说，类似于绳索和红黑树的混合体。
似乎应该可以跟踪左子树的大小并通过旋转更新它，或者做一些其他聪明的事情，我希望聪明的人已经解决了这个问题。
Seems like it should be possible to either keep track of the size of the left subtree and update it through rotations […]
是的，这很有可能；但是与其跟踪左子树的大小，不如跟踪以给定节点为根的 complete 子树的大小要简单一些。 （然后您可以通过检查其左子树的大小来获取其左子树的大小。）它并不像您想象的那么棘手，因为只要其子节点是最新的，您就可以随时重新计算节点的大小，因此除了确保通过沿着树向上移动来重新计算大小之外，您不需要任何额外的簿记。
请注意，在大多数可变红黑树实现中，'put' 和 'delete' 一旦恢复了不变量就停止向树上回走，而使用这种方法你需要走在所有情况下一直备份树。这对性能的影响很小，但至少不难实现。 （在纯粹的功能性红黑树实现中，即使这也不是问题，因为它们总是必须沿着完整的路径返回以创建新的父节点。所以你可以将大小计算放在构造函数中 - 非常简单。)
已编辑 以回应您的评论：
I was vaguely hoping this data structure already had a name so I could just find some implementations out there and that there was something clever one could do to minimize the updating but (while I can find plenty of papers on data structures that are variations of balanced binary trees) I can't figure out a good search term to look for papers that let one lookup the nth least element.
集合中第 n 个最小值的奇特术语是 order statistic; so a tree structure that enables fast lookup by order statistic is called an order statistic tree。第二个 link 包含一些可能对您有帮助的参考资料——不确定，我没有看过它们——但无论如何，这应该会给你一些很好的搜索词。 :-)
是的，这完全有可能。 Self-balancing树算法实际上不需要是搜索树，这只是典型的表现。实际要求是以某种方式对节点进行排序（绳索提供）。
需要的是在插入和擦除时更新树权重。轮换不需要完全更新，本地就足够了。例如，左旋转需要将 parent 的权重添加到新的 parent（因为新的 parent 是旧的 parent 的右 child 没有必要沿着新的 parent 的右后裔树向下走，因为那已经是新的 parent 的左后裔树）。类似地，对于右旋转，只需要减去新 parent 的权重，因为新 parent 的右后裔树将成为旧 parent 的左后裔树.
我想可以创建一个插入件来更新重量，因为它会旋转，然后将重量添加到任何剩余的祖先上，但我在解决这个问题时没有费心。我只是将新节点的权重一直添加到树上，然后根据需要进行旋转。同样对于擦除，我进行了 fix-up 旋转，然后减去要删除的节点的权重，然后最终从树上解开节点。
是否有一个排序集的数据结构允许快速查找第 n 个（即最少但第 n 个）项目？也就是说，类似于绳索和红黑树的混合体。
似乎应该可以跟踪左子树的大小并通过旋转更新它，或者做一些其他聪明的事情，我希望聪明的人已经解决了这个问题。
Seems like it should be possible to either keep track of the size of the left subtree and update it through rotations […]
是的，这很有可能；但是与其跟踪左子树的大小，不如跟踪以给定节点为根的 complete 子树的大小要简单一些。 （然后您可以通过检查其左子树的大小来获取其左子树的大小。）它并不像您想象的那么棘手，因为只要其子节点是最新的，您就可以随时重新计算节点的大小，因此除了确保通过沿着树向上移动来重新计算大小之外，您不需要任何额外的簿记。
请注意，在大多数可变红黑树实现中，'put' 和 'delete' 一旦恢复了不变量就停止向树上回走，而使用这种方法你需要走在所有情况下一直备份树。这对性能的影响很小，但至少不难实现。 （在纯粹的功能性红黑树实现中，即使这也不是问题，因为它们总是必须沿着完整的路径返回以创建新的父节点。所以你可以将大小计算放在构造函数中 - 非常简单。)
已编辑 以回应您的评论：
I was vaguely hoping this data structure already had a name so I could just find some implementations out there and that there was something clever one could do to minimize the updating but (while I can find plenty of papers on data structures that are variations of balanced binary trees) I can't figure out a good search term to look for papers that let one lookup the nth least element.
集合中第 n 个最小值的奇特术语是 order statistic; so a tree structure that enables fast lookup by order statistic is called an order statistic tree。第二个 link 包含一些可能对您有帮助的参考资料——不确定，我没有看过它们——但无论如何，这应该会给你一些很好的搜索词。 :-)
是的，这完全有可能。 Self-balancing树算法实际上不需要是搜索树，这只是典型的表现。实际要求是以某种方式对节点进行排序（绳索提供）。
需要的是在插入和擦除时更新树权重。轮换不需要完全更新，本地就足够了。例如，左旋转需要将 parent 的权重添加到新的 parent（因为新的 parent 是旧的 parent 的右 child 没有必要沿着新的 parent 的右后裔树向下走，因为那已经是新的 parent 的左后裔树）。类似地，对于右旋转，只需要减去新 parent 的权重，因为新 parent 的右后裔树将成为旧 parent 的左后裔树.
我想可以创建一个插入件来更新重量，因为它会旋转，然后将重量添加到任何剩余的祖先上，但我在解决这个问题时没有费心。我只是将新节点的权重一直添加到树上，然后根据需要进行旋转。同样对于擦除，我进行了 fix-up 旋转，然后减去要删除的节点的权重，然后最终从树上解开节点。