扩充的数据结构

程序员文章站 2022-06-05 19:42:11

...

编程中常常会遇到已有的数据结构无法解决问题，这时不要急着创建新的数据结构，可以在已有数据结构的基础上添加新的字段。本节在红黑树这一基础数据结构上进行扩展，得出两个重要的应用—动态顺序统计和区间树。

一、动态顺序统计

一种支持一般动态集合上顺序统计操作的数据结构。通过这种数据结构，可以快速找到一个集合中的第i小的数，（select）或给出一个指定元素在集合的全序中的位置。（rank）

【思想】添加新项：在红黑树的结点上记录下该结点的子树个数。size[x] = size[left[x]] + size[right[x]] +1。若结点为空，则为0。

此外当你对该扩展的数据结构进行插入和删除操作时，需随时更新子树的大小，与插入和删除操作同步进行，但是需要重新使其回到平衡。主要在于case2和case3这两种情况的旋转。<可以与算法系列笔记4>红黑树的插入代码进行对比，看修改情况。

代码：

返回第i 排名的元素os_select(i)

BSTNode* OSRBTree::os_select(BSTNode *p, const int &ith){
	if(p == NULL) return p;
	int k = 1;
	if(p->left != NULL){
		k = p->left->size + 1;           // 当前该结点所对应的rank
		
	}
	if(ith == k) return p;
	if(ith < k) return os_select(p->left, ith);
	else return os_select(p->right, ith - k);
}

给定一个元素x，返回其排名(os_rank(x))

//  return the rank of value
int OSRBTree::os_rank(BSTNode *p, const int &value){
	if(p == NULL) return 0;
	int k = 1;
	if(p->left != NULL)
		k = p->left->size + 1;
	if(p->val == value)
		return k;
	else if(p->val > value) return os_rank(p->left, value);
	else return os_rank(p->right, value)+k;
}

方法论：如<OSTree—顺序统计树>

1：选择一个基础的数据结构(red-black tree)

2：在数据统计中维护一些附加信息(子树大小)

3：验证这个数据结构上的信息不会受修改操作的影响(insert, delete---rotations)

4：建立新的运算。假设新的数据已经存好了，然后开始使用这些信息(os_select, os_rank).

二、区间树(Interval Tree)

【图示化补充】

问题：保存一系列的区间，比如说时间区间。需要查询集合中的所有区间，与给定区间发生重叠的有哪些？

我们按照上面提到的方法论来进行：

1：选择红黑树作为基本的数据结构，并将区间的较低值(low)作为键值

2：将结点子树的最大值作为新添加的项(m[x] = max{high[int[x]],m[left[x]], m[right[x]]}).

3：是否受插入删除等操作的影响？受，但是在O(1)时间内就能调整过来，见代码。

4：新的操作，查询集合中与给定区间重叠的一个区间。

#ifndef INTERVALTREE
#define INTERVALTREE
#include <iostream>
#include <string>
using namespace std;
struct dataNode{
    int low;
    int high;
};
class BSTNode{
public:
    BSTNode *left, *right;
    BSTNode *parent;
    int val;
    dataNode d;
    string color;
    int m;         // 最大值
};
 
class IntervalTree{
public:
    IntervalTree(const dataNode &d)
    {
        root = new BSTNode();
        root->d = d;
        root->color = "black";
        root->left = NULL;
        root->right = NULL;
        root->m = d.high;
        root->parent = NULL;
        root->val = d.low;
    }
 
    BSTNode* insertBST(BSTNode *p, const dataNode &d);
    void insertIntervalTree(BSTNode *root1, const dataNode &d);
    void inorderOSRBTree(BSTNode *p);
    BSTNode* intervalSearch(BSTNode *p, const dataNode &d);
public:
    BSTNode *root;
    void destroyBST(BSTNode *p);
};
 
#endif