treap平衡树练习

你的名字 2021-11-23 03:52 205阅读 0赞

平衡树就是左旋右旋的一种树，赵老师讲数据结构的时候一直没实现，觉得很简单。

结果是很简单，但是，，代码量有点不敢恭维。

下面是一个大神的板子。自己敲了一遍。

#include <bits/stdc++.h>
    using namespace std;
    
    #define maxn 100010
    #define INF 0x7fffffff
    
    struct treapNode {
    	int lChild, rChild; // 左右子节点下标
    	int value, weight;  // 节点关键码及权值
    	int count, size;    // 副本数及子树大小
    } treap[maxn];
    
    int numNodes, root, n;
    
    int newNode(int val) {
    	numNodes++;
    	treap[numNodes].value = val;
    	treap[numNodes].weight = rand(); // 随机权值
    	treap[numNodes].count = treap[numNodes].size = 1;
    	return numNodes;
    } // 建立一个新的节点
    
    void update(int p) {
    	treap[p].size = treap[treap[p].lChild].size +
    		treap[treap[p].rChild].size +
    		treap[p].count;
    } // 更新某一个点的 size 方便获取排名
    
    void build() {
    	newNode(-INF); // 保证 BST 性质的两个点
    	newNode(INF);
    	root = 1;
    	treap[root].rChild = 2;
    	update(root);
    } // 初始化
    
    int getRankByVal(int p, int val) {
    	if (p == 0) return 0;
    	if (val == treap[p].value)
    		return treap[treap[p].lChild].size + 1;
    	if (val < treap[p].value)
    		return getRankByVal(treap[p].lChild, val);
    	return getRankByVal(treap[p].rChild, val) +
    		treap[treap[p].lChild].size +
    		treap[p].count;
    }
    // 上下两个函数很好理解，不作赘述
    // 一切从 BST 性质出发
    int getValByRank(int p, int rnk) {
    	if (p == 0) return INF;
    	if (treap[treap[p].lChild].size >= rnk)
    		return getValByRank(treap[p].lChild, rnk);
    	if (treap[treap[p].lChild].size + treap[p].count >= rnk)
    		return treap[p].value;
    	return getValByRank(treap[p].rChild,
    		rnk - treap[treap[p].lChild].size - treap[p].count);
    }
    
    void zig(int &p) {
    	int q = treap[p].lChild;
    	treap[p].lChild = treap[q].rChild;
    	treap[q].rChild = p;
    	p = q;
    	update(treap[p].rChild);
    	update(p); // 别忘记更新
    }
    
    void zag(int &p) {
    	int q = treap[p].rChild;
    	treap[p].rChild = treap[q].lChild;
    	treap[q].lChild = p;
    	p = q;
    	update(treap[p].lChild);
    	update(p);
    }
    
    void insert(int &p, int val) {
    	if (p == 0) {
    		p = newNode(val);
    		return;
    	}
    	if (val == treap[p].value) {
    		treap[p].count++;
    		update(p);
    		return;
    	}
    	if (val < treap[p].value) {
    		insert(treap[p].lChild, val);
    		if (treap[p].weight < treap[treap[p].lChild].weight) zig(p);
    	} else {
    		insert(treap[p].rChild, val);
    		if (treap[p].weight < treap[treap[p].rChild].weight) zag(p);
    	} // zig 和 zag 操作，保证满足大根堆性质
    	update(p);
    } // 插入一个点
    
    int getPre(int val) {
    	int ans = 1;
    	int p = root;
    	while (p != 0) {
    		if (val == treap[p].value) {
    			if (treap[p].lChild > 0) {
    				p = treap[p].lChild; // 左子树上不断向右走，获取最大的前驱
    				while (treap[p].rChild > 0) p = treap[p].rChild;
    				ans = p;
    			}
    			break;
    		}
    		if (treap[p].value < val &&
    			treap[p].value > treap[ans].value) ans = p; // 尝试更新答案
    		p = val < treap[p].value ? treap[p].lChild : treap[p].rChild;
    	}
    	return treap[ans].value;
    } // 获取前驱
    
    int getNext(int val) {
    	int ans = 2;
    	int p = root;
    	while (p != 0) {
    		if (val == treap[p].value) {
    			if (treap[p].rChild > 0) {
    				p = treap[p].rChild; // 右子树上不断向左走，获取最小的后继
    				while (treap[p].lChild > 0) p = treap[p].lChild;
    				ans = p;
    			}
    			break;
    		}
    		if (treap[p].value > val &&
    			treap[p].value < treap[ans].value) ans = p; // 尝试更新答案
    		p = val < treap[p].value ? treap[p].lChild : treap[p].rChild;
    	}
    	return treap[ans].value;
    }
    
    void remove(int &p, int val) {
    	if (p == 0) return;
    	if (val == treap[p].value) {
    		if (treap[p].count > 1) {
    			treap[p].count--;
    			update(p);
    		} else if (treap[p].lChild != 0 || treap[p].rChild != 0) {
    			if (treap[p].rChild == 0 ||
    				treap[treap[p].lChild].weight > treap[treap[p].rChild].weight) {
    				zig(p);
    				remove(treap[p].rChild, val);
    			} else {
    				zag(p);
    				remove(treap[p].lChild, val);
    			} // 通过旋转来删除节点
    			update(p);
    		} else p = 0;
    		return;
    	}
    	if (val < treap[p].value) remove(treap[p].lChild, val);
    	else remove(treap[p].rChild, val);
    	update(p);
    }
    
    int main() {
    	ios::sync_with_stdio(false);
    	cin.tie(NULL);
    	numNodes = 0;
    	build();
    	cin >> n;
    	int opt, x;
    	while (n--) {
    		cin >> opt >> x;
    		switch (opt) {
    			case 1: { insert(root, x); break; }
    			case 2: { remove(root, x); break; }
    			case 3: { cout << getRankByVal(root, x) - 1 << endl; break; } // 减一
    			case 4: { cout << getValByRank(root, x + 1) << endl; break; } // 加一
    			case 5: { cout << getPre(x) << endl; break; }
    			case 6: { cout << getNext(x) << endl; break; }
    		}
    	}
    	return 0;
    }

今天上午刚刚搞明白什么是后缀数组，只写了一个模板题，下午就搞后缀自动机。这是第二遍看后缀自动机了，感觉有点东西了，虽然还是不太明白，但是事不过三。明天再看一遍。相信就没问题了。

加油！

7.25晚11点更新

啪啪打脸，又是没看懂

7.26上午11点更新

啪啪打脸

7.26下午5点更新

啪啪打脸