Treap实现名次树C++

Treap实现名次树C++

相关内容

Treap树堆C++实现

名次树

相比Treap结点，增加数据域size，表示其及其所有后代结点总数，即叶节点最小只有1

  • 返回第k个元素，即第k小的元素
    从根节点开始，递归地在左子树或者右子树中寻找，若在右子树中寻找，则需要将k减去父结点左子树后代结点及父结点总数，递归地，直到找到对应结点返回关键字，或没找到返回-1
int RankTree::kth(Node *p, int k) {int order = p->size - (p->right == NULL ? 0 : p->right->size);if (order == k) {return p->data;} else if (order > k) {return p->left == NULL ? -1 : kth(p->left, k);} else {return p->right == NULL ? -1 : kth(p->right, k - order);}
}
  • 返回值x的名次，即比x小的结点的个数加1
    从根节点开始，递归地在左子树或者右子树中寻找，若右子树中寻找则需要加上父结点左子树后代结点及父结点总数，递归地，直到找到关键字返回名次，或未找到返回-1
int RankTree::rank(int x, int order) {Node *p = root;while (p) {if (p->data == x) {return p->size - (p->right == NULL ? 0 : p->right->size) + order;} else if (p->data < x) {order = p->size - (p->right == NULL ? 0 : p->right->size) + order;p = p->right;} else {p = p->left;}}return -1;
}

实现代码

/*
author : eclipse
email  : eclipsecs@qq.com
time   : Sat Jun 13 18:20:57 2020
*/
#include<bits/stdc++.h>
using namespace std;struct Node {int data;Node *left;Node *right;int priority;int size;Node(int value, int level) : data(value), left(NULL), right(NULL), priority(level) {}void maintain();
};void Node::maintain() {size = 1 + (left == NULL ? 0 : left->size) + (right == NULL ? 0 : right->size);
}class RankTree {
private:Node *root;void leftRotate(Node* &p);void rightRotate(Node* &p);void insert(Node* &p, int value);void remove(Node* &p, int value);int kth(Node *p, int k);int rank(int x, int order);void traverse(Node *p);
public:RankTree();void insert(int value);void remove(int x);Node* search(int x);int kth(int k);int rank(int x);void traverse();
};RankTree::RankTree() {root = NULL;
}void RankTree::leftRotate(Node* &p) {Node *k = p->right;p->right = k->left;k->left = p;p->maintain();k->maintain();p = k;
}void RankTree::rightRotate(Node* &p) {Node *k = p->left;p->left = k->right;k->right = p;p->maintain();k->maintain();p = k;
}void RankTree::insert(int value) {insert(root, value);
}void RankTree::insert(Node* &p, int value) {if (p == NULL) {p = new Node(value, rand());} else {if (value == p->data) {return;} else if (value < p->data) {insert(p->left, value);} else {insert(p->right, value);}if(p->left && p->left->priority > p->priority) {rightRotate(p);} else if(p->right && p->right->priority < p->priority) {leftRotate(p);}}p->maintain();
}void RankTree::remove(int value) {remove(root, value);
}void RankTree::remove(Node* &p, int value) {if (p->data == value) {if (p->left == NULL) {p = p->right;} else if (p->right == NULL) {p = p->left;} else {if (p->left->priority > p->right->priority) {rightRotate(p);remove(p->right, value);} else if (p->left->priority < p->right->priority) {leftRotate(p);remove(p->left, value);}}} else {if (value < p->data) {remove(p->left, value);} else {remove(p->right, value);}}p->maintain();
}Node* RankTree::search(int value) {Node *p = root;while (p) {if (p->data == value) {return p;} else {p = p->data < value ? p->right : p->right;}}return NULL;
}int RankTree::kth(int k) {return kth(root, k);
}int RankTree::kth(Node *p, int k) {int order = p->size - (p->right == NULL ? 0 : p->right->size);if (order == k) {return p->data;} else if (order > k) {return p->left == NULL ? -1 : kth(p->left, k);} else {return p->right == NULL ? -1 : kth(p->right, k - order);}
}int RankTree::rank(int x) {rank(x, 0);
}int RankTree::rank(int x, int order) {Node *p = root;while (p) {if (p->data == x) {return p->size - (p->right == NULL ? 0 : p->right->size) + order;} else if (p->data < x) {order = p->size - (p->right == NULL ? 0 : p->right->size) + order;p = p->right;} else {p = p->left;}}return -1;
}void RankTree::traverse() {traverse(root);
}void RankTree::traverse(Node *p) {if (p->left) {traverse(p->left);}printf("%d ", p->data);if (p->right) {traverse(p->right);}
}int main(int argc, char const *argv[]) {RankTree *rankTree = new RankTree();int N;int value;scanf("%d", &N);for (int i = 0; i < N; i++) {scanf("%d", &value);rankTree->insert(value);}scanf("%d", &value);printf("%d is in %d-th place\n", value, rankTree->rank(value));scanf("%d", &value);printf("%d-th element is %d\n", value, rankTree->kth(value));rankTree->traverse();return 0;
}

输入数据

10
1 11 7 14 17 18 9 19 8 12
19 9

输出结果

19 is in 10-th place
9-th element is 18
1 7 8 9 11 12 14 17 18 19

鸣谢

算法竞赛入门经典训练指南

最后

  • 由于博主水平有限，不免有疏漏之处，欢迎读者随时批评指正，以免造成不必要的误解！