@fuheimao 2015-08-11T12:04:03.000000Z 字数 2135 阅读 545

# Treap

数据结构 腹黑猫

#include "iostream"#include "ctime"#include "cstdlib"using namespace std;struct Node{    Node* Child[2];    int Key;    int Priority;    int Size;    void Maintain(){        Size = 1;        if (Child[0] != NULL) Size += Child[0] -> Size;        if (Child[1] != NULL) Size += Child[1] -> Size;    }};void Rotate(Node* &Top, bool Flick){    Node* K = Top -> Child[Flick ^ 1];    Top -> Child[Flick ^ 1] = K -> Child[Flick];    K -> Child[Flick] = Top;    Top -> Maintain();    K -> Maintain();    Top = K;}int Find(Node* Top, int Key){    while (Top != NULL){        if (Top -> Key == Key) return true;        int LOR = Key > Top -> Key;        Top = Top -> Child[LOR];     }    return false;}void Insert(Node* &Top, int Key){    //if (Find(Top, Key)) return; 若有重复元素注释掉……    if (Top == NULL){        Top = new Node();        Top -> Child[0] = Top -> Child[1] = NULL;        Top -> Key = Key;        Top -> Priority = rand();    }else{        int LOR = Key > Top -> Key;        Insert(Top -> Child[LOR], Key);        if (Top -> Child[LOR] -> Priority > Top -> Priority){            Rotate(Top, LOR ^ 1);        }    }    Top -> Maintain();}void Remove(Node* &Top, int Key){    int LOR = Key > Top -> Key;    if (Key == Top -> Key){        if (Top -> Child[0] == NULL){            Top = Top -> Child[1];        }else if (Top -> Child[1] == NULL){            Top = Top -> Child[0];        }else{            LOR = Top -> Child[0] -> Priority > Top -> Child[1] -> Priority;            Rotate(Top, LOR);            Remove(Top -> Child[LOR], Key);        }    }else{        Remove(Top -> Child[LOR], Key);    }    if (Top != NULL) Top -> Maintain();}int FindKth(Node* Top, int K){    if (Top == NULL || K <= 0 || K > Top -> Size) return 0;    int Size = (Top -> Child[1] == NULL ? 0 : Top -> Child[1] -> Size);    if (K == Size + 1){        return Top -> Key;    }else if (K <= Size){        return FindKth(Top -> Child[1], K);    }else{        return FindKth(Top -> Child[0], K - Size - 1);    }}int Rank(Node* Top, int Key){    if (!Find(Top, Key)) return 0;    int _Rank = (Top -> Child[0] == NULL ? 0 : Top -> Child[0] -> Size);    if (Top -> Key == Key){        return _Rank + 1;    }else if (Top -> Key > Key){        return Rank(Top -> Child[0], Key);    }else{        return Rank(Top -> Child[1], Key) + _Rank + 1;    }}Node* Predecessor(Node* Top, Node* Best, int Key){    if (Top == NULL) return Best;    if (Key < Top -> Key){        return Predecessor(Top -> Child[0], Best, Key);    }    return Predecessor(Top -> Child[1], Top, Key);}Node* Successor(Node* Top, Node* Best, int Key){    if (Top == NULL) return Best;    if (Key <= Top -> Key){        return Successor(Top -> Child[0], Top, Key);    }    return Successor(Top -> Child[1], Best, Key);}int main(int argc, char const *argv[]){    Node* Root = NULL;    Insert(Root, 10);    Insert(Root, 50);    Remove(Root, 10);    Insert(Root, 400);    Insert(Root, 20);    cout << endl << FindKth(Root, 2);    cout << endl << Rank(Root, 400);    return 0;}

• 私有
• 公开
• 删除