树堆算法

treap算法

1. 所谓树堆就是一棵改变了结点排序方式的二叉搜索树.通常,树内的每个结点都有一个关键值.另外还要为每一个结点指定x.priority(优先级),它是一个独立选取的随机数.假设每个优先级是不同的且树堆里每个结点存取的数值也是不同的.树堆里的关键值(x.key)必须遵循二叉搜索树的规则,而优先级(x.priority)遵循最小堆的规则.
   
   • 如果v是u的左孩子,则v.key
   • 如果v是u的右孩子,则v.key>u.key
   • 如果v是u的孩子,则v.priority>u.priority
2. 这有助于我们用有趣的角度去理解树堆,假设我们将带有关键词的结点(x1,x2,x3.....xn)插入到树堆里.得到的一棵树堆是通过将这些结点以他们的优先级(随机选取)的顺序插入一棵正常的二叉搜索树形成的,即xi.priority < xj.priority表示xi在xj之前被插入.
   
   • a. ：在给定一个已经带有关键词和优先级(互异)的结点x1,x2,x3.....xn组成的集合里,存在唯一的一棵treap树与这些结点相关联.
   • b. ：treap树的期望高度是O(lgn),因此treap内查找一个值所花的时间是O(lgn),让我们看看一个新节点插入到一个已经存在的treap树中,要做的第一件事就是将一个随机的优先级赋予到这个新的结点.通过某些旋转操作去是新插入的结点满足treap的性质.
     
     • c.难点：同时满足堆和BST的性质， 这个需要旋转（这里统一用小堆）， 只是在插入和删除元素的时候会用到旋转
       左旋转： 当随机数（以后称为修正值）大于右儿子的修正值，就坐转
       右旋转：当修正值大于左儿子的修正值， 就右转
       不可能同时小于左右儿子的修正值， 因为每次有了其中一种，treap就会被调整.

    int COUNT;  //统计树中不重复节点的个数  
    int HEIGHT; //统计数的高度  
    #include <iostream>  
    #include <cstdio>  
    #include <algorithm>  
    #include <cstring>  
    #include <string>  
    #include <time.h>  
    using namespace std;  

//数据节点  
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;  
}