- /**
- * 目的:实现Treap(小堆 + 二叉查找树)
- *
- *
- *
- *
- *
- */
- #include <iostream>
- #include <cstdio>
- #include <algorithm>
- #include <cstring>
- #include <string>
- #include <time.h>
- using namespace std;
- int COUNT; //统计树中不重复节点的个数
- int HEIGHT; //统计数的高度
- //数据节点
- class DNode
- {
- public:
- int data;
- DNode():data(0){};
- DNode(int d):data(d){}
- bool operator = (const DNode &d){
- return data = d.data;
- }
- bool operator == (const DNode &d){
- return data == d.data;
- }
- bool operator > (const DNode &d){
- return data > d.data;
- }
- bool operator < (const DNode &d){
- return data < d.data;
- }
- void show(){
- cout << "***************" << endl;
- cout << "data: " << data << endl;
- }
- };
- //treap的节点
- class TNode{
- public:
- DNode data;
- int count;
- int fix;
- int size; //孩子节点的个数,根节点count的值也会加载里面
- TNode *left;
- TNode *right;
- TNode():data(DNode()), count(1), fix(rand()), size(1), left(NULL), right(NULL){}
- TNode(const DNode & d){
- data = d;
- count = 1;
- size = 1;
- fix = rand();
- left = right = NULL;
- }
- void show(){
- data.show();
- cout << "count: " << count << endl;
- cout << "fix: " << fix << endl;
- }
- int lsize(){ //得到左儿子这棵树的节点数
- return NULL == left ? 0 : left->size;
- }
- int rsize(){ //得到右儿子这棵树的节点数
- return NULL == right ? 0 : right->size;
- }
- void up(){ //算size
- if(this){
- size = lsize() + rsize() + count;
- }else{
- size = 0;
- }
- }
- };
- class Treap{
- private:
- void _leftRotate(TNode *& cur);
- void _rightRotate(TNode *& cur);
- public:
- TNode *root;
- Treap():root(NULL){}
- void insert(TNode *& cur, DNode data);
- void mid_travel(TNode * cur);
- TNode * search(TNode * cur, DNode data);
- //寻找第k小
- TNode * kth_mini(TNode *cur, const int k);
- //寻找第k大
- TNode * kth_max(TNode * cur, const int k);
- //从小到大的元素data排名
- int rank_min(TNode * cur, DNode data);
- int height(TNode * cur){//求树的高度
- if(NULL == cur){
- return 0;
- }
- return 1 + max(height(cur->left), height(cur->right));
- }
- };
- void Treap::_leftRotate(TNode *& cur){
- if(NULL == cur){
- return;
- }
- TNode * rson = cur->right;
- cur->right = rson->left;
- rson->left = cur;
- cur->up();
- rson->up();
- cur = rson;
- }
- void Treap::_rightRotate(TNode *& cur){
- if(NULL == cur){
- return;
- }
- TNode * lson = cur->left;
- cur->left = lson->right;
- lson->right = cur;
- cur->up();
- lson->up();
- cur = lson;
- }
- void Treap::insert(TNode *& cur, DNode data){ //注意更新节点的size
- if(NULL == cur){
- cur = new TNode(data);
- COUNT++;
- }else if(data > cur->data){
- insert(cur->right, data);
- if(cur->fix > cur->right->fix){
- _leftRotate(cur); //从插入点的上一点到根递归旋转,同时更新size
- }else{
- cur->up(); //如果不旋转就更新size
- }
- }else if(data < cur->data){
- insert(cur->left, data);
- if(cur->fix > cur->left->fix){
- _rightRotate(cur);
- }else{
- cur->up();
- }
- }else{
- cur->count++;
- cur->up();
- }
- }
- void Treap::mid_travel(TNode * cur){
- if(NULL != cur){
- mid_travel(cur->left);
- cur->show();
- mid_travel(cur->right);
- }
- }
- TNode * Treap::search(TNode * cur, DNode data){
- if(NULL == cur)
- return NULL;
- if(data > cur->data)
- return search(cur->right, data);
- else if(data < cur->data)
- return search(cur->left, data);
- else
- return cur;
- }
- /**
- * 可行性:利用二叉查找树的节点大小关系很容易得到第k大
- *
- * 1.如果cur节点的左孩子cur->left的size大于等于k,那么第k大一定在左子树
- * 2.如果cur节点的左孩子cur->left->size + cur->count 小于k,那么在右子树,此时让k=k-cur->count-cur->lsize();
- 3.否则就是cur了
- * 注意点:当k大于根节点的size就直接返回NULL;
- */
- TNode * Treap::kth_mini(TNode * cur, const int k){
- if(NULL == cur || k > cur->size)
- return NULL;
- if(k <= cur->lsize()){
- return kth_mini(cur->left, k);
- }else if(k > cur->lsize() + cur->count){
- return kth_mini(cur->right, k - cur->lsize() - cur->count);
- }else
- return cur;
- }
- TNode * Treap::kth_max(TNode * cur, const int k){
- return kth_mini(cur, root->size - k + 1);
- }
- //排名
- //没找到返回-1
- int Treap::rank_min(TNode * cur, DNode data){
- //首先判断data是否在里面
- if(NULL == search(cur, data)){
- return -1;
- }
- if(NULL == cur){
- return 0;
- }
- if(data == cur->data){
- return cur->lsize() + 1;
- }else if(data > cur->data){
- return cur->lsize() + cur->count + rank_min(cur->right, data);
- }else{
- return rank_min(cur->left, data);
- }
- }
- //不是装逼,编译器输出中文乱码
- int main(){
- freopen("out.txt", "w", stdout);
- srand((unsigned)time(NULL));
- Treap *root = new Treap();
- int num = 3000000;
- COUNT = 0; //将不重复节点统计变量置0
- //随机生成num个节点插入树中, 当有序生成节点插入时数的高度依然不变
- //如上所说,treap是期望性高度为lg(n), 而二叉查找树当遇到有序节点插入,将导致严重退化
- for(int i= 0; i < num; i++){
- DNode * newD = new DNode(rand() % num);
- root->insert(root->root, *newD);
- }
- //得到树的高度, 看看treap到底有多平衡
- HEIGHT = root->height(root->root);
- //中序遍历可排序
- root->mid_travel(root->root);
- cout << "############### end mid travel #########" << endl;
- cout << "k th max is: " << endl;
- TNode * kth = root->kth_max(root->root, 5);
- kth->show();
- cout << endl << endl;
- //验证第k大 和 排名为k大的 data 是否相同
- int rank = root->rank_min(root->root, kth->data);
- if(kth->data == root->kth_max(root->root, root->root->size - rank + 1)->data){
- cout << "rank with kth is right" << endl;
- }else{
- cout << "rank with kth is error" << endl;
- }
- cout << "tree's height is: " << HEIGHT << endl;
- cout << "no repeat node is: " << COUNT << endl;
- cout << "root's size: " << root->root->size << endl;
- return 0;
- }
- //该片段来自于http://www.codesnippet.cn/detail/3107201410064.html
来源: http://www.codesnippet.cn/detail/3107201410064.html