大佬教程收集整理的这篇文章主要介绍了使用 RB 树的动态集，大佬教程大佬觉得挺不错的，现在分享给大家，也给大家做个参考。
假设我们有一个由整数组成的动态集合 S 和一个索引 i，我们希望找到 S 中按递增顺序写入的第 i 个最小负数（如果有）。 例子： S= {-5,-2,-1,2,5} 对 i=3 的 naswer 是 -1，对 i = 4 是未定义的。 目标是选择红黑树作为底层数据结构，并定义一个附加属性，允许在 O(lg n) 时间内解决问题。应该使用有关算法的任何指南来解决这样的问题？
它被称为订单统计树 (https://en.wikipedia.org/wiki/Order_statistic_treE)。
通常，您可以使用额外的属性（子树的大小）扩展树节点。对于叶子，它是 1，对于内部节点，它是
size(left_subtreE) + size(right_subtreE) + 1
Wiki 有明确的解释和伪代码。它适用于任何类型的平衡树（RB/AVl/Treap/etc），您需要在旋转（或任何树修改）期间支持子树的大小。
以上是大佬教程为你收集整理的使用 RB 树的动态集全部内容，希望文章能够帮你解决使用 RB 树的动态集所遇到的程序开发问题。
如果觉得大佬教程网站内容还不错，欢迎将大佬教程推荐给程序员好友。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。