数据结构的扩张

data structure

Posted by Jow on July 2, 2019

目录

  1. 动态顺序统计
  2. 如何扩张数据结构
  3. 区间树

在实际的环境中,可能你并不需要太多的复杂的东西,但是那些基本的知识你一定要很清楚,你要明白如果将这些基本的东西通过演变变成适合当前场景的复杂的东西。

动态顺序统计

在这里我们通过给红黑树节点添加一个数目的属性,即这棵子树有多少个节点。然后从根开始查找就能很快的查找到在某个位置的数据,例如第5小的数据。

如何扩张数据结构

  1. 选择一种数据结构
  2. 确定基础数据结构中要维护的附加信息
  3. 检验基础数据及结构上的基本修改操作能否维护附加信息
  4. 设计一些新操作

区间树

  1. 红黑树作为基本数据结构
  2. 节点x除了自身区间信息之外,还包含区间内的最大值,区间左开右闭
  3. 维护树中的数据
  4. 设计新操作