第十四章——数据结构的扩张

xiaoxiao2025-07-18  6

  虽然写这个博客主要目的是为了给我自己做一个思路记忆录,但是如果你恰好点了进来,那么先对你说一声欢迎。我并不是什么大触,只是一个菜菜的学生,如果您发现了什么错误或者您对于某些地方有更好的意见,非常欢迎您的斧正!

14.1动态顺序统计

n个元素结合中第i个顺序统计量就使该集合中的具有第i小关键字的元素。

本节介绍如何修改红黑树,使得在O(lgn)的时间内确定任何的顺序统计量。

顺序统计树T只是简单地在每个结点再附加一个信息x.size的一棵红黑树。这个信息包含了以x为根的子树(包括x本身)的结点树,即这棵子树的大小。

x.size=x.left.size + x.right.size + 1

查找具有给定秩(集合线性序中的位置)的元素

确定一个元素的秩

对子树规模的维护 在左旋代码中添加:

14.2如何扩张数据结构

14.3区间树 没怎么看懂,有兴趣的话可以看一下这个博客,写的还不错。 https://blog.csdn.net/u010183397/article/details/46917439

转载请注明原文地址: https://www.6miu.com/read-5033281.html

最新回复(0)