顺序统计树
维基百科,自由的 encyclopedia
在计算机科学,顺序统计树(英语:Order statistic tree)是二叉搜索树的变种。除了插入、查询和删除,这种数据结构还支持以下两种操作:
- Select(i) — 在树中查询第i小的元素
- Rank(x) – 查找元素x的排名
这两种操作的平均时间复杂度是。当所用数据结构是平衡二叉树时,这是最坏复杂度。
在计算机科学,顺序统计树(英语:Order statistic tree)是二叉搜索树的变种。除了插入、查询和删除,这种数据结构还支持以下两种操作:
这两种操作的平均时间复杂度是。当所用数据结构是平衡二叉树时,这是最坏复杂度。