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;
}